Hallo,
kurz beschriebn habe ich folgendes Problem. Ich habe eine Menge an zweidimensionalen Punkten und versuche verzweifelt den kleinsten Umkreis um diese Punkt zu legen. Das Ganze natürlich programmiertechnisch. Das Thema wurde hier schonmal angeschnitten unter /t/kleinsten-umkreis-berechnen/813773
Zum iterativen Verfahren kann ich sagen, dass auf jeden Fall ein Kreis gefunden wird. Allerdings kommt es dabei hin und wieder vor, dass die drei Punkte ein stumpfwinkliges Dreieck bilden und damit nicht den kleinstmöglichen Umkreis bilden können.
Interessant ist der Ansatz, wo zunächst der größte Abstand zwischen zwei Punkten der Menge gefunden wird. Der Mittelpunkt wird dann auf die halbierte Strecke gesetzt und der dritte Punkt über den größten Abtsand zu eben jenen Mittelpunkt ermittelt. Das habe ich schon probiert zu implementieren, erbrachte aber nicht unbedingt den erwünschten Erfolg. Muss dieses Verfahren theoretisch funktionieren?
Hat sonst jemand einen Hinweis, wo ich Informationen zur Lösung meines Problem herbekomme?
…eine Menge an zweidimensionalen Punkten und versuche verzweifelt
den kleinsten Umkreis um diese Punkt zu legen. Das Ganze
natürlich programmiertechnisch.
Welzl-Algorithmus. Das ist ein gewitztes randomisiertes Verfahren, das (nachweislich!) für jede Punktmenge die korrekte Lösung liefert.
Interessant ist der Ansatz, wo zunächst der größte Abstand
zwischen zwei Punkten der Menge gefunden wird. Der Mittelpunkt
wird dann auf die halbierte Strecke gesetzt und der dritte
Punkt über den größten Abtsand zu eben jenen Mittelpunkt
ermittelt.
Da kannst Du dran rumprobieren und -optimieren, bis Du schwarz wirst: Es wird Dir nicht gelingen, den Anteil gewisser „blöder Fälle“, bei denen die Methode versagt, auf Null zu senken.
Interessant ist der Ansatz, wo zunächst der größte Abstand
zwischen zwei Punkten der Menge gefunden wird. Der Mittelpunkt
wird dann auf die halbierte Strecke gesetzt und der dritte
Punkt über den größten Abtsand zu eben jenen Mittelpunkt
ermittelt. Das habe ich schon probiert zu implementieren,
erbrachte aber nicht unbedingt den erwünschten Erfolg. Muss
dieses Verfahren theoretisch funktionieren?
Hallo,
was heisst interessant, der Ansatz ist schlicht falsch. Du kannst daraus nur entnehmen, dass der Umkreis nicht kleiner sein kann. Zeichne einen weiteren Kreis um eine der beiden Extrempunkte: alle Punkte innerhalb dieses Kreises haben einen geringeren Abstand, würden also den gefundenen Umkreis nicht verändern - aber sie können ausserhalb des angeblichen Umkreises liegen.
Hallo,
kurz beschriebn habe ich folgendes Problem. Ich habe eine
Menge an zweidimensionalen Punkten und versuche verzweifelt
den kleinsten Umkreis um diese Punkt zu legen. Das Ganze
natürlich programmiertechnisch.
Hallo Stefan !
Ein sehr einfaches Verfahren um einen Kreis um alle Punkte zu finden ist folgendes.
Gegeben sind die Punkte
P_1(x_1|y_1),…,P_n(x_n|y_n).
Wähle als Mittelpunkt
M\left(\frac{1}{n}\sum\limits_{i=1}^n x_i\mid\frac{1}{n}\sum\limits_{i=1}^n y_i\right).
Wähle als Radius
r=\max\limits_i\ \ \overline{MP_i}.
Das ergibt einen Kreis der alle Punkte einschließt, das muss allerdings nicht der kleinste aller möglichen Kreise sein. Insbesondere ist das Verfahren schlecht bei Ausreißern, d.h. wenn viele Punkte nah beisammen liegen und einer weit draußen.
Der Mittelpunkt M ist der Punkt, der die Summe der Abstandsquadrate zu den Punkten P_i minimiert.
Gruß