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

[heinz]

Hallo mal wieder,

ich bin auf der Suche nach einem Algorithmus, der "geschlossene" Kreise "liefert".

Ein Bild sagt mehr als tausend Worte:

Der linke Kreis ist das was ich im Moment habe (Bresenham), der rechte Kreis ist was ich gerne hätte.

Kennt jemand von Euch einen Algo. der das kann?

Viele Grüße,
heinz

[bluestar]

Bresenham

Wie wäre es denn, wenn du den Algo von Bresenham einfach an deine Bedürfnisse anpasst?

[tobo]

Du kannst mal schauen, ob du hier fündig wirst:
https://de.wikipedia.org/wiki/Rasterung_von_Kreisen

[heinz]

Wie wäre es denn, wenn du den Algo von Bresenham einfach an deine Bedürfnisse anpasst?

Danke für die schnelle Antwort.
Bin leider nicht so der Mathe-Freak.

Habe schon überlegt bei jedem gesetzten Pixel die umliegenden auch zu setzen.
Das würde allerdings zu vielen doppelt gezeichneten Pixeln führen, was ich gerne
vermeiden würde.

Der eigentliche Zweck ist auch nicht einen Kreis zu zeichnen sondern an den betreffenden
Stellen in einer sehr großen Karte bestimmte "Dinge" zu finden.
(Hoffe man versteht einigermassen was ich meine...)

gruß heinz

[eggy]

Erklär mal was genau das Ziel ist, ich geh mal davon aus, dass Du mit Distanzen evtl besser beraten bist...

[heinz]

https://de.wikipedia.org/wiki/Rasterung_von_Kreisen

Danke für den Link.
Den Grafiken auf der rechten Seite nach zu urteilen sind die Kreise dort aber auch nicht geschlossen.
Werde die Algos aber trotzdem mal testen.

gruß heinz

[heinz]

Erklär mal was genau das Ziel ist,...

Ich versuch es mal:
Es existiert eine große zweidimensionale Karte (Kantenlänge 65536 Felder)
Jetzt möchte ich von einem beliebigen Punkt aus mit einem wachsenden Radius
das umgebende Gebiet nach "bestimmten Dingen" absuchen um z.B. den am nächsten liegenden
Fundort zu bestimmen oä.
Mit dem bisherigen Algo. habe ich das Problem, dass bestimmte Felder nicht getestet werden.

gruß heinz

Nachtrag:
Die Karte ist auch nicht im Speicher präsent (da zu groß).
Jedes Feld wird per randomseed zur Laufzeit errechnet. Weshalb auch so wenig wie möglich doppelt
berechnet werden sollen.

[tobo]

Mit Feld ist hier offensichtlich nicht Pixel gemeint, oder? Denn dann wäre das ja z.B. nur 256x256 groß und das wäre nun wahrlich nicht riesig!? Was ist also ein Feld und aus was besteht es? Der geringste Abstand ist die Quadratwurzel der Summe der quadrierten x/y-Abstand-Deltas zu einem Mittel- oder Randpunkt dieser bestimmten Dinge. Du musst halt erklären, was das Erkennungsmerkmal dieser bestimmten Dinge ist...

EDIT: Kantenlänge 65536! Das relativiert das dann schon wieder...

[eggy]

https://de.wikipedia.org/wiki/Euklidischer_Abstand
https://de.wikipedia.org/wiki/Polarkoor ... oordinaten

Ich würd wahrscheinlich so vorgehen, erstmal den Bereich zu bestimmen, den ich nicht testen muss, d.h. alles ausserhalb eines Suchkorridors, der durch den Radius vorgegeben ist, ausschliessen und dann anhand der Formel r=sqrt(x^2 + y^2) den Abstand der Punkte zum Kreismittelpunkt berechnen, ist abs(r) größer als der Radius, liegt der Punkt ausserhalb Deines Suchkreises.

Aber garantiert gibts was effizienteres...

[heinz]

Mit Feld ist hier offensichtlich nicht Pixel gemeint, oder?

Ob Feld oder Pixel ist meiner Meinung nach egal. Oder sehe ich das falsch?
Stell Dir einfach eine Bilddatei vor mit 65536 mal 65536 Pixel oder eben ein Array
mit 65536 mal 65536 Feldern.

Ja, ich weiss, mit erklären hab ich es nicht so... Sorry...

gruß heinz

[heinz]

...erstmal den Bereich zu bestimmen, den ich nicht testen muss, d.h. alles ausserhalb eines Suchkorridors, der durch den Radius vorgegeben ist, ausschliessen

Diesen Bereich kenne ich aber vorher nicht.
Als Beispiel:
Ich suchen den am nächsten liegenden Fundort.
Dann beginne ich mit dem Radius von 1 und suche die umgebenden Felder ab.
Finde ich nichts, wiederhole ich die Suche mit Radius 2 usw.

gruß heinz

[eggy]

Kennst Du Deine Fundorte schon, und sind es "wenig genug"?
Dann ist es vielleicht einfacher die Distanz all Deiner Fundstellen zu berechnen, und dann alle Ergebnisse der Größe nach sortieren und die ersten x, die einen Abstand kleiner als r haben zurückzugegeben.

(Für mich hört sich das Ganze nach OSM-Daten an... liegen die Daten evtl in nem Postgres? Dann: die Geoerweiterungen solltenTM dazu bereits Funktionen haben)

[tobo]

Ja, mit der Größe habe ich mich verlesen. Aber was ich grundsätzlich sagen wollte: Solange du nicht genauer sagst, was du suchst, kann dir niemand sagen, wie du es findest. Da ist die Entfernung zum Nichtfund erstmal sekundär. Du weißt doch offensichtlich, was du suchst - das muss sich doch irgendwie beschreiben lassen!?

[GregorS]

Der Vorschlag mit dem Anpassen ist gut. Das war auch mein erster Gedanke.

Zum Verständnis: Das Problem mit dem Original-Algorithmus ist, dass es bei ihm im Bereich von 45° (und den entsprechenden Winkeln) zu Moiree-Mustern von nicht gesetzten Pixeln kommt, wenn man den Algorithmus in „1-Pixel-Schritten“ anwendet. Wobei die nicht gesetzten Pixel in Heinz' Fall nicht durchsuchten „Sektoren“ der Originalkarte entsprechen.

Den Bresenham-Algorithmus anzupassen wäre nicht sonderlich schwer, aber das „neue“ Problem mit einem angepassten Bresenham-Kreis ist, dass es viele doppelt gezeichnete Pixel gibt – in Heinz' Fall sind das doppelt behandelte Karten-Ausschnitte.

Gruß

Gregor

[heinz]

Kennst Du Deine Fundorte schon, und sind es "wenig genug"?

Nein leider nicht. Wie bereits oben erwähnt, ist die gesamte Karte nicht im Speicher oder auf Platte vorhanden
und deren Inhalt unbekannt.
Wenn ich den Inhalt eines Feldes wissen möchte, muss ich ihn erst mittels rand() berechnen.
Ich habe mal testweise die gesamte Karte (4294967296 Felder) durchsuchen lassen und bin auf ca. 21000000 Fundstellen gestossen.
(Hat fast 3 Stunden gedauert...)

gruß heinz

[heinz]

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

[GregorS]

'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

[MSfree]

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?

[GregorS]

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.

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

Das ist allerdings ein guter Punkt.

Gruß

Gregor

[heinz]

'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

[GregorS]

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

[heinz]

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

[heinz]

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

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

[heinz]

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

[heinz]

Oh mann, was hab ich angerichtet...

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

gruß heinz