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

[heinz]

Nochmal eine Grafik zum verdeutlichen:

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

[GregorS]

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

[tobo]

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

[heinz]

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.

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

Nein, ich schau gleich mal rein. Danke...

gruß heinz

[heinz]

...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

[GregorS]

...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

[heinz]

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

[GregorS]

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!

[bluestar]

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

[heinz]

Hast Du's JETZT kapiert?

Anscheinend nicht. Sorry.

- 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

[heinz]

Hallo bluestar,

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

Das wäre extrem klasse!
40262

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

gruß heinz

[tobo]

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.

[heinz]

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]

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]

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.

[tobo]

Entweder verstehe ich das jetzt nicht richtig oder du meinst was anderes. Das Problem ist ja nicht, dass man so einen Kreis (1/8-Kreis) in der dünnsten Strichstärke mit dem Radius r berechnen kann, sondern das beim folgenden Berechnen von r+1, zwischen den Kreisen mit r und r+1, Pixel sind, die von keinem der beiden Kreise abgedeckt sind.
app.php/gallery/image/1723
Das halte ich eigentlich auch für logisch, da ja immer eine "Mehrheitsentscheidung" pro Pixel getroffen wird und diese Entscheidung, mit wachsendem Radius, nicht konstant nach außen mitwächst. Möglicherweise!? Vielleicht verstehe ich aber auch einfach nur nicht was du meinst, eggy.

[heinz]

Hallo nochmal,

ich hatte gestern Nacht im Bett noch eine Idee, die zu funktionieren scheint.
40264
Werde es jetzt erst mal so verwenden.

Vielen Dank an alle für Eure Hilfe.

gruß heinz