Hi,

ich wollt mal fragen wie man prüft ob ein Kreis eine Linie schneidet

ich hab schon einige src gefunden, allerdings bisher in c, was aber nich wirklich ein problem ist das zu portieren, nur funzt das nie so dann wie es soll.

Wenn jemand ne schöne Line-Circle Kollisions Funktion posten könnte wäre ich sehr dankbar und könnte endlich mein fast gestorbenes projekt Crackout wieder zum leben erwecken

Hier mal ne routine die ich gefunden habe, und portiert habe, die aber ums verrecken nicht funzt:

Achja, das ganze ist 2D, obs 2D oder 3D ist mir relativ schnuppe.
3D wäre nicer, muss aber nich sein.

:::

Delphi:



C:



daher hab ich die routine:
http://www.scherfgen-software.net/index ... lision2d_2


thx im voraus,
Final

Ich kann zwar im Moment leider nicht nachprüfen ob mein Gerechne jetzt so stimmt (ich hock gerade an einen FH-CIP-Pool Rechner ohne installierter Progragrammiersprache und leider hab ich auch keinen Taschenrechner oder Formelsammlung zur Hand), aber ich versuch´s mal:

Also erstmal den Kreis: (Methode ala Pythagoras)


(X+Xo)^2 + (Y+Yo)^2 = R^2 => X = sqrt ( R^2 - (Y-Yo)^2 ) -Xo

Xo,Yo = Kreismittelpunkt

Eine Gerade beschreiben... sagen wir mal mit:

Y=mX+t (Jede andere Geradenformel würde es vermutlich auch tun,
Tipp: 2-Punkt-Geradenformel - hab´s nur gerade leider nicht im Kopf)

m = Steigung
t = Y-Achsenabschnitt

eingesetzt wäre dann :

m*sqrt ( R^2 - (Y-Yo)^2) - Xo +t - Y = 0

Also wenn dieser Term da oben Null ist (if-Abfrage), dann trifft deine Gerade den Kreis(hoffe ich zumindest, bitte rechne es nochmal durch ...
jetzt mußt du nur noch in deinen Linienzeichnen-Algorithmus diese
Formel mitreinwurschteln und die Gerade Punkt für Punkt abfragen...
(Möglicherweise mit den Bresenham-Algorithmus ?!?)

_________________
Jetzt reicht´s - her mir der Flex !

Die Gerade Punkt für Punkt abfragen? Das halte ich für ziemlich illusorisch... in welcher Auflösung willst du denn die For-Schleife entlang laufen ohne das du Gefahr läufst einen Schnittpunkt zu übersehen? Diese Auflösung müsst ja rein mathematisch unendlich klein sein.
Und dazu kommt, dass es ziemlich schwierig wird den Bereich der Gerade zu definieren auf den man die For-Schleife ansetzt, zumindest wenn man flexibel bleiben will. In jedem Fall musst du hunderte Rechnungen durchführen nur um bei 99% festzustellen, dass da kein Schnittpunkt war. Ziemliche Rechenzeitverschwendung.

Ich denke mal man kann die beiden Schnittpunkte auch einfach ausrechnen.
Folgende Überlegung:

1.) wir haben eine Gerade g(x) = A + x * B
B ist ein Richtungsvektor und A ein Punkt auf der Gerade.

2.) wir haben außerdem eine Kugel definiet über einen Mittelpunkt M und einen Radius r.

wir suchen nun ein Skalar s so das g(s) Schnittpunkt mit der Kugel ist. Das heißt der Abstand zwischen g(s) und M ist genau r.
d. h. |g(s) - M| = r
<-> |A + s * B - M| = r

Durch Auflösen des Betrags, Quadrierung und Umstellen lässt sich folgende Gleichung erhalten:

c1 * s² + 2 * c2 * s + c3 = r²
wobei gilt:
c1 = |B|²
c2 = (M[0]-A[0])*B[0] + (M[1]-A[1])*B[1] + (M[2]-A[2])*B[2]
c3 = |M-A|²
ERKLÄRUNG zu c2: B[2] bedeutet 3. Komponente des Vektors b bzw. die Z-Komponente. Was da im Prinzip steht ist das Punktprodukt von (M-A) und B.

Durch einsetzen obiger Gleichung in die Quadratische Lösungsformel erhalten wir:

s1 = - (c2/c1) + sqrt[ (c2/c1)² - (c3 - r²)/c1 ]
s2 = - (c2/c1) - sqrt[ (c2/c1)² - (c3 - r²)/c1 ]

Die gesuchten Schnittpunkte sind also S1 = g(s1) und S2 = g(s2)
Tangiert die Gerade die Kugel gibt der Wurzelausdruck 0. Ist der die Zahl unter der Wurzel gar negativ bedeutet das, dass die Gerade die Kugel nicht schneidet.

Wenn ich mich nicht verrechnet/verdacht habe, müsst man so relativ schnell und sicher auf die Schnittpunkte kommen so sie den existieren. Implementierbar in wenigen Zeilen Code.

Grüße,
Lith

_________________
Selber Denken macht klug!

Wenn es nur 2D sein soll, du die Kollisionspunkte nicht brauchst und auch nur prüfen willst, ob die Linie von der Richtung her den Kreis trifft (zielen etc), dann gibt es noch zwei einfache geometrische Ansätze:
Einen über das Lot und einen über Winkel.

- Zum ersteren hab ich vor langer Zeit mal eine Funktion geschrieben, die allerdings nicht getestet ist. Sie bilded die Senkrechte vom Kreismittelpunkt auf die Linie und prüft dann, ob der Schnittpunkt zwischen Senkrechte und Linie innerhalb des Kreises liegt.



- Für den Ansatz über die Winkel brauchst du zwei Vektoren, den Richtungvektor der Line und einen zwischen Linienanfang und Kreismittelpunkt. Ist der Winkel den diese Vorktoren einschließen kleiner als der Arcustangent vom Betrag des zweiten Vektors und dem Radius des Kreises, so schneidet die Linie den Kreis.
Allsklar? ... Naja wenn man es sich aufzeichnet ist es sehr einleuchtend


Wie auch immer das sind natürlich geometrische ansätze also für Computerspiele so nicht unbedingt geeignet, weil zu speziell und langsam, aber ich dachte es interessiert dich vielleicht.