Umkreis um mehrere Kreise berechnen

[ethrandil]

Hallo,
ich suche eine Möglichkeit um den Umkreis um mehrere Kreise mit unterschiedlichen Radien zu finden.

Ich habe als Eingabe: Mittelpunkte und Radien der Kreise
Ich suche: Den Mittelpunkt des Kreises, in den alle gegebenen Kreise reinpassen, mit minimalem Radius.

ich hab nix gefunden :(

- Eth

[Trap]

Der Umkreis von 2 Kreisen ist nicht schwer.

Gilt Umkreis(a,b,c)=Umkreis(Umkreis(a,b),c) (für alle a,b,c)? Dann wäre es gelöst...

[mithrandir]

Dere!

Bin zwar ein Laie, aber ich finde das nicht so schwierig (wenn ich mich nicht vertue).

Du hast die Koordinaten des Mittelpunktes eines jeden Kreises. Du erhöst jeweils x und y-Wert um den Radius. Den größten x und y-Wert aus allen Kreisen merkst du dir. Dasselbe machst du mit den kleinsten Werten (also Radius vom Mittelpunkt subtrahieren). Dann hast du schon einmal die Eckpunkte eines Rechtecks, in das alle Kreise reinpassen.

Und vom Rechteck kommt man dan ganz einfach auf den Kreis.

bye, Peter

[Neomi]

Der perfekte Lösung dazu (ich brauchte das für Punkte) habe ich auch nie gefunden, ich kann nur ein Näherungsverfahren anbieten.

1. Den Mittelpunkt (0.5 * (xMin + xMax), ...) finden.

2. Einen Radius errechnen und einen Kreis bilden, in dem alle anderen liegen.

3. Von jedem relevanten Kreis A aus (die inneren haben oft keinen Einfluß) den Kreis B bilden, in dem der gesuchte Kreis M seinen Mittelpunkt haben darf, so daß der jeweilige Kreis A noch drin liegt. Das ist der Mittelpunkt von A mit Radius M (der aus 2.) minus Radius A.

4. Die Schnittmenge (boolsches Und) der B-Kreise aus 3. bilden. Das läßt sich vereinfachen, indem du immer die Schnittpunkte von zwei B-Kreisen sammelst, die auch innerhalb aller anderen B-Kreise liegen.

5. Mit den gesammelten Schnittpunkten, die in allen B-Kreisen liegen bildest du den Mittelpunkt. Weiter bei 2. und so oft loopen, bis der Abstand der Schnittpunkte klein genug ist.

@mithrandir:
Das ist zwar ein simples Verfahren, liefert aber einen unnötig großen Umkreis. "EINEN" Kreis zu finden ist leicht, "DEN EINEN" (perfekten) Kreis zu finden ist das Problem.

[Trap]

Und vom Rechteck kommt man dan ganz einfach auf den Kreis.
Dummerweise ist deine Methode nicht idempotent(umkreis(x)=umkreis(umkreis(x))), womit sie sicher nicht den eindeutigen Umkreis berechnet. Umkreis = Kreis mit minimalem Radius der alle x enthält.

Umkreis für Punkte ist exakt lösbar in O( n ): http://www.personal.kent.edu/%7Ermuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

[mithrandir]

Dere!

Gut. Wieder was dazugelernt. Sagte ja, dass ich ein Laie bin (Mathe war immer eines der schwächsten Fächer bei mir ; - )

bye, Peter

[Neomi]

Umkreis für Punkte ist exakt lösbar in O( n ): http://www.personal.kent.edu/%7Ermuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Nach sowas hatte ich vor langem mal gesucht. Danke! :)

[DocEW]

Der auf der Seite angegebene Linearzeit-Algorithmus scheint aber nicht so ganz einfach zu sein...
Hier (http://www.charlesriver.com/visualcomputing/programs/MiniBall.cpp)findest du eine Implementation des "Minidisc"-Algorithmus von Emo Welzl. Der ist ziemlich einfach zu verstehen (z.B. hier (http://www.csl.sony.co.jp/person/nielsen/visualcomputing/visualcomputing-chapter7-colorlowres.pdf)beschrieben) und läuft auch in Linearzeit.
Wenn du Fragen hast, frag mich ruhig, ist eine schöne Prüfungsvorbereitung für Dienstag... :/

[Coda]

Der perfekte Lösung dazu (ich brauchte das für Punkte) habe ich auch nie gefundenAllg. ist der kleinste Kreis oder Kugel um ein Objekt recht schwer zu bestimmen. Bei der Kugel weiß ich nichtmal ob es einen Algorithmus gibt.

[DocEW]

Wobei dann noch zu klären wäre, ob "kleinster Kreis, in dem n Punkte liegen" so einfach auf "kleinster Kreis, in dem n Kreise liegen" zu transformieren ist... *grübel*