Schneidet eine Gerade einen Kreisbogen?

05.07.2018, 08:50

voodoo

Schneidet eine Gerade einen Kreisbogen?

Moin moin,

Ich hab momentan ein kleines problem. Ich soll rausfinden, ob eine gerade einen kreisbogen schneidet.
Ein einfaches beispiel:

[attach]47621[/attach]

Bild aus externem Link als Anhang eingefügt. Bitte keine externen Links verwenden. Steffen

Die rote Gerade schneidet zwar den Kreis aber nicht den Kreisbogen, die schwarze Gerade schneidet den Kreisbogen.
Ich weiß: Den Mittelpunkt des Kreises $\begin{eqnarray*} z = \left[ z_x z_y \right]^T \end{eqnarray*}$ , den Radius des Kreises berechnet mithilfe von $\begin{eqnarray*} x_0 \end{eqnarray*}$ . $\begin{eqnarray*} x_0 \end{eqnarray*}$ ist der Startpunkt des Kreisbogens, sodass $\begin{eqnarray*} R^2 = ||z - x_0||^2 \end{eqnarray*}$ gilt, wobei $\begin{eqnarray*} R^2 \end{eqnarray*}$ der radius zum quadrat ist. Den Endpunkt des Kreisbogens $\begin{eqnarray*} x_1 = \left[x_1 y_1\right]^T \end{eqnarray*}$

Dann habe ich für die Gerade 2 punkte gegeben. Ein Startpunkt und ein Endpunkt auf der Geraden (das kommt von meiner Anwendung so). Als Startpunkt $\begin{eqnarray*} x_{target} = \left[ x_0 y_0\right]^T \end{eqnarray*}$ und als Endpunkt ein weit entfernten Punkt $\begin{eqnarray*} x_out = \left[ x_1 y_1 \right]^T \end{eqnarray*}$ .

Ich habe jetzt angefangen damit, den Kreis zu beschreiben, also den vollständigen.
Es ist doch so, dass ich meinen vollständigen Kreis beschreiben kann mit $\begin{eqnarray*} (x - z_x)^2 + (y- z_y)^2 = R^2 \end{eqnarray*}$ .
Und meine gerade lässt sich doch beschreiben mit $\begin{eqnarray*} x(t) = (x_1 - x_0)t + x_0 \end{eqnarray*}$ .
hmmm aber was mach ich jetzt? wie gehts weiter?

05.07.2018, 10:05

HAL 9000

Auf diesen Beitrag antworten »

Du kannst den Kreis parametrisch beschreiben durch

$\begin{eqnarray*} \begin{pmatrix}x\\ y\end{pmatrix} = \begin{pmatrix}z_x\\ z_y\end{pmatrix} +R\begin{pmatrix}\cos(\varphi)\\ \sin(\varphi)\end{pmatrix}\qquad (*) \end{eqnarray*}$

wobei $\begin{eqnarray*} \varphi=0 \end{eqnarray*}$ dem Kreispunkt $\begin{eqnarray*} (z_x+R,z_y)^T \end{eqnarray*}$ entspricht, und dann für $\begin{eqnarray*} 0\leq \varphi\leq 2\pi \end{eqnarray*}$ der Kreis im mathematisch positiven Drehsinn einmal durchlaufen wird. Gemäß (*) kannst du Punkt $\begin{eqnarray*} x_0 \end{eqnarray*}$ einen Winkel $\begin{eqnarray*} \varphi_0 \end{eqnarray*}$ zuordnen (Stichwort: Polarkoordinatentransformation), ebenso $\begin{eqnarray*} x_1 \end{eqnarray*}$ einen Winkel $\begin{eqnarray*} \varphi_1 \end{eqnarray*}$ . Der Kreisbogen ist dann ebenfalls durch (*) gegeben, nur eben mit der Winkeleinschränkung $\begin{eqnarray*} \varphi_0\leq \varphi\leq \varphi_1 \end{eqnarray*}$ .

Ein Problem gibt es noch im Fall $\begin{eqnarray*} \varphi_1<\varphi_0 \end{eqnarray*}$ : Dann muss man den Endwinkel womöglich "eine Umdrehung weiter" betrachten, d.h. Wert $\begin{eqnarray*} \varphi_1 \end{eqnarray*}$ um einen Vollwinkel $\begin{eqnarray*} 2\pi \end{eqnarray*}$ erhöhen. (**)

Die Frage "Schnittpunkt ja/nein" läuft dann ähnlich: Die bewusste Gerade bzw. der Strahl wird mit dem Kreis geschnitten, und dem oder den Schnittpunkten werden dann wieder gemäß (*) passenden Winkel $\begin{eqnarray*} \varphi \end{eqnarray*}$ zugeordnet: Liegen diese im Intervall $\begin{eqnarray*} [\varphi_0,\varphi_1] \end{eqnarray*}$ , so wird tatsächlich der Bogen geschnitten, sonst nicht. Auch hier ist technisch wieder das Problem (**) zu beachten, aber das will ich jetzt nicht im Detail ausführen.

Zitat:

Original von voodoo
Als Startpunkt $\begin{eqnarray*} x_{target} = \left[ x_0 y_0\right]^T \end{eqnarray*}$ und als Endpunkt ein weit entfernten Punkt $\begin{eqnarray*} x_out = \left[ x_1 y_1 \right]^T \end{eqnarray*}$ .

Irgendwie symbolisch unklug, hier wieder mit $\begin{eqnarray*} x_0,x_1 \end{eqnarray*}$ zu operieren, wo diese Symbole schon durch die Kreisbogenendpunkte verbraten sind - das solltest du bereinigen, sonst führt das noch ins Chaos, z.B. schon gleich hier

Zitat:

Original von voodoo
Und meine gerade lässt sich doch beschreiben mit $\begin{eqnarray*} x(t) = (x_1 - x_0)t + x_0 \end{eqnarray*}$ .

05.07.2018, 11:04

riwe

Auf diesen Beitrag antworten »

RE: Schneidet eine Gerade einen Kreisbogen?
eventuell eine Alternative:

$\begin{eqnarray*} \vec{x}=\overrightarrow{A}+t\cdot(\overrightarrow{E}-\overrightarrow{A}) \end{eqnarray*}$

mit A und E Anfangs- und Endpunkt der Sehne
schneidet g diese Gerade mit 0 =< t <= 1 sollte man glücklich sein können Augenzwinkern

05.07.2018, 11:13

voodoo

Auf diesen Beitrag antworten »

RE: Schneidet eine Gerade einen Kreisbogen?

Zitat:

Original von riwe
schneidet g diese Gerade mit 0 =< t <= 1 sollte man glücklich sein können Augenzwinkern

So einen Tip hat man mir auch gegeben, aber ich versteh nicht ganz wie man das nun machen soll...
Was meinst du mit g?

05.07.2018, 13:49

HAL 9000

Auf diesen Beitrag antworten »

RE: Schneidet eine Gerade einen Kreisbogen?
@werner

Das ist ein brauchbares Verfahren, sofern die Gerade den Bogen garantiert höchstens einmal schneidet. Sind aber auch zwei Schnittpunkte möglich , so klappt das nicht.

Auch zu beachten: Wenn es nicht um Geraden, sondern Strahlen geht, und der Startpunkt des Strahls mitten im Kreissegment umrandet von dem bewussten Bogen und deiner Sehne liegt... Augenzwinkern

Es gibt also feine Unterschiede zu beachten zwischen dem Schnittverhalten Bogen sowie zugehöriger Sehne. Augenzwinkern

05.07.2018, 14:13

voodoo

Auf diesen Beitrag antworten »

RE: Schneidet eine Gerade einen Kreisbogen?
Ich müsste auf jedenfall wissen, wie oft meine Gerade meinen Kreisbogen schneidet. Also es kann in meiner Anwendung vorkommen, dass der Startpunkt und der Endpunkt der Gerade außerhalb des Kreisbogen liegt aber der Kreisbogen zweimal geschnitten wird.

So wie ich das gerade rausgelesen habe, lässt sich dann der Ansatz von Werner nicht weiter verfolgen oder?

05.07.2018, 14:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von voodoo
Also es kann in meiner Anwendung vorkommen, dass der Startpunkt und der Endpunkt der Gerade außerhalb des Kreisbogen liegt aber der Kreisbogen zweimal geschnitten wird.

Soviel geometrisches Vorstellungsvermögen solltest du doch haben, dass du erkennst, dass in diesem Fall die Sehne nicht geschnitten wird.

05.07.2018, 17:31

riwe

Auf diesen Beitrag antworten »

RE: Schneidet eine Gerade einen Kreisbogen?

Zitat:

Original von HAL 9000
@werner

Das ist ein brauchbares Verfahren, sofern die Gerade den Bogen garantiert höchstens einmal schneidet. Sind aber auch zwei Schnittpunkte möglich , so klappt das nicht.

Auch zu beachten: Wenn es nicht um Geraden, sondern Strahlen geht, und der Startpunkt des Strahls mitten im Kreissegment umrandet von dem bewussten Bogen und deiner Sehne liegt... Augenzwinkern

Es gibt also feine Unterschiede zu beachten zwischen dem Schnittverhalten Bogen sowie zugehöriger Sehne. Augenzwinkern

ja klar

06.07.2018, 20:36

voodoo

Auf diesen Beitrag antworten »

RE: Schneidet eine Gerade einen Kreisbogen?
Also rein theoretisch sind in meiner Anwendung alle Fälle möglich. Ich hab von meinem Tutor eben nur die Lösung von Werner bekommen, aber die ist wohl nicht gedacht für meinen Fall.

Nehmen wir also an, das ich meinen Kreisbogen definiert habe mit drei Punkten, $\begin{eqnarray*} z \end{eqnarray*}$ , $\begin{eqnarray*} x_0 \end{eqnarray*}$ und $\begin{eqnarray*} x_1 \end{eqnarray*}$ und meine zwei Punkte ebenfalls definiert sind.
Die zwei Punkte würden meine Linie bezeichnen: $\begin{eqnarray*} P_1 = \begin{pmatrix} a_1 \\ a_2 \end{pmatrix} \end{eqnarray*}$ und $\begin{eqnarray*} P_2 = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \end{eqnarray*}$ .
So jetzt kommen wir auch nicht mehr mit den Punkten durcheinander.

$\begin{eqnarray*} \begin{pmatrix} v \\ w \end{pmatrix} = \begin{pmatrix} z_x \\ z_y \end{pmatrix} + R \cdot \begin{pmatrix} \cos{\phi} \\ \sin{\phi} \end{pmatrix} \end{eqnarray*}$
das denke ich kapier ich. Muss halt nur eigentlich $\begin{eqnarray*} \phi \end{eqnarray*}$ suchen und dann könnte ich einfach mein $\begin{eqnarray*} v \end{eqnarray*}$ bzw. $\begin{eqnarray*} w \end{eqnarray*}$ ausrechnen, wobei
$\begin{eqnarray*} (1) \begin{pmatrix} x_0 \\y_0 \end{pmatrix} = \begin{pmatrix} z_x \\z_y \end{pmatrix} + R \cdot \begin{pmatrix} \cos{\phi}\\\sin{\phi} \end{pmatrix}\\ (2) \begin{pmatrix} x_1\\y_1 \end{pmatrix} = \begin{pmatrix} z_x \\z_y \end{pmatrix} + R \cdot \begin{pmatrix} \cos{\phi}\\\sin{\phi} \end{pmatrix}\\ \end{eqnarray*}$
im prinzip formel umstellen und ausrechnen oder? Bis hierhin ist die überlegung doch richtig (abgesehen von dem Spezialfall $\begin{eqnarray*} \phi_0 > \phi_1 \end{eqnarray*}$ )

So wie bringe ich jetzt meine Punkte $\begin{eqnarray*} P_1 \end{eqnarray*}$ und $\begin{eqnarray*} P_2 \end{eqnarray*}$ da mit rein? da steh ich noch so ein bisschen auf dem Schlauch... traurig

11.07.2018, 10:48

voodoo

Auf diesen Beitrag antworten »

ich habe eine Lösung, die allerdings ein bisschen anders ist:
ich kann meinen kreis beschreiben mit: $\begin{eqnarray*} (x - z_x)^2 + (y - z_y)^2 - r^2 = 0 \end{eqnarray*}$ (1)
dabei ist $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ die x- und y- koordinaten von einem Punkt auf dem Kreis.

Jetzt kann ich meine gerade beschreiben mit: $\begin{eqnarray*} P = (P_2 - P_1) \cdot t + P_1 \end{eqnarray*}$ (2), wobei $\begin{eqnarray*} P = \begin{pmatrix} x\\y \end{pmatrix} \end{eqnarray*}$

so unser t können wir jetzt wie folgt berechnen: $\begin{eqnarray*} at^2 + bt + c = 0 \end{eqnarray*}$ mit:
$\begin{eqnarray*} a = (b_1 - a_1)^2 + (b_2 - a_2)^2 \end{eqnarray*}$
$\begin{eqnarray*} b = 2\cdot(b_1 - a_1) \cdot (a_1 - z_x) + 2\cdot(b_2 - a_2) \cdot (a_2 - z_y) \end{eqnarray*}$
$\begin{eqnarray*} c = (a_1 - z_x)^2 + (a_2 - z_y)^2 - r^2 \end{eqnarray*}$

es folgt: $\begin{eqnarray*} t_{1,2} = \frac{-b \pm \sqrt{b^2 - 4 a c}}{2a} \end{eqnarray*}$

Soweit hoffentlich versändlich... klar, wenn $\begin{eqnarray*} b^2 - 4 a c < 0 \end{eqnarray*}$ ist, dann wird die wurzel daraus imaginär und die gerade schneidet den kreis nicht.
Wenn $\begin{eqnarray*} 0 < t_{1,2} < 1 \end{eqnarray*}$ ist, dann schneidet die gerade den kreis. das heißt wir können uns $\begin{eqnarray*} t_{1,2} \end{eqnarray*}$ ausrechnen. das setzen wir dann in (2) ein um $\begin{eqnarray*} P \end{eqnarray*}$ auszurechnen.
Dann können wir den Punkt $\begin{eqnarray*} P = \begin{pmatrix} x\\y \end{pmatrix} \end{eqnarray*}$ in (1) einsetzen.
Wir haben also einen Punkt auf dem Kreis. Um auszurechnen, ob das ding auf dem Kreisbogen liegt, dann einfach mit $\begin{eqnarray*} atan2 \end{eqnarray*}$ überprüfen, ob der Punkt $\begin{eqnarray*} P \end{eqnarray*}$ zwischen dem Punkt $\begin{eqnarray*} x_0 \end{eqnarray*}$ und $\begin{eqnarray*} x_1 \end{eqnarray*}$ liegt (mit transponierung, Mittelpunkt $\begin{eqnarray*} z \end{eqnarray*}$ haben wir ja)

Ich hoffe ich hab alles richtig aufgeschrieben... Bei mir funktioniert es jetzt super

11.07.2018, 13:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von voodoo
Um auszurechnen, ob das ding auf dem Kreisbogen liegt, dann einfach mit $\begin{eqnarray*} atan2 \end{eqnarray*}$ überprüfen, ob der Punkt $\begin{eqnarray*} P \end{eqnarray*}$ zwischen dem Punkt $\begin{eqnarray*} x_0 \end{eqnarray*}$ und $\begin{eqnarray*} x_1 \end{eqnarray*}$ liegt

Nun, das klingt doch genau nach meinem Vorschlag oben: atan2 ist doch die Funktion, mit der man den Winkel der Polarkoordinatentransformation ausrechnet.

12.07.2018, 10:26

voodoo

Auf diesen Beitrag antworten »

atan2: https://de.wikipedia.org/wiki/Arctan2#Formel

Also im Prinzip guckt man, wenn $\begin{eqnarray*} 0 < t < 1 \end{eqnarray*}$ , ob der Punkt, denn man für den Kreis ausgerechnet hat auf dem Kreisbogen liegt oder eben nicht.

12.07.2018, 10:34

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von voodoo
Wenn $\begin{eqnarray*} 0 < t_{1,2} < 1 \end{eqnarray*}$ ist, dann schneidet die gerade den kreis.

Den Teil hatte ich mir noch gar nicht genauer angeschaut... du musst sprachlich genauer sein:

Die Gerade durch $\begin{eqnarray*} P_1,P_2 \end{eqnarray*}$ schneidet den Kreis, wenn die obige quadratische Gleichung überhaupt reelle Lösungen $\begin{eqnarray*} t \end{eqnarray*}$ hat - jede dieser Lösungen entspricht dann einem Schnittpunkt der Gerade mit dem Kreis.

Aber nur für $\begin{eqnarray*} t \end{eqnarray*}$ -Werte im Intervall $\begin{eqnarray*} [0,1] \end{eqnarray*}$ liegen diese Punkte der Geraden auch tatsächlich auf der Strecke (!) $\begin{eqnarray*} P_1P_2 \end{eqnarray*}$ .

Worauf kommt es dir nun hinsichtlich des Schnittes mit dem Kreisbogen an, auf die (unendliche) Gerade oder doch nur auf die (endliche) Strecke? Im Eröffungsbeitrag war noch von "Gerade" die Rede, aber womöglich verwendest du die Begriffe ja etwas fahrlässig...

Neue Frage »

Antworten »

Schneidet eine Gerade einen Kreisbogen?

Verwandte Themen