3 Punkte in einem Kreis

Neue Frage »

Frauke8 Auf diesen Beitrag antworten »
3 Punkte in einem Kreis
Meine Frage:
Ich arbeite momentan an einem Computerspiel. Dabei muss ich unter anderem überprüfen, ob 3 gegebene Punkte in einen Kreis mit einem bestimmten Radius passen. Derzeit gehe ich per Brute Force über einen Haufen von Mittelpunkten und überprüfe jeweils, ob die Punktabstände zwischen Kreismitte und Punkten kleinergleich dem Radius sind. Jedoch ist das nicht gerade genau und obendrein rechenintensiv. Gibt es da einen einfacheren Weg das Problem anzugehen?

Meine Ideen:
.
HAL 9000 Auf diesen Beitrag antworten »

Es gibt grundsätzlich zwei Fälle:

a) Die drei Punkte bilden ein spitz- oder rechtwinkliges Dreieck. Dann ist der Umkreis der kleinste Kreis, der die drei Punkte enthält.

b) Die drei Punkte bilden ein stumpfwinkliges Dreieck. Dann ist der Kreis mit der längsten Seite als Durchmesser der kleinste Kreis, der die drei Punkte enthält.

Ob a) oder b) vorliegt, lässt sich anhand der drei Seitenlängen leicht feststellen: Sei o.B.d.A. die längste der drei Seiten, dann bedeutet Fall a) mit Kreisradius , und entsprechend Fall b) mit Kreisradius .
Ulrich Ruhnau Auf diesen Beitrag antworten »
RE: 3 Punkte in einem Kreis
Zitat:
Original von Frauke8
Meine Frage:
... Dabei muss ich unter anderem überprüfen, ob 3 gegebene Punkte in einen Kreis mit einem bestimmten Radius passen. ... Gibt es da einen einfacheren Weg das Problem anzugehen?
.

Es gibt sogar eine lineare Methode. Sie bezieht sich auf das Lösen einer Matizengleichung. Angenommen die drei Punkte liegen auf einem Kreis mit Radius und Mittelpunkt dann gilt:



Das muß man erst einmal ausmultiplizieren.



Weil es schon spät ist, mache ich morgen weiter.
Ulrich Ruhnau Auf diesen Beitrag antworten »
RE: 3 Punkte in einem Kreis


Einmal umsortieren:



Dies in die Matrixform pressen:



Das führt auf ein Produkt, bei dem der linke Vektor und die Matrix bekannt sind und man nur nach dem rechten Vektor auflösen muß.



Für letzteres kann man die Cramersche- und die Sarrussche Regel einsetzen, um das ganze zu programmieren. Oder man besorgt sich eine Software zum Lösen linearer Gleichungssysteme.

Ein Nachteil fällt mir im Nachhinein auf. Die Punkte sollten nach Möglichkeit auf dem Kreis liegen. Das Verfahren, das sich normalerweise auf n Punkte bezieht, funktioniert aber auch, wenn diese Punkte nur ungefähr auf einem Kreis liegen. Bei drei Punkten jedoch, die ein Dreieck mit einem stumpfen Winkel aufspannen, würde ich von dem beschriebenen Verfahren abweichen und den Kreis genau zwischen jene beiden Punkte legen, die am weitesten voneinander entfernt sind. Dann liegt der dritte Punkt nach dem Satz des Thales in diesem Kreis, womit die Aufgabe gelöst ist.

Gib doch mal ein paar Punkte vor, damit ich mein bereits vorhandenes Programm darauf los lassen kann!
Gualtiero Auf diesen Beitrag antworten »

Da von Frauke8 anscheinend nichts mehr kommt, springe ich mal als Datenlieferant ein.

Beispiele für drei Punkte mit zufälliger Lage.
Es geht hier ja nur um mögliche Konstellationen, daher habe ich die zwei Punkte A und B gleich belassen; Punkt C ändert sich, sodass sich jeweils ein eigener Fall ergibt.

A (3 11), B (6 2 )

Fall 1: A, B, C (5 5)

Fall2: A, B, C (9 2)

Fall3: A, B, C (6 10)

Fall4: A, B, C (9 8)

Fall5: A, B, C (9 11)

Fall6: A, B, C (11 13 )
werner Auf diesen Beitrag antworten »

nach dem schönen Vorschlag von HAL (inclusive der kleinen Bosheit von Gualtiero) smile
 
 
HAL 9000 Auf diesen Beitrag antworten »

Du solltest mal die Berechnungsformel für die Seitenlängen a,b in deinem Sheet überprüfen: Da stehen nämlich durch die Bank falsche Werte. unglücklich
Ulrich Ruhnau Auf diesen Beitrag antworten »

Zitat:
Original von Gualtiero
A (3 11), B (6 2 )

Fall 1: A, B, C (5 5)

Hier ist die Matrix singulär, sodaß nur meine zweite Methode zu einem richtigen Ergebnis führt.
[attach]55643[/attach]
Zitat:

Fall2: A, B, C (9 2)

Im zweiten Fall ist der rote Kreis kleiner als der blaue. Man finde den roten Kreis, indem man zwischen die beiden Punkte, die am weitesten voneinander entfernt liegen, den kleinstmöglichen Kreis legt, der diese Punkte berührt. Der Mittelpunkt dieses Kreises liegt in der Mitte der beiden Punkte. Der blaue Kreis wird über die Matrizenmethode bestimmt und hat die Eigenschaft, daß Gualtieros schwarze Punkte nur auf ihm und nicht in ihm liegen. Daher ist er stets größer als der rote Kreis.
[attach]55644[/attach]
Zitat:

Fall3: A, B, C (6 10)

Hier das gleiche wie im Fall 2. Den roten Kreis würde ich auch hier bevorzugen, weil er kleiner ist.
[attach]55645[/attach]
Zitat:

Fall4: A, B, C (9 8)

Beide Kreise liegen übereinander. Es ist hier also egal, welche Methode man wählt.
[attach]55646[/attach]
Zitat:

Fall5: A, B, C (9 11)

Hier erfüllt nur der blaue Kreis die Aufgabe, weil ein schwarzer Punkt außerhalb vom roten Kreis liegt. Also lohnt sich die Matrizenmethode, mit der der blaue Kreis in Durchmesser und Position berechnet wurde. Es ist der kleinstmögliche Kreis, der alle Punkte einschließt.
[attach]55647[/attach]
Zitat:

Fall6: A, B, C (11 13 )
Ulrich Ruhnau Auf diesen Beitrag antworten »

Zitat:
Original von Gualtiero
Da von Frauke8 anscheinend nichts mehr kommt, springe ich mal als Datenlieferant ein.
A (3 11), B (6 2 )

Fall6: A, B, C (11 13 )

Auch hier muß man den blauen Kreis nehmen, der der Matrizenmethode entspricht, weil der rote Kreis nicht alle Punkte umschließt.
[attach]55648[/attach]
Final gesprochen nehme man zuerst die Methode vom roten Kreis und schaue ob dieser die drei Punkte umschließt. Wenn das nicht der Fall ist, dann bilde man einen neuen Kreis nach der Matrizenmethode. Dieser erfüllt dann die Aufgabe mit Sicherheit.
HAL 9000 Auf diesen Beitrag antworten »

Ein kleines Python-Script zum Problem, speziell auch angewandt auf die Werte von Gualtiero:

[attach]55655[/attach]

EDIT: Hab es noch ein bisschen "optimiert". Augenzwinkern
werner Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Du solltest mal die Berechnungsformel für die Seitenlängen a,b in deinem Sheet überprüfen: Da stehen nämlich durch die Bank falsche Werte. unglücklich

echt?
da scheinen mir die Indizes durcheinander gekommen zu sein.
naja das Alter
Gualtiero Auf diesen Beitrag antworten »

@riwe
Diese Maße sollten stimmen, die hat mein CAD-System erstellt.

[attach]55657[/attach]

Beim ersten Punkt C1 hätte ich nie gedacht, dass ich damit jemand reinlege.

(Hmm, . . . aber wenn ich es gewusst hätte, hätte ich ihn schon deswegen genommen. Teufel )

Nein Blödsinn, ist ein Scherz. Der Grund ist der, dass es in Fraukes Anfrage heißt: " . . . ob 3 gegebene Punkte . . . " Und drei Punkte müssen nicht immer ein Dreieck bilden. Deshalb ein Fall mit drei Punkten in einer Geraden. Ein Programm muss das bewältigen.

Soweit ich Deinen Code verstehe, @HAL, werden auch andere entartete Dreiecke korrekt verarbeitet, z.B. zwei identische Punkte und ein davon verschiedener dritter, oder gleich drei Punkte in einem.
Ich denke, noch kürzer/einfacher geht nicht.
HAL 9000 Auf diesen Beitrag antworten »

Ja, den Entartungsfall habe ich oben nicht ausdrücklich erwähnt, aber der passt vollständig zu Fall b), selbst wenn alle drei Punkte zusammenfallen. Augenzwinkern

Das rechtwinklige Dreieck passt übrigens nicht nur zu a), sondern (in der rechnerischen Behandlung) auch zu b) - was ich im Skript auch genutzt habe.


P.S.: Übrigens sind werner und riwe zwei verschiedene Personen, sofern ich nicht irgendwas verpasst habe...

====================================================

Zur Erklärung der im Python-Skript verwendeten Formel des Umkreismittelpunkts: Da habe ich mir zunutze gemacht, dass man dort von Haus aus bequem mit komplexen Zahlen rechnen kann, hier einfach durch Identifikation der drei gegebenen Punkte mit den entsprechenden komplexen Zahlen in der Gaußschen Ebene. Klar ist dann

.

Der Mittelpunkt des Umkreises eines echten (d.h. nicht entarteten) Dreiecks ist Schnittpunkt zweier Mittelsenkrechten, das ist in komplexen Zahlen ausgedrückt



mit reellen Parametern , es folgt unmittelbar

.

Sei nun das übliche Skalarprodukt, wenn man die komplexen Zahlen als -Vektoren auffasst. Die letzte Gleichung skalarmultipliziert mit ergibt

.

Nun gilt für alle komplexen Zahlen , da ja und senkrecht aufeinander stehen, somit haben wir





und somit insgesamt schließlich

.

Setzt natürlich voraus, aber das ist bei einem echten Dreieck - so u.a. in Fall a) - erfüllt.
Mathema Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
P.S.: Übrigens sind werner und riwe zwei verschiedene Personen, sofern ich nicht irgendwas verpasst habe...


was ist mit meinem account passiert?
HAL 9000 Auf diesen Beitrag antworten »

Ok, dann ist es so: Ein "werner" (mit deutscher email-Adresse) hat sich 2004 registriert, nur einen Beitrag geschrieben, und mysteriöserweise ist sein Account 2009 an riwe (Österreicher) übergegangen, der seitdem auf zwei Accounts postet. Das finde ich schon etwas verwirrend, vor allem wenn dann irgend jemand mal mit riwe Kontakt aufnehmen will über die dann wohl nicht ihm gehörende email-Adresse [email protected] - vielleicht kann das irgendwie mal bereinigt werden.
werner Auf diesen Beitrag antworten »

der Ordnung halber: ich = riwe = werner bin genauso verwirrt, da meine Beiträge und Nachrichten zum Teil bis ganz verschwunden sind usw. .....

naja schade, waren doch sooo bedeutend Augenzwinkern

@Hal: wenn man in meinem 1. Beitrag die Spalten a, b, c .... um 2 Zeilen nach unten verschiebt sollte alles stimmen
HAL 9000 Auf diesen Beitrag antworten »

Hatte mich schon gewundert, wieso in den ersten beiden Zeilen überhaupt Werte von angegeben waren...

Was die Account-Geschichte betrifft: Lösche doch bitte mal die email-Adresse [email protected] aus deinem Profil, sofern es nicht die deine ist.
werner Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Hatte mich schon gewundert, wieso in den ersten beiden Zeilen überhaupt Werte von angegeben waren...

Was die Account-Geschichte betrifft: Lösche doch bitte mal die email-Adresse [email protected] aus deinem Profil, sofern es nicht die deine ist.

danke für den Hinweis, die ist mir gänzlich unbekannt.
Ich werde tun, was der Meister befiehlt Augenzwinkern
Ulrich Ruhnau Auf diesen Beitrag antworten »
RE: 3 Punkte in einem Kreis
Zitat:
Original von Frauke8
Ich arbeite momentan an einem Computerspiel. Dabei muss ich unter anderem überprüfen, ob 3 gegebene Punkte in einen Kreis mit einem bestimmten Radius passen. Derzeit gehe ich per Brute Force über einen Haufen von Mittelpunkten und überprüfe jeweils, ob die Punktabstände zwischen Kreismitte und Punkten kleinergleich dem Radius sind. Jedoch ist das nicht gerade genau und obendrein rechenintensiv. Gibt es da einen einfacheren Weg das Problem anzugehen?
.

Hallo Frauke8 Wink , hast Du nun einen besseren Weg für Dein Computerspiel gefunden? Sind wir richtiger Weise davon ausgegangen, daß ein Umkreis mit einem minimalen Radius gefunden werden soll? Ob und welchen Weg willst Du jetzt implementieren? Oder ist Dir alles zu kompliziert?

Man könnte die Rechnung vereinfachen, indem man von den drei Punkten den Mittelwert nimmt und das näherungsweise als Kreismittelpunkt einsetzt. Aber wenn Du die Brute-Force-Methode verwendest, dann hoffentlich ohne die Wurzel zu ziehen. Das kostet Rechenzeit. Dann prüfe lieber die Formel
Freude für mögliche Kreismittelpunkte in der Nähe des 3-Punktemittelwertes.

Melde Dich mal ! Ich möchte wissen, was Dir geholfen hat.
Du kannst von mir aus auch kleine Code-Auszüge hochladen und hier prüfen lassen. Willkommen
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Ulrich Ruhnau
Aber wenn Du die Brute-Force-Methode verwendest, dann hoffentlich ohne die Wurzel zu ziehen. Das kostet Rechenzeit.

Mein Python-Script oben kommt zur Berechnung des Mittelpunkts mit den vier Grundrechenarten aus; lediglich zur Berechnung des Radius wird eine einzige Quadratwurzelberechnung benötigt. In der Hinsicht ist die Vorgehensweise schon optimal. Augenzwinkern
Ulrich Ruhnau Auf diesen Beitrag antworten »

@HAL
Auf meinem Mac-Book habe ich momentan kein Python. Könntest Du vielleicht den Code in anderer Form hier darstellen?
Mit ging es vor allem darum, zu verhindern, daß Frauke8 undankbar ist und sich nicht mehr meldet. unglücklich
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Ulrich Ruhnau
Könntest Du vielleicht den Code in anderer Form hier darstellen?

Könnte ich, aber mache ich nicht. Die Umsetzung in andere Sprachen sollte kein ernstliches Problem sein.

https://www.python.org/downloads/macos/
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »