Algorithmus für "geschlossene" Kreise [gelöst]

Vom einfachen Programm zum fertigen Debian-Paket, Fragen rund um Programmiersprachen, Scripting und Lizenzierung.
Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 18:20:00

tobo hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 17:59:11
Solange du nicht genauer sagst, was du suchst, kann dir niemand sagen, wie du es findest.
Das ganze ist eine Sternenkarte eines Spiels.
Jedes Feld ist ein Sektor in dem es entweder nichts oder ein Sonnensystem oder sonstwas (ein Raumschiff, ein Ereignis, ...) gibt.
Was in dem jeweiligen Sektor ist, ist vor der Berechnung (rand()) unbekannt.
Deshalb suche ich einen Algo. der, ohne Felder auszulassen, einen bestimmten Radius absucht.

gruß heinz

Benutzeravatar
GregorS
Beiträge: 2518
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Algorithmus für "geschlossene" Kreise

Beitrag von GregorS » 13.04.2018 18:25:47

'Ne Idee: „Zeichne“ Kreise mit immer größeren Radien, wobei die Schrittweite 5, 10 oder 20 ist. Den Bereich zwischen dem neuen und dem letzten Kreis durchsuchst Du dann mit einem missbrauchten Flood-Fill-Algorithmus.

Dann hättest Du das Problem mit den nicht gesetzten Pixeln erschlagen. Und wenn es mehrere Fundstellen gibt, behandelst Du die separat.

Das wär' doch was, oder ...

Gruß

Gregor
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

Benutzeravatar
MSfree
Beiträge: 10686
Registriert: 25.09.2007 19:59:30

Re: Algorithmus für "geschlossene" Kreise

Beitrag von MSfree » 13.04.2018 18:27:40

Ich verstehe den Zusammenhang zwischen finden von "Dingen" und dem Zeichnen von Kreisen nicht.

Das Finden von "Dingen" hört sich für mich nach dem typischen CAD-Problem an, wo man von der Cursorposition den nächsten Punkt fangen (snappen) will. Das Problem löst man aber nicht durch das Zeichnen von Kreisen sondern durch suchen von "Dingen" in einer geeigneten Datenstruktur, typischerweise KD-Bäume, Quadtrees oder Octrees.

Klar, man kann seine "Dinge" auch in eine große Pixelmatrix eintragen und die linear durchsuchen, das dauert halt schlicht viel zu lange.

Wenn es wirklich um das Zeichnen von Kreisen geht, dann würde ich den Kreis in ein n-Eck zerlegen und jede Kante des n-Ecks mit einer Antialiasingmethode zeichnen. Idealwerweise läßt man das die Graphikhardware machen, dann kann man mehrere Milliarden Pixel pro Sekunden zeichnen, mit einer 4-Kern CPU kommt man kaum über 200 Millionen Punkte pro Sekunde.

Naja, und was RAM angeht, was sind schon 65536 mal 65536 Pixel zu 3 Byte, wenn man 16GB RAM im Rechner hat? :mrgreen:

Benutzeravatar
GregorS
Beiträge: 2518
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Algorithmus für "geschlossene" Kreise

Beitrag von GregorS » 13.04.2018 18:40:40

MSfree hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:27:40
Ich verstehe den Zusammenhang zwischen finden von "Dingen" und dem Zeichnen von Kreisen nicht.
Das Finden von "Dingen" hört sich für mich nach dem typischen CAD-Problem an, wo man von der Cursorposition den nächsten Punkt fangen (snappen) will. Das Problem löst man aber nicht durch das Zeichnen von Kreisen sondern durch suchen von "Dingen" in einer geeigneten Datenstruktur, typischerweise KD-Bäume, Quadtrees oder Octrees.
Der Unterschied zum CAD-Problem ist, dass man beim CAD-Problem die „Fundstellen“ (Gitterpunkte o.ä.) kennt. Heinz sucht aber so etwas wie den „nächsten Planeten der M-Klasse“. Dessen Position kennt er aber nicht.
MSfree hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:27:40
Naja, und was RAM angeht, was sind schon 65536 mal 65536 Pixel zu 3 Byte, wenn man 16GB RAM im Rechner hat? :mrgreen:
Das ist allerdings ein guter Punkt.

Gruß

Gregor
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 18:43:23

GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:25:47
'Ne Idee: „Zeichne“ Kreise mit immer größeren Radien, wobei die Schrittweite 5, 10 oder 20 ist. Den Bereich zwischen dem neuen und dem letzten Kreis durchsuchst Du dann mit einem missbrauchten Flood-Fill-Algorithmus.
Danke für den Vorschlag!
Die Idee ist gar nicht schlecht, man hätte keine "Leerräume" mehr.
Allerdings müsste man dann erst alle Felder in diesem Zwischenraum durchsuchen (berechnen) um danach den mit dem geringsten
Abstand finden zu können.
Mit der "Kreis-Mal-Methode" wäre die Anzahl der "nutzlos" berechneten Felder minimal da man, wenn gefunden,
direkt die Suche beenden kann.

gruß heinz

Benutzeravatar
GregorS
Beiträge: 2518
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Algorithmus für "geschlossene" Kreise

Beitrag von GregorS » 13.04.2018 18:51:55

heinz hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:43:23
...
Allerdings müsste man dann erst alle Felder in diesem Zwischenraum durchsuchen (berechnen) um danach den mit dem geringsten
Abstand finden zu können.
...
Da schmeiße ich Dir mit Freuden einen 17-Tonnen-Container auf die Füße. *eg*

Nimm einen Container, der nach der Entfernung zum Schiff sortiert. Wenn es mehrere Fundstellen gibt, befindet sich das gesuchte Ding an der ersten Position.

Gruß

Gregor
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 18:54:32

MSfree hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:27:40
Das Finden von "Dingen" hört sich für mich nach dem typischen CAD-Problem an, wo man von der Cursorposition den nächsten Punkt fangen (snappen) will. Das Problem löst man aber nicht durch das Zeichnen von Kreisen sondern durch suchen von "Dingen" in einer geeigneten Datenstruktur, typischerweise KD-Bäume, Quadtrees oder Octrees.
Das Problem ist, dass die Datenstruktur eben nicht bekannt ist.
Wie schon mehrmals erwähnt ist die Datenstruktur nicht vorhanden, sie wird errechnet.
Ob in einem Feld/Sektor/Pixel/Wasauchimmer etwas ist oder nicht ist vor der Berechnung nicht bekannt.
Um es wie in einem CAD-Programm zu machen, müsste ich die Position aller Sterne kennen um den nächsten zu finden.
Das ist aber nicht der Fall und bei der Größe auch nicht so einfach möglich.

gruß heinz

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 19:06:24

MSfree hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:27:40
Naja, und was RAM angeht, was sind schon 65536 mal 65536 Pixel zu 3 Byte, wenn man 16GB RAM im Rechner hat? :mrgreen:
Bei meinem Testlauf kamen in der Karte über 21 000 000 Systeme heraus.
Bei einer größe von, sagen wir mal nur 500 byte pro System (Sterne, Planeten, Schiffe, Ressourcenfundstellen auf fast jedem Planet, ...), sind das schon über 10 Gbyte...
Auch würde die Erstellung der Karte eine halbe Ewigkeit dauern.

Deshalb kam ich ja auf die Idee es mittels rand() zu machen...

gruß heinz

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 19:11:25

GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:51:55
Nimm einen Container, der nach der Entfernung zum Schiff sortiert. Wenn es mehrere Fundstellen gibt, befindet sich das gesuchte Ding an der ersten Position.
Dazu müsste ich aber doch auch erst alle Systeme berechnen/erstellen um sie in die Container legen zu können...

gruß heinz

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 19:13:14

Oh mann, was hab ich angerichtet...

Ich suche doch "nur" einen Algo. der einen Kreis ohne "Lücken" berechnen kann... :lol:

gruß heinz

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 19:23:03

Nochmal eine Grafik zum verdeutlichen:
1723
Gezeichnet wurden immer wieder Kreise, bei denen der Radius jedes mal um 1 erhöht wurde.
Wie man sieht, werden hier sehr viele Pixel nicht gezeichnet.
Was ich suche ist ein Algo. der diese leerstellen nicht hat.

gruß heinz

Benutzeravatar
GregorS
Beiträge: 2518
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Algorithmus für "geschlossene" Kreise

Beitrag von GregorS » 13.04.2018 19:36:07

heinz hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 19:11:25
GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 18:51:55
Nimm einen Container, der nach der Entfernung zum Schiff sortiert. Wenn es mehrere Fundstellen gibt, befindet sich das gesuchte Ding an der ersten Position.
Dazu müsste ich aber doch auch erst alle Systeme berechnen/erstellen um sie in die Container legen zu können...
Du musst ganz genau das tun, was Du sowieso tun musst. Ein Sektor, den Du nicht nach dem Gesuchten durchsuchst, ist in diesem Fall ja mal *gar nichts* wert. In den Container tust Du nur die Sektoren bzw. Systeme, die Du gefunden hast. Und mit dem richtigen Container, werden die „automatisch“ nach dem sortiert, was Du brauchst. Am Ende einer „Flood-Fill-Orgie“ guckst Du, ob in dem Container etwas drin ist. Wenn ja, ist es das erste Element, wenn nicht, nimmst Du Dir den nächsten „Suchradius“ vor. Fäddich.

Gruß

Gregor
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

tobo
Beiträge: 1964
Registriert: 10.12.2008 10:51:41

Re: Algorithmus für "geschlossene" Kreise

Beitrag von tobo » 13.04.2018 19:37:08

Wie ich das verstehe: Du suchst nicht den Kreis, sondern die Kreislinie. Auf dieser Linie (1 mal rumgelaufen; Symmetrie 1/8) schaust du dir die Informationen der dabei jeweils betretenen Felder/Pixel an. Ist auf keinem dieser Felder die Information vorhanden, dann Radius+1 und laufe die nächstgrößere Kreislinie ab. Problem dabei, du willst natürlich keine Felder auslassen, du darfst aber auch keine Felder doppelt betreten, da die Information dieser Felder dynamisch generiert wird und deswegen variiert. Passt das so in etwa?

Nebenbei, kennst du das schon?
http://www.mttcs.org/Skripte/Pra/Materi ... esung9.pdf

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 19:49:08

tobo hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 19:37:08
Wie ich das verstehe: Du suchst nicht den Kreis, sondern die Kreislinie. Auf dieser Linie (1 mal rumgelaufen; Symmetrie 1/8) schaust du dir die Informationen der dabei jeweils betretenen Felder/Pixel an. Ist auf keinem dieser Felder die Information vorhanden, dann Radius+1 und laufe die nächstgrößere Kreislinie ab. Problem dabei, du willst natürlich keine Felder auslassen, du darfst aber auch keine Felder doppelt betreten, da die Information dieser Felder dynamisch generiert wird und deswegen variiert. Passt das so in etwa?
Klasse! Ich glaube mal Du bist der erste, der wirklich verstanden hat worum es mir geht.
Das mit den doppelten Feldern ist nicht ganz so wichtig:
Es ist nicht schlimm wenn Felder doppelt betreten werden, ich möchte es nur minimieren um Rechenzeit zu sparen...
Keine Felder auszulassen ist allerdings sehr wichtig.
tobo hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 19:37:08
Nebenbei, kennst du das schon?
http://www.mttcs.org/Skripte/Pra/Materi ... esung9.pdf
Nein, ich schau gleich mal rein. Danke...

gruß heinz

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 19:57:23

GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 19:36:07
...In den Container tust Du nur die Sektoren bzw. Systeme, die Du gefunden hast.
Ich möchte eigentlich, wenn möglich, garnichts irgenwo reintun um es hinterher abzusuchen/abzufragen. (Zu viele "unnütz" abgesuchte Felder...)
Mit der "Kreis-Methode" ist z.B. automatisch das zuerst gefundene, auch das am nächsten liegende System.
Es mag dabei mehrere Systeme (in diesem Radius) geben aber keines ist näher...

gruß heinz

Benutzeravatar
GregorS
Beiträge: 2518
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Algorithmus für "geschlossene" Kreise

Beitrag von GregorS » 13.04.2018 20:07:57

heinz hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 19:57:23
GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 19:36:07
...In den Container tust Du nur die Sektoren bzw. Systeme, die Du gefunden hast.
Ich möchte eigentlich, wenn möglich, garnichts irgenwo reintun um es hinterher abzusuchen/abzufragen. (Zu viele "unnütz" abgesuchte Felder...)
Mannomann ... dann tu die gefundenen Sektoren/Systeme (also DIE, DIE DAS ENTHALTEN, WAS DU SUCHST) halt sonstwo rein. Hauptsache, Du musst nie-nie-niemals Container benutzen, was?

Tja, dann ...

Gruß

Gregor
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 20:17:00

GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 20:07:57
Mannomann ... dann tu die gefundenen Sektoren/Systeme (also DIE, DIE DAS ENTHALTEN, WAS DU SUCHST) halt sonstwo rein. Hauptsache, Du musst nie-nie-niemals Container benutzen, was?

Tja, dann ...
Was ist denn jetzt los?

Es geht nicht um Container sondern um Rechenaufwand.
Mit der von Dir vorgeschlagenen Methode (Flood-Fill) muss man sehr viele Sektoren berechnen, obwohl man das nächste System vlt. schon längst hat.

gruß heinz

Benutzeravatar
GregorS
Beiträge: 2518
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Algorithmus für "geschlossene" Kreise

Beitrag von GregorS » 13.04.2018 20:32:45

heinz hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 20:17:00
GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 20:07:57
Tja, dann ...
Was ist denn jetzt los?
Es geht nicht um Container sondern um Rechenaufwand.
Mit der von Dir vorgeschlagenen Methode (Flood-Fill) muss man sehr viele Sektoren berechnen, obwohl man das nächste System vlt. schon längst hat.
Also mal extra-langsam:

- Du „zeichnest“ einen Kreis mit r=bla
- Den Bereich innerhalb dieses Kreises „füllst“ Du mit dem Flood-Fill-Algorithmus
- Wenn Du dabei auf einen Sektor mit dem gesuchten Ding stößt, tust Du DIESEN UND SONST NICHTS in den Container. Wenn der Container dabei automatisch nach Entfernung sortiert, ist das erste Element darin DAS NÄCHSTE (im Sinne von NAH!)
- Wenn der Bereich innerhalb des Kreises fertig durchsucht wurde, entscheidest Du:
- Wenn nichts im Container ist, fängst Du wieder oben an mit r=bla+10 (oder bla+20, vielleicht gefällt Dir das besser ;-)
- Wenn etwas im Container ist, ist es das ERSTE ELEMENT IM CONTAINER

Hast Du's JETZT kapiert?

Gruß

Gregor

PS: Das Problem ist in meinen Augen gelöst. Ciao!
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

Benutzeravatar
bluestar
Beiträge: 2334
Registriert: 26.10.2004 11:16:34
Wohnort: Rhein-Main-Gebiet

Re: Algorithmus für "geschlossene" Kreise

Beitrag von bluestar » 13.04.2018 20:52:30

Kannst du mal deinen Code posten, dann kann ich dir die Stellen zeigen, wo die Fehlpixel entstehen.

Apropos Performance:
Du nimmst 1/4 Kreissegmente und lässt pro Segment einen Thread rechnen ;)

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 21:02:45

GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 20:32:45
Hast Du's JETZT kapiert?
Anscheinend nicht. Sorry.
GregorS hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 20:32:45
- Wenn der Bereich innerhalb des Kreises fertig durchsucht wurde, ...
Man kann also erst wissen welches der nächste ist wenn man alle Fundstellen innerhalb des gefüllten Bereiches ermittelt hat.
Um das zu umgehen bräuchte man einen Füll-Algo der in der Mitte beginnt und spiralförmig nach aussen "geht", damit man nicht alle berechnen muss.
Und genau das ist es doch was ich mit den Kreisen mache.

Die Idee mit dem Füllen ist toll aber sehr Rechenintensiv...

Werde mal nach Füllroutinen schauen, vlt. findet sich ja da was brauchbares.

gruß heinz

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 21:12:39

Hallo bluestar,
bluestar hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 20:52:30
Kannst du mal deinen Code posten, dann kann ich dir die Stellen zeigen, wo die Fehlpixel entstehen.
Das wäre extrem klasse!
NoPaste-Eintrag40262

Der Code stammt ursprünglich von https://de.wikipedia.org/wiki/Bresenham-Algorithmus.

gruß heinz

tobo
Beiträge: 1964
Registriert: 10.12.2008 10:51:41

Re: Algorithmus für "geschlossene" Kreise

Beitrag von tobo » 13.04.2018 22:30:26

Meine Vorstellung ist, dass du da so eine Art Kreisring absuchen musst. Oder anders ausgedrückt, eine Kreislinie virtuell mit einem dickeren (nach innen geneigten) Stift gezogen. Bei einem Punkt P(x,y) überprüfst du dann also nicht nur einen Pixel, sondern ein Quadrat von 4 Pixel (2x2). Das Quadrat ist dann in Abhängigkeit zum jeweiligen Quadranten zu legen. Beim mathematisch 1. Quadranten liegt also das Pixel oben rechts im Quadrat, im 4. Quadranten unten rechts. Beim Übergang von Pixel zu Pixel+1 kannst du dir die Koordinaten des Vorgängerpixels merken. Ändert aber natürlich nichts daran, dass zum Vorgängerkreisring mehr und doppelt gemachter Aufwand entsteht. Aber logischerweise sollte dadurch alles abgedeckt sein.

Benutzeravatar
heinz
Beiträge: 535
Registriert: 20.12.2007 01:43:49

Re: Algorithmus für "geschlossene" Kreise

Beitrag von heinz » 13.04.2018 22:44:50

Hallo tobo,

danke für die Anregung. Hatte schon eine ähnliche Idee.
Werde aber noch ein wenig weitersuchen denn bei meiner Suche bin ich hierauf gestossen:
https://de.wikipedia.org/wiki/Rasterung_von_Linien
Neben dem Absatz: Bidirektionale Rasterung ist ein Bild und darunter die Anmerkung:
Die hohlen Kreise geben die Pixel an, die eingefärbt werden, wenn bei d=0 das andere Pixel gewählt wird.
Es scheint also irgendwie zu gehen.

Bin aber heute scheinbar nicht mehr in der Lage es umzusetzen. :(
Werde morgen nochmal drangehen...

gruß heinz

tobo
Beiträge: 1964
Registriert: 10.12.2008 10:51:41

Re: Algorithmus für "geschlossene" Kreise

Beitrag von tobo » 13.04.2018 23:06:19

Ich denke, dass das eher nur eine Optimierung ist. Du berechnest nur noch die Hälfte der Punkte und spiegelst dann. Beim Kreis ist das ja noch sehr viel günstiger. Du musst nur 1/8 der Punkte auf der Kreislinie berechnen und spiegelst über alle 4 Achsenabschnitte, durch vertauschen der Vorzeichen. Trotzdem glaube ich nicht, dass du an der doppelten Strichstärke vorbeikommst!?

eggy
Beiträge: 3331
Registriert: 10.05.2008 11:23:50

Re: Algorithmus für "geschlossene" Kreise

Beitrag von eggy » 13.04.2018 23:48:18

tobo hat geschrieben: ↑ zum Beitrag ↑
13.04.2018 23:06:19
Trotzdem glaube ich nicht, dass du an der doppelten Strichstärke vorbeikommst!?
Doch kommt man, so zum Beispiel:

Jeder Pixel kann in einem 3x3 Pixel Raster betrachtet werden, in Abhängigkeit von den 4 Quadranten schaut man, ob in zwei Richtungen das Nachbarfeld belegt ist, ist das nicht der Fall zeichnet man einen weiteren Pixel, wo, das kann man aus der "Himmelsrichtung" ablesen:
Beispiel:
0x0 (123)
0x0 (456)
x00 (789)

Wir sind link überhalb des Mittelpunkts, daher betrachen wir hier nur links und unten vom Ausgangspixel: für den mittleren Pixel ist klar, dass der Nabarpixel entweder auf 4 oder 8 liegen sollte, und nicht auf 7, also wird entweder 4 oder 8 gesetzt. Damit ist dann die Linie zu 7 verbunden.
Als Nächstes macht man dann mit Pixel 7 weiter und schau sich die umliegen Pixel an. So Tastet man sich einmal im Kreis rum (ein Wechsel der Quadranten ergibt nen Wechsel der relevaten Nachbarpixel die betrachtet werden müssen)

Geht, allerdings nicht sonderlich effizient.

Antworten