Koordinatensystem + Kreis --> alle Koordis im Kreis ermittel

[yankee]

Hi @ll,

ich habe ein Koodinatensystem. Eine Koordinatenlänge entspricht 1 Längeneinheit (LE)
Irgendwo an einer zufälligen stelle im Koordinatensystem befindet sich der Mittelpunkt eines Kreises mit dem bekannten Radius von nLE.
Jetzt möchte ich alle Koordinaten auflisten, die innerhalb des Kreises liegen.

Ich habe da nicht so richtig 'ne Idee, wie ich das anstelle...
Könnt ihr mir helfen?

[xineohp]

moin,

als erste Einschränkung würde ich alle Punkte wegfallen lassen, die nicht im, den Kreis umgebenden, Quadrat liegen. Sprich man lässt zwei Schleifen(i,j) laufen, die eine(i) von mx-r bis mx+r und die zweiter(j) innerhalb der ersten von my-r bis my+r. (wobei mx/my den Mittelpunkt des Kreises und r den Radius des selben in LE angibt)

Innerhalb dieser Schleifen prüfst du dann noch ob der Abstand von i/j von mx/my größer als r LE ist, wenn ja, dann liegt der Punkt außerhalb, wenn nicht, dann innerhalb des Kreises. (frei nach Pythagoras: (i-mx)^2+(j-my)^2 <= r^2)


EDIT: Ich bin davon ausgegangen, dass der Kreismittelunkt auf einem Koordinaten Kreuz liegt, wenn nicht musst du halt jeweils auf den nächsten ganzzahligen Wert runden.

[alcaeus]

Hi yankee,

du könntest auch gleich alle Koordinaten auflisten, die diese Gleichung erfüllen:

Code:

(x-x0)²+(y-y0)² <= r²

Nun stellt sich aber die Frage, ob du für einige bekannte Koordinatenpaare festlegen musst, ob sie im Kreis sind oder ob du ALLE Koordinaten ausgeben müssen. Letzteres dürfte wohl aufgrund einiger mathematischer Regeln ("zwischen 2 verschiedenen reellen Zahlen x und y liegt immer mindestens eine reelle Zahl z, für die gilt z <> x <> y")

Greetz
alcaeus

[nailor]

such mal bei google. ich kiegs nicht mehr genau hin aber es gibt einen "optimierten angepassten bresenham code zum zeichnen von kreisen" oder in english wörter wie "heavily optimized bresenham circle drawing" das sind nicht die perfekten keywords, aber in die richtung. da gibts spieleentwickler, die (vornehmlich c++ mit assembler-kern) da sehr stark optimierte und seeeehr effektive algos zu entwickelt haben.