umkreis von unregelmäßigen n-ecken < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:25 Di 13.07.2004 | | Autor: | angela |
hallo MatheRaum
für die bearbeitung eines architekturentwurfes möchte ich den kleinstmöglichen umkreis eines unregelmäßigen n-ecks bestimmen
weiß aber nicht wie
die koordinaten der eckpunkte sind bekannt...
danke vorab für die hilfe
angela
ich habe diese frage in keinem weiteren forum gestellt.
|
|
| |
|
Hallo angela,
> für die bearbeitung eines architekturentwurfes möchte ich
> den kleinstmöglichen umkreis eines unregelmäßigen n-ecks
> bestimmen
weiß aber nicht wie
die koordinaten der eckpunkte
> sind bekannt...
So wie ich das verstehe, hast du also n Punkte in der Ebene gegeben, und suchst den kleinsten Kreis, der diese Punkte enthält.
Mindestens drei der Punkte müssen dann auf diesem kleinsten Kreis liegen, denn:
1. Liegt kein Punkt auf dem Kreis, dann kann man einfach seinen Radius so lange verringern, bis mindestens ein Punkt drauf liegt.
2. Liegen nur 1 oder 2 Punkte auf dem Kreis, dann kann man den Kreis bei kleiner werdendem Radius ein wenig verschieben, bis ein weiterer Punkt auf dem Kreis liegt.
Eine - brutale - Möglichkeit ist, einfach alle Kreise durch je drei Punkte zu bestimmen, die wegzuwerfen, die nicht alle Punkte enthalten, und von den verbleibenden den mit kleinstem Radius zu nehmen. (Dies nennt man dann eine "brute force"-Methode.) Sowohl für die Bestimmung dieser Kreise als auch für die Bestimmung, ob ein Punkt im Kreis liegt, gibt es Formeln.
Je nachdem, wie groß n ist, kann das vielleicht schon ausreichen, aber bestimmt gibt es noch einen geschickteren Weg als diesen.
Wenn ich mir meine Herleitung, dass der Minimalkreis drei Punkte enthält, so aussehe, dann könnte man daraus doch vielleicht einen Algorithmus entwickeln, oder? Ich geb mal meine Idee (ungetestet!):
1. Bestimme irgendeinen Kreis, der alle Punkte enthält. (Geht z.B., indem man irgendeinen der Punkte wählt, und den größten Abstand zu den anderen Punkten als Radius verwendet. Damit kann man den folgenden Punkt 2. überspringen.)
2. Verkleinere den Radius soweit, dass mindestens ein Punkt auf dem Kreis liegt. (Geht z.B., indem man alle Abstände der Punkte zum Kreismittelpunkt bestimmt, und den größten nimmt.)
Ab hier wird's formelmäßig etwas komplizierter, füchte ich.
3. Wenn genau ein Punkt auf dem Kreis liegt, verschiebe den Mittelpunkt in Richtung dieses Punktes und verkleinere den Radius so, dass der Punkt immer noch auf dem Kreis liegt, so lange, bis ein weiterer Punkt auf dem Kreis liegt. (Da müsste man für jeden anderen Punkt ausrechnen, wie der Radius sein muss, damit er auf dem Kreis liegt, und dann den mit größtem Radius nehmen.)
4. Wenn genau zwei Punkte auf dem Kreis liegen, dann gibt es zwei Möglichkeiten (siehe Stefans Reaktion auf diesen Beitrag):
4a. Der Mittelpunkt des Kreises liegt auf der Verbindungsstrecke der beiden Punkte (nämlich genau in der Mitte), dann ist der kleinste Kreis gefunden.
4b. Der Mittelpunkt des Kreises liegt nicht auf der Verbindungsstrecke der beiden Punkte, dann gehen wir so vor: Verschiebe den Mittelpunkt senkrecht zur Verbindungsgerade dieser Punkte (also quasi in Richtung "mitten durch die beiden Punkte"), und reduziere den Radius so, dass die beiden Punkte immer noch auf dem Kreis liegen, so lange, bis ein weiterer Punkt auf dem Kreis liegt oder der Mittelpunkt auf der Verbindungsstrecke der beiden Punkte angekommen ist. (Sollte vom Ansatz wie 3. funktionieren, nur dass die Formel anders wird.)
5. Wenn mindestens drei Punkte auf dem Kreis liegen, sind wir fertig und haben unseren kleinsten Kreis gefunden.
Der Aufwand dieses Algorithmus - wenn er denn funktioniert - ist O(n), im Gegensatz zu [mm] O(n^3) [/mm] für meine erste Idee.
Versteht jemand meine Idee, und kann ggf. die Formeln für 3. und 4. nachreichen?
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:32 Mi 14.07.2004 | | Autor: | Stefan |
Lieber SirJective!
> 2. Liegen nur 1 oder 2 Punkte auf dem Kreis, dann kann man
> den Kreis bei kleiner werdendem Radius ein wenig
> verschieben, bis ein weiterer Punkt auf dem Kreis liegt.
Bist du dir da sicher? Das sehe ich nicht so ganz ein. (Ich sollte allerdings dazu sagen, dass ich eine Null in Geometrie bin, insofern heißt das gar nichts. Aber ich möchte es wenigstens verstehen.  ) Insbesondere im Anblick des von mir gesetzten Links und meiner bescheidenen Anschaungsfähigkeit kann ich mir Situationen vorstellen, wo nur 2 Punkte auf dem (kleinsten!) Kreis liegen (und der Mittelpunkt des Kreises dann auf der Mitte der Verbindungsstrecke, logischerweise). "Kleinster" Kreis im Sinne von "kleinster Radius", oder?
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:46 Mi 14.07.2004 | | Autor: | SirJective |
Hallo Stefan,
> Insbesondere im
> Anblick des von mir gesetzten Links und meiner bescheidenen
> Anschaungsfähigkeit kann ich mir Situationen vorstellen, wo
> nur 2 Punkte auf dem (kleinsten!) Kreis liegen (und der
> Mittelpunkt des Kreises dann auf der Mitte der
> Verbindungsstrecke, logischerweise). "Kleinster" Kreis im
> Sinne von "kleinster Radius", oder?
Ja, du hast völlig recht!
Ich dachte nicht an den Fall, dass der Mittelpunkt des Kreises bereits mittig zwischen den beiden Randpunkten liegt. In dem Fall ist natürlich nichts mehr zu verkleinern, und der minimale Kreis enthält nur zwei Punkte.
Dies ist also ein abzugrenzender Sonderfall.
Das Beispiel mit 2 Punkten legt den schon nahe, ebenso wie ein stumpfwinkliges Dreieck. Ich werde meine Antwort entsprechend korrigieren (aber deutlich sichtbar  ).
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:56 Mi 14.07.2004 | | Autor: | SirJective |
Hallo Stefan,
die im Link gegebene Lösungsstrategie entspricht meiner ersten Idee, bis auf den Unterschied, dass ich übersehen habe, dass der kleinste Kreis auch durch 2 Punkte bestimmt sein kann, die auf einem gemeinsamen Durchmesser liegen. Diese Kreise müssen zusätzlich berechnet werden.
Ich denke, dass die nicht nur einfacher zu berechnen sind, sondern dass sogar gilt:
Falls es einen solchen gibt, der alle Punkte enthält, dann ist der kleinste von ihnen bereits die Lösung.
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:59 Mi 14.07.2004 | | Autor: | Stefan |
Lieber SirJective!
> die im Link gegebene Lösungsstrategie entspricht meiner
> ersten Idee, bis auf den Unterschied, dass ich übersehen
> habe, dass der kleinste Kreis auch durch 2 Punkte bestimmt
> sein kann, die auf einem gemeinsamen Durchmesser liegen.
> Diese Kreise müssen zusätzlich berechnet werden.
Ja, das sehe ich genauso. Ich meinte ja auch schon, dass es deiner Idee im Wesentlichen entspricht (und das "Unwesentliche" sind halt die Zweipunktkreise).
> Ich denke, dass die nicht nur einfacher zu berechnen sind,
> sondern dass sogar gilt:
> Falls es einen solchen gibt, der alle Punkte enthält, dann
> ist der kleinste von ihnen bereits die Lösung.
Das hatte ich mir auch schon überlegt und ist intuitiv klar. Kannst du das beweisen? (Mir fehlt die Zeit, ich muss noch einen Kurs für morgen vorbereiten ![[wein]](/images/smileys/wein.gif "[wein]") , der Beweis würde mich aber interessieren.)
Liebe Grüße
Stefan
|
|
|
|
![[]](/images/popup.gif){kind=small}
Planung eines Feuerwehrhauses