Schnittpunkte einer Strecke mit einem Kreisausschnitt

Neue Frage »

LarstheLax Auf diesen Beitrag antworten »
Schnittpunkte einer Strecke mit einem Kreisausschnitt
Meine Frage:
Hallo,

ich muss für eine Simulation die Schnittpunkte einer Strecke (definiert durch zwei beliebige Punkte) mit einem Kreisausschnitt (gegeben ist der Mittelpunkt, Radius und beide begrenzenden Punkte auf dem Kreisbogen) berechnen. Schwierig dabei ist der Kreisbogen.

Meine Ideen:
Die Schnittpunkte mit den beiden Strecken des "Kuchenstückes" kann man mit einem linearen Gleichungssystem für den Schnittpunkt zweier Strecken berechnen.
Aber bei dem Kreisbogen bin ich etwas ratlos.
Ich habe viele Erklärungen für die Berechnung zwischen Geraden und Kreis gefunden, aber nichts bei meinem Problem.
Generell gibt es da ja drei Möglichkeiten: Keine, einen oder zwei Schnittpunkte.
Steffen Bühler Auf diesen Beitrag antworten »
RE: Schnittpunkte einer Strecke mit einem Kreisausschnitt
Willkommen im Matheboard!

Durch Gleichsetzen der Kreis- und Geradengleichung müsstest Du weiterkommen. Hast Du es damit schon probiert?

Viele Grüße
Steffen
LarstheLax Auf diesen Beitrag antworten »

Vielen Dank!

Die Schnittpunkte einer Geraden mit einem Kreis herauszufinden ist ja wie schon geschrieben recht einfach.
Nur hab ich erstens keine Gerade, sondern eine Strecke. Also ist meine Streckengleichung so etwas hier:
(x(s), y(s))=(x1+s*(x2-x1), y1+s*(y2-y1))

Und ich habe ja auch keinen vollen Kreis, sondern nur ein Kreissegment. D.h. ich habe eine gekrümmte Strecke (Kreisbogen oder auch Kreissehne) zwischen zwei Punkten.
Nun weiß ich aber nicht wie man dafür eine Gleichung aufstellt, bzw. die Gleichung eines vollen Kreises umstellt.
Und natürlich weiß ich nicht, wie ich diese Gleichung dann mit meiner Streckendefinition gleichsetzen soll.
Steffen Bühler Auf diesen Beitrag antworten »

Ich verstehe Dich so, dass Du zwei Punkte einer Strecke hast, also und .

Dann kannst Du doch auf jeden Fall eine Geradengleichung aufstellen, mit .

Und Du hast einen Kreis mit Mittelpunkt und Radius . Der hat die Gleichung .

Nun sollten sich doch die beiden Schnittpunkte durch Gleichsetzen dieser Terme ergeben, also .

Oder verstehe ich etwas falsch?
LarstheLax Auf diesen Beitrag antworten »

Das stimmt so schon, ja.
Nur weiß ich dann ja noch nicht ob die Schnittpunkte die da raus kommen auch wirklich auf der Strecke oder sonst wo auf der Geraden liegen.
Und beim Kreis ist es genauso. Dass es Schnittpunkte mit dem Kreis gibt, heißt noch lange nicht, dass diese Schnittpunkte auch innerhalb des Kreisbogens liegen.
Ich könnte natürlich die Gleichung aus Gerade und Kreis lösen und dann testen ob die Schnittpunkte auf der Strecke liegen. beim Kreisbogen wäre es etwas schwieriger.
Steffen Bühler Auf diesen Beitrag antworten »

Ach, jetzt verstehe ich .

Zitat:
Original von LarstheLax
Ich könnte natürlich die Gleichung aus Gerade und Kreis lösen und dann testen ob die Schnittpunkte auf der Strecke liegen.


Ja, das wäre dann die Konsequenz mit meiner Methode. Vielleicht hat jemand noch eine elegantere Idee.

Viele Grüße
Steffen
 
 
Huggy Auf diesen Beitrag antworten »

Um das Testen in irgendeiner Form wird man nicht herumkommen. Die Frage ist, wie man das macht? Wenn man keine Zeichnung machen will, empfiehlt es sich, Geraden und Kreis in Parameterform darzustellen. Man muss dann prüfen, ob die Parameter der eventuellen Schnittpunkte in dem zulässigen Bereich für die Strecken bzw. für den Kreisbogen liegen. Abgesehen von technischen Details sehe ich da keine Probleme.
LarstheLax Auf diesen Beitrag antworten »

Alles klar, dann mache ich das so:
Aus Strecke und Kreisbogen mache ich eine Gerade und einen Kreis.
Dann berechne ich die Schnittpunkte von Gerade und Kreis.
Falls es Schnittpunkte gibt:
Liegen diese auf dem von der Strecke benützten Teil der Geraden?
Und liegen die dann noch übrigen Schnittpunkte auf dem Kreisbogen?

Die Überprüfung mit dem Kreisbogen kann man so machen, dass man die Koordinaten der beiden Grenzpunkte auf dem Bogen als Bedingungen nimmt. Nur wenn der Schnittpunkt einen X- und einen Y-Wert hat, die im Intervall X1->X2 bzw. Y1->Y2 liegen (hier mit den Vorzeichen aufpassen), liegt er auch auf dem Kreisbogen.

Das mit der Zeichnung geht leider nicht, weil ich das Ganze implementieren muss.
LarstheLax Auf diesen Beitrag antworten »

Hallo nochmal,

ich habe die ganzen Rechnungen jetzt implementiert und bin fleißig am testen.
Dummerweise hab ich gemerkt, dass mir ein Fehler unterlaufen ist. Und zwar bei dem Teil
"Und liegen die dann noch übrigen Schnittpunkte auf dem Kreisbogen?".

Ich bin erst davon ausgegangen, dass ich lediglich die X- und Y-Werte der beiden Kreisbogenendpunkte mit den Koordinaten meiner berechneten Punkte vergleichen muss. Also sozusagen: Wenn X>X1 & X<X2.
Das funktioniert aber nur 100%ig bei Kreisvierteln wo ein Endpunkt auf dem selben X-Wert und der andere auf dem selben Y-Wert wie der Kreismittelpunkt liegt.

Da ich ja schon vorher weiß, dass die Punkte auf jeden Fall auf dem Kreis liegen, könnte man ja über die beiden Endpunkte ein Rechteck aufspannen (direkte Verbindung ist Diagonale der Rechtecks) und schauen ob der Punkt darin liegt.
Nur ist das jetzt etwas umständlich zu programmieren.
Hat irgendjemand vielleicht noch eine andere Idee?
Steffen Bühler Auf diesen Beitrag antworten »

Ich hatte damals darüber nachgedacht, die Winkel von Start- und Endpunkt des Kreisausschnitts zu berechnen. Und die beiden Winkel der Schnittpunkte. Letztere müssen dann zwischen ersteren liegen.

Allerdings kann ich mich erinnern, dass ich bei einem ähnlichen Problem ins Schleudern kam, weil das "dazwischen" nicht so einfach zu definieren ist. Außerdem fand ich Deinen Intervallansatz recht elegant, daher hab ich nichts dazu geschrieben.

Aber vielleicht ist mein Winkelansatz noch ausbaufähig.

Viele Grüße
Steffen
HAL 9000 Auf diesen Beitrag antworten »

Ich hab den Thread mal kurz überflogen, und ich würde es so machen:

Sei der bewusste Kreis, die beiden den Kreisbogen begrenzenden Endpunkte, sowie ein Vektor senkrecht zu , der in die Halbebene des Kreisbogens hinein zeigt, außerdem sei für jeden Punkt der Ebene definiert.

Dann liegt genau dann auf dem Kreisbogen, wenn gilt - weil er dann in der "richtigen" Halbebene liegt!

So, nun zu einer beliebigen Geraden in dieser Ebene, da gibt es folgende Fälle:

1) : Nix zu tun.

2) (Tangente): Im Fall liegt der Tangentenpunkt auf dem Kreisbogen, im Fall nicht.

3) (echter Schnitt mit zwei Punkten):

3.1) Im Fall liegen sowohl auf dem Kreisbogen, die Gerade schneidet Strecke nicht.

3.2) Im Fall liegt auf dem Kreisbogen, nicht, die Gerade schneidet Strecke .

3.3) analog mit vertauschten Rollen der beiden Punkte.

3.4) Im Fall liegen sowohl nicht auf dem Kreisbogen, und die Gerade schneidet auch Strecke nicht.


Bei dieser Methode hatte ich auch ein wenig die Performance im Auge: Hier benötigt man nur Grundrechenarten, während bei Winkelberechnungen zwangsläufig Trigonometrie ins Spiel kommt, i.d.R. ein Performance-Killer verglichen mit den vorgenannten Operationen. Augenzwinkern
LarstheLax Auf diesen Beitrag antworten »

Das mit dem Winkel habe ich tatsächlich später im Code verwendet. Da ging es darum, dass die Strecke mit dem ganzen Kuchenstück nur einen Schnittpunkt hat und einer der Streckenendpunkte im Kreisbogen liegen muss.

Mit der Methode von HAL 9000 könnte man das ja alles in eine externe Funktion packen und die dann an unterschiedlichen Stellen aufrufen.
Den Vektor r bestimme ich sowieso schon für oben genannte Winkelberechnung (der Mittelpunkt der Strecke AB wird mit dem Kreismittelpunkt verbunden).

Mir ist nur nicht ganz klar, wie ich f(P)>=0 testen soll.
Da ich im zweidimensionalen Koordinatensystem unterwegs bin, müsste f(P) ja eine X- und eine Y-Komponente haben.
Oder ist f(P) dann ein Vektor dessen Richtung ich bestimmen muss um zu sehen ob f(P)>=0 gilt?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von LarstheLax
Mir ist nur nicht ganz klar, wie ich f(P)>=0 testen soll.
Da ich im zweidimensionalen Koordinatensystem unterwegs bin, müsste f(P) ja eine X- und eine Y-Komponente haben.

Wie bitte? Als Skalarprodukt der zwei genannten Vektoren ist das eine reelle Zahl!!! Oder hast du meine obige Definition von schlicht überlesen:

Zitat:
Original von HAL 9000
für jeden Punkt der Ebene definiert.

ist der Verbindungsvektor der beiden Punkte A,P.
LarstheLax Auf diesen Beitrag antworten »

Oh, stimmt. Tschuldigung!
Dann ist mir alles klar und ich kann loslegen.
Vielen Dank!
Neue Frage »
Antworten »



Verwandte Themen

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