Kleinster Kreis, der eine gegebene Menge von Punkten enthält
-
Hallo Leute,
ich suche einen Algorithmus für folgendes Problem:
Gegeben sind die x,y Koordinaten von vielen (ca. 100000) Punkten in einer Ebene. Gesucht ist der kleinste mögliche Kreis, so dass alle gegebenen Punkte innerhalb des Kreises liegen.
Es kann davon ausgegangen werden, dass alle gegebenen Punkte auf einem bestimmten Raster liegen, sozusagen die Pixel eines Bildes. Es sind aber nicht notwendigerweise alle Rasterpunkte gegeben, die innerhalb des Kreises liegen.
Gesucht sind die Koordinaten des Mittelpunktes und der Radius des Kreises, jeweils mit Sub-Pixel Genauigkeit.Gruß
Michael
-
Ich nehme mal an, man berechnet die konvexe Hülle und dann mit den Eckpunkten findet man recht leicht nen Kreis. Also so in etwa: http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/fakultaet/programmierpraktikum/2009_ss_aufgabenstellung.pdf
Gibt aber auch andere Verfahren, siehe zB. http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo42.php
-
Hallo Daniel,
danke für deine Hinweise, das hilft mir schon mal weiter.
Eine Frage habe ich noch:
Muss man zur Bestimmung der konvexen Hülle eine vollständige Triangulation durchführen, oder gibt es ein einfacheres Verfahren? Denn die Punkte, die innerhalb der Hülle liegen, die interessieren mich ja gar nicht.Gruß
Michael
-
Daniel@work schrieb:
Ich nehme mal an, man berechnet die konvexe Hülle und dann mit den Eckpunkten findet man recht leicht nen Kreis. Also so in etwa: http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/fakultaet/programmierpraktikum/2009_ss_aufgabenstellung.pdf
siehe dazu auch Graham Scan.
-
-
das problem hört auf den schönen namen "minimum enclosing disk" oder auch "smallest enclosing disk". Mit der konvexen Hülle hat das nur bedingt was zu tun.