Minimaler Kreis um eine 2D-Punktmenge

Neue Frage »

oXmoX Auf diesen Beitrag antworten »
Minimaler Kreis um eine 2D-Punktmenge
Hallo!

Ich habe eine Menge von 2D-Punkten und möchte nun Position und Radius eines Kreises haben, der minimalen Flächeninhalt hat und alle Punkte enthält.

Gibt es eine algebraische Lösung für dieses Problem und wie sieht sie aus?
Gibt es sonst einen Algorithmus, der mir die Lösung liefert?

Bin dankbar für jeden Hinweis.

Gruß,
oXmoX
AD Auf diesen Beitrag antworten »

Hast du auch schon im Informatikerboard gefragt? Die wissen das vielleicht.

Ist jedenfalls kein einfaches Problem: Schon bei nur drei Punkten gibt es zwei wesentlich verschiedene Fälle zu beobachten:

a) Die drei Punkte bilden ein stumpfwinkliges Dreieck. In diesem Fall nimmt man als Kreis denjenigen mit der längsten Dreiecksseite als Durchmesser.

b) Die drei Punkte bilden ein spitz- oder rechtwinkliges Dreieck. In diesem Fall nimmt man als Kreis den Umkreis des Dreiecks.

Vielleicht gibt es darauf aufbauend irgendeinen Algorithmus...
oXmoX Auf diesen Beitrag antworten »

Ich schätze mal in meinem konkreten Fall gibt es eine ganz einfache Lösung. Die 8 2D-Punkte stammen nämlich aus der Projektion von 8 3D-Würfelecken ab. Der 3D-Würfel ist zuvor bekannt, also auch sein Mittelpunkt. Wenn ich zusätzlich zu den 8 Eckpunkten also auch seinen Mittelpunkt projeziere, dann habe ich damit einen Mittelpunkt für meinen 2D-Kreis (nicht exakt aber exakt genug). Jetzt brauche ich nurnoch den Radius. Den könnte ich in einer Schleife ermitteln, in der ich den maximalen Abstand des gefundenen Mittelpunktes zu den 8 Eckpunkten suche.

Irgendwelche Verbesserungsvorschläge? ...Am liebste wäre mir immernoch die Antwort auf meine oben gestellte Frage. Wichtig ist mir noch, dass das ganze einigermaßen echtzeitfähig sein muss.

...So langsam ist das Thema wirklich eher in der Informatik-Ecke angesiedelt Augenzwinkern


...die Frage ist eigentlich: Wie macht man eine perspektivische Projektion einer Kugel?

Ich kann irgendwie nur Punkte projezieren. unglücklich

edit. Doppelpost zusammengefügt, bitte benutze die edit-Funktion! (MSS)
jovi Auf diesen Beitrag antworten »

Endlich mal eine interessante Aufgabe Freude
Auf den ersten Blick habe ich schon vermutet, dass es dafür eine algebraische Lösung gibt, bin mir aber überhaupt nicht mehr sicher.
Also denke ich solltest du Arthurs Rat folgen und dafür einen geeigneten Algorithmus suchen. (Gebiet: Angewandte Rechnergestützte Geometrie)
Falls du nicht fündig wirst und dir das Problem wichtig genug ist, dann mach doch eine Preisfrage draus und gib deine Menge von 2D-Punkten an.
(ich hätte schon Ideen für einen Algo ...)
Dann käme mal etwas Leben hier ins Board Augenzwinkern
AD Auf diesen Beitrag antworten »

Zitat:
Original von jovi
(ich hätte schon Ideen für einen Algo ...)

Ich auch, aber mit der Effizienz bin ich noch sehr unzufrieden. Das muss besser gehen...
Tobias Auf diesen Beitrag antworten »

Ich hätte folgenden Vorschlag:


1.) Zuerst zieht man einen Rahmen um die Punkte. Dabei sind die Seiten des Rahmens parallel zur X- bzw Y-Achse (blauer Rahmen). Man sucht also diejenigen Punkte, die den größten/kleinsten X- bzw. Y-Wert haben. Aus dem Rechteck resultiert ein Mittelpukt (blauer Punkt).

2.) Nun zieht man analog einen Rahmen nur um 45° gedreht (grün) und ermittelt ebenfalls den Mittelpunkt (grüner Punkt).

3.) Verbinde den grünen und den blauen Mittelpunkt miteinander und wähle einen Kreismittelpunkt auf genau der Halbierung der Strecke. (roter Punkt).

4.) Suche vom roten Punkt aus denjenigen Punkt aus der Punktwolke, der am weitesten entfernt liegt. Die Entfernung gibt jetzt den Radius vor. (rote Linie).

5.) Mit Mittelpunkt und Radius hast du einen Kreis bestimmt.


Die Frage ist: Wie weit ist das Resultat dieser methode vom Optimum entfernt und welche Güte besitzt es gegenüber extremen Beispielen
 
 
AD Auf diesen Beitrag antworten »

Ohne jetzt irgendwie nach dem Algorithmus recherchiert zu haben, schreibe ich mal meine Gedanken hin:

1) Es interessieren nur die Punkte, die auf der Begrenzung der konvexen Hülle aller Punkte liegen. Sind diese Randpunkte innerhalb des Kreises, dann auch die gesamte konvexe Hülle und somit auch die restlichen Punkte.

2) Für den Kreis mit minimalen Durchmesser sehe ich zwei Möglichkeiten:

2a) Genau zwei der Punkte liegen auf dem Kreis. Dann müssen das zwei Punkte mit maximalen Abstand sein; diese bilden dann den Durchmesser des Kreises.

2b) Mindestens drei der Punkte liegen auf dem Kreis (bei "allgemeiner Lage" werden das genau drei sein), von denen es drei gibt, die ein nichtstumpfwinkliges Dreieck bilden.

Das Punktpaar mit dem maximalen Abstand (aus 2a) muss an diesem Dreieck übrigens nicht beteiligt sein: Dazu betrachte man ein gleichseitiges Dreieck mit Umkreis und einen vierten Punkt "fast" auf dem Ende desjenigen Durchmessers, dessen einer Randpunkt einer der Dreieckspunkte ist.
oXmoX Auf diesen Beitrag antworten »

Hey, Ihr habt eure Hausaufgaben echt gemacht Jungs! Freude

1000 Dank dafür! Aber ich bevorzuge immernoch meinen Vorschlag mit der Projektion. Konkret geht es nämlich um ein einfaches Kameramodell, bei dem der Raum in virtuelle Voxel unterteilt wird, die dann auf die Bildebene der Kamera projeziert werden. Die konvexe Hülle der Projezierten Eckpunkte ist dann die 2D-Silhouette des Voxels. Diese wird in meinem Programm durch einen Kreis angenähert. Dabei werden zudem noch Linsenverzerrungen berücksichtigt ...was die Sache mit der Kugelprojektion noch etwas komplizierter macht. Jedenfalls hab ich jetzt eine echtzeitfähige vorläufige Lösung gefunden (siehe oben).

Es sieht mir danach aus, dass es keine algebraische Lösung oder einen wirklich simplen Algorithmus dafür gibt.

...Also für mich braucht ihr eure Köpfe jetzt nicht mehr zu zerbrechen.
AD Auf diesen Beitrag antworten »

Ich hab das mal spaßeshalber programmiert (in C), was ich da im letzten Beitrag verzapft habe - natürlich für den allgemeinen Fall von n Punkten in der Ebene. Scheint ganz gut zu funktionieren.

1.Schritt: Berechnung der konvexen Hülle mit Aufwand . Ergebnis: Punkte, dabei ist .
Bei n zufällig in einen Kreis geworfenen Punkten scheint das m aber eher in der Größenordnung zu liegen. Fragt mich nicht, wieso - für mich wäre irgendwie plausibler gewesen. verwirrt

2.Schritt: Berechnung des Umfassungsdreiecks bzw. -durchmessers (s.o.) für ebendiese konvexe Hülle mit Aufwand .

Bei Interesse stelle ich den Quellcode mal hier rein. Wink
oXmoX Auf diesen Beitrag antworten »

Zitat:
Original von Arthur DentBei Interesse stelle ich den Quellcode mal hier rein. Wink

Nur zu! Den Service will ich mir nicht entgehen lassen. Insbesondere iteressiert mich die Berechnung der konvexen Hülle. Damit wollte ich mich demnächst nämlich auch mal befassen.
AD Auf diesen Beitrag antworten »

So, hat etwas gedauert - ich hab noch notdürftig die wichtigsten Kommentare zur Bestimmung der konvexen Hülle eingefügt. Wink
oXmoX Auf diesen Beitrag antworten »

Danke nocmal! Hat mir sehr geholfen.
AD Auf diesen Beitrag antworten »

Na hoffentlich waren nicht allzu viele Bugs drin. Die Routinen sind nahezu ungetestet!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »