Ich hab folgendes Problem:
Man hat auf einer Fläche (2D) verschiedene Punkte gegeben. Die Anzahl der Punkte ist variabel. Ich möchte nun den Mittelpunkt und den Radius des Kreises berechnen der alle Punkte gerade noch umschließt. Der Kreis soll der kleinste Kreis sein. Das ganze entspricht etwas dem Problem mit dem Umkreis des Dreiecks, doch leider hab ich hier nur eine beliebige anzahl von Punkten. Die Sache mit dem Schwerpunkt funktioniert auch nicht, da es sein kann, daß sehr viele Punkte auf einem Haufen liegen, und nur ein Punkt weit weg ist. Der Schwerpunkt wäre dann ja irgendwo in der nähe der vielen Punkte, der kleinste umfassende Kreis hat seinen Mittelpunkt aber genau zwischen den vielen Punkten und dem einzelnen Punkt.
Ich hab mir auch gedacht, ich könnte erst mal ausrechnen welche beiden Punkte am weitesten auseinander liegen. Der Mittelpunkt des umfassenden Kreises müsste dann genau zwischen den beiden Punkten liegen. Dies stimmt in etwa 90 Prozent der Fälle, es gibt jedoch ein paar wenige Kombinationen, wo das nicht mehr hinhaut, wie z. B. bei einem gleichseitigen Dreieck.
Wer kennt die Lösung?
mfg
Marco
Hallo Marco,
ich hätte einen Tipp (kann es leider nicht überprüfen, da ich gerade weder Zirkel noch Lineal zu Hand habe):
alle Punkte verbinden -> ergibt Polygon. Die Seiten über die Schnittpunkte so weit verlängern, bis sie sich wieder schneiden -> ergibt Polygon mit geringerer Seitenzahl. So weitermachen bis sich ein Dreieck ergibt. Von diesem Dreieck dann den Umkreismittelpunkt bestimmen. (Der Umkreisradius ist natürlich kleiner gleich dem Umkreisradius des Dreiecks, aber so hast du den Mittelpunkt.)
Hoffentlich stimmt’s 
Gruß,
Nina
Lösung ist richtig, aber unbrauchbar für mich
Diese Lösung ist nicht schlecht. Hat jedenfalls nach einigen Zeichnungen zum erfolg geführt. Doch leider gibt es ein Problem bei mir: Ich muß das am PC berechnen. Am Anfang hab ich nur die Koordinaten von den Punkten gegeben. Wenn man daraus jetzt das kleine Polygon in der Mitte berechnen möchte, dann ist das ganz schön anspruchsvoll. Die graphische Lösung des Problems funktioniert zwar, doch leider ist der PC nicht so intelligent wie ich. Was ich eigentlich bräuchte wäre eine mathematische Lösung des Problems, sozusagen eine Formel. Aber vielleicht findet sich ja eine Lösung. Eins ist jedenfalls klar: es gibt nur eine einzige Lösung, bzw. der Kreis ist eindeutig. Demnach ist das Problem lösbar. (Aber wie?)
mfg
Marco
Hi Marco,
suche das Punktepaar (A,B) mit dem größten Abstand zueinander. Halbiere die Stecke zwischen beiden. Dies ist Dein temporärer Mittelpunkt (T). Jetzt suche den übriggebliebenen Punkt ©, der den größten Abstand zu T hat. Ist der Abstand T:C größer als T:A, dann nutze das Dreieck ABC und finde den kleinsten Umkreis. Ist der Abstand kleiner, dann hat der Kreis dem Mittelpunkt T und den Radius T:C / 2
Ciao
Uwe
Du hast da ein nettes kleines Optimierungsproblem, welches auch noch nichtlinear ist. Du suchst einen Punkt, dessen maximaler Abstand zu einem der gegebenen Punkte minimal wird. D.h. die Loesung ist komplizierter als das Simplexverfahren. Ist aber ein konvexes Problem, so dass jeder Algorithmus mit schrittweisen Verbesserungen zum Ziel fuehrt.
Oder systematisch: Nimm Dir drei Punkte, baue den Kreis dazu, bestimme den Punkt mit groesstem Abstand zum Mittelpunkt, ersetze den zu ihm naechsten der drei Punkte durch ihn,… Dieses Verfahren konvergiert, da der Kreis immer groesser wird, ob es das Optimum wird, kann ich nicht garantieren.
Ciao Lutz
PS: wesentlich komplizierter ist das „Regenwurmproblem“ (Prof. Kummer): Welche Form minimaler Flaeche muss ein Hammer haben, um jeden Draht von 5cm Laenge zu ueberdecken (tierfreundliche Version).
n-Knick-Version: Gerader Draht mit n Knickstellen, gleiches Problem, schon n=3 ist unbekannt.
Die Lösung stimmt und hilft mir echt weiter. Danke. Einen kleinen Fehler hast Du allerdings noch.
Ist der Abstand kleiner, dann hat der Kreis dem
Mittelpunkt T und den Radius T:C / 2
Der Radius stimmt leider nicht ganz. Der Radius ist die Strecke A:T oder T:B.
Vielen Dank.
Jetzt muß ich nur noch berechnen wie man den Umkreises eines Dreiecks berechnet, aber das dürfte ja nicht allzu schwierig sein.
mfg
Marco
Hi Marco
Ist der Abstand kleiner, dann hat der Kreis dem
Mittelpunkt T und den Radius T:C / 2
Der Radius stimmt leider nicht ganz. Der Radius ist die
Strecke A:T oder T:B.
Peinlich!
Jetzt muß ich nur noch berechnen wie man den Umkreises eines
Dreiecks berechnet, aber das dürfte ja nicht allzu schwierig
sein.
Der Mittelpunkt ist der Schnittpunkt der Mittellote zweier Seiten.
Ciao
Uwe
Formel für Umkreis eines Dreiecks in C++
Hallo nochmal,
Falls es nun jemanden interessiert habe ich hier den Code in C, um den Umkreis eines Dreieckes zu berechnen. Gegeben sind die 3 Punkte des Dreiecks. Sonst nix.
void BerechneUmkreis(CPunkt* punkt, CKreis* kreis)
{
double xa = punkt[0].x;
double ya = punkt[0].y;
double xb = punkt[1].x;
double yb = punkt[1].y;
double xc = punkt[2].x;
double yc = punkt[2].y;
double my = (-xb*xc+xc*xc+xa*xb-xa*xc-yb*yc+yc*yc+ya*yb-ya*yc) /
(2.0*(-xc*yb+xc*ya+xa*yb+xb*yc-xa*yc-xb*ya));
kreis->mittelpunkt.x = 0.5*xa+0.5*xb-my*yb+my*ya;
kreis->mittelpunkt.y = 0.5*ya+0.5*yb+my*xb-my*xa;
kreis->radius = (kreis->mittelpunkt-punkt[0]).Betrag();
}