Kreisfindung

[berni86]

Hallo liebe Algorithmiker,

Ich suche einen Algorithmus, der mir anhand eine Liste von 2-dimensionalen Koordinaten (X und Y) berechnet, ob diese Koordinaten eine Kreis- bzw. Elipsenform bilden.

Der Wertebereich von x und y sind

0 <= x von <= 1024; 0 <= y <= 768

Ansich muss sich der x- und y-Wert in eine richtung bewegen (richtung 0 oder weg von 0) dann wieder umkehren bzw. wieder in die entgegengesetzte richtung wandern und den ausgangs x- bzw. y wert treffen. oder?

[flashpixx]

Berechne die Brennpunkte, bei einem Kreis fallen beide Brennpunkte in einem Punkt zusammen, bei einer Ellipse existieren zwei unterschiedliche

[berni86]

soweit ich das richtig verstanden habe, kann ich dann aber nur unterscheiden, ob es sich um einen kreis oder um eine ellipse handelt.

ich will aber erstmal erkennen, ob die verschiedenen koordinaten einen kreisförmiges gebilde bilden.

als programmierer geschrieben

boolean = isCircle(Liste aus Koordinaten)

[Bubble]

Wenn "sehr viele" oder geeignet liegende Punkte vorhanden sind: Mittelpunkt und Halbachsen bestimmen, dann testen ob alle Punkte (gegebenenfalls mit etwas Tolleranz) die Ellipsengleichung erfüllen.

Wenn sich die Halbachsen nicht zuverlässig (innerhalb einer akzeptablen Tolleranz) direkt durch Suchen/Sortieren der Punktliste bestimmen lassen, sei es durch zu wenige oder schlecht liegende Punkte, dann musst Du untersuchen, ob sich Halbachsen finden lassen, mit denen alle Punkte die Ellipsengleichung erfüllen.

[Bubble]

Berechne die Brennpunkte, bei einem Kreis fallen beide Brennpunkte in einem Punkt zusammen, bei einer Ellipse existieren zwei unterschiedliche

Dann kann er aber noch immer nicht sagen, ob die Punkte eine, zwei oder noch mehr Kreise beschreiben, die z.B. nur zufällig den gleichen Mittelpunkt haben.

[berni86]

ja, ich habe sehr viele Punkte. Meistens mit einem abstand von ca 1-5 pixeln.

Daher würde sich vllt deine (bubble) methode anbieten.

kannst du vllt näher erklären, was du mit mittelpunkt (zwischen welchen punkten) und halbachsen meinst?

ich glaube ich habe eine ahnung was du meinst, aber nähere erläuterungen würde helfen.

EDIT: wichtig ist mir eigentlich nur, dass sich die "linie aus punkten" an irgendeiner stelle wieder treffen muss. die umschlossene fläche muss ich haben. Anschließen muss ich durch einen algorithmus testen können, ob sich testpunkte innerhalb dieser fläche befinden

Bearbeitet 14. September 2010 von berni86

[Bubble]

Der Mittelpunkt ist halt der Mittelpunkt. Die Halbachsen sind die Große und die Kleine: Der jeweils größte bzw. kleinste Abstand eines auf der Ellipse liegenden Punktes vom Mittelpunkt. Beide stehen senkrecht aufeinader. Dies ist für die Ellipsengleichung bedeutsam.

So, nun hast Du aber die Fragestellung grob verändert: Du willst also jetzt wissen, ob Punkte innerlab eines durch eine Koordinatenliste definierten geschlossenen Polygonzugs liegen?

[berni86]

exakt. aber das ist dann der 2. schritt.

erstmal muss ich wissen ob die Koordinatenliste eine bestimmte fläche aufspannt.

Die Form ist dabei variabel. Es kann sich im extremfall um einen Kreis oder auch einem Drei- oder Viereck handeln

[Bubble]

erstmal muss ich wissen ob die Koordinatenliste eine bestimmte fläche aufspannt.

Das ist in gewissen Grenzen eine Definitionsfrage. Du musst genauer darlegen, was akzeptable Flächen sind, was nicht und Dir dann Kriterien zum Überprüfen überlegen.

[flashpixx]

Um zu ermitteln, wie "gut" das Gebilde ist, was Du untersuchen willst, berechne den SSE (sum of squared error). Stell die Gleichung der Form auf, die untersuchen willst also z.B. Kreisgleichung und berechne den quadratischen Fehler der Gleichung zu den Punkten. Das Ergebnis gibt Dir eine Information darüber, wie gut die Punkte dem Kreis gleichen oder nicht.

[berni86]

Um zu ermitteln, wie "gut" das Gebilde ist, was Du untersuchen willst, berechne den SSE (sum of squared error). Stell die Gleichung der Form auf, die untersuchen willst also z.B. Kreisgleichung und berechne den quadratischen Fehler der Gleichung zu den Punkten. Das Ergebnis gibt Dir eine Information darüber, wie gut die Punkte dem Kreis gleichen oder nicht.

ja... das wäre gut, wenn ich nur bestimmte formen, wie in deinem fall einen perfekten kreis, zulassen wollen würden. Bei deinem lösungsansatz wird vorausgesetzt, dass ich nur eine bestimmte form zulassen will. das ist bei mir aber nicht der fall

[flashpixx]

ja... das wäre gut, wenn ich nur bestimmte formen, wie in deinem fall einen perfekten kreis, zulassen wollen würden.

Du musst irgendein Charakteristikum haben, das Dir einen Rückschluss auf die Form zulässt. Sonst macht es keinen Sinn. Entweder Du hast Punkte und berechnest, wenn sie einen Kreis / Ellipse ergeben, die Brennpunkte. Oder im zweiten Fall berechnest Du die Ähnlichkeit von dem optimalen Objekt und triffst darüber eine Aussage.

Aus Deinen Postings geht nicht wirklich hervor was Du für ein Problem hast.