Kreisliniensegment-Kollisionserkennungsalgorithmus?
Habe ich eine Linie von a nach B und Einen Kreis an Position C mit dem radius R.
Was ist ein guter Algorithmus zu verwenden, um zu überprüfen, ob die Zeile schneidet der Kreis? Und auf welcher Koordinate entlang der Kreise Rand es aufgetreten ist?
InformationsquelleAutor der Frage Mizipzor | 2009-07-02
Du musst angemeldet sein, um einen Kommentar abzugeben.
Unter
Berechnen:
d = L - E ( Richtungsvektor von ray, von Anfang bis Ende )
f = E - C ( Vektor vom Mittelpunkt der Sphäre zur ray-start )
Dann die Schnittmenge gefunden..
Das Stopfen:
P = E + t * d
Dies ist eine parametrische Gleichung:
Px = Ex + tdx
Py = Ey + tdy
in
(x - h)2 + (y - k)2 = r2
(h,k) = Mittelpunkt des Kreises.
zu bekommen:
x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0
x = ex + tdx
y = ey + tdy
( ex + tdx )2 - 2( ex + tdx )h + h2 +
( ey + tdy )2 - 2( ey + tdy )k + - k2 - r2 = 0
ex2 + 2extdx + h2dx2 - 2exh - 2tdxh + h2 +
ey2 + 2eytdy + h2dy2 - 2ey - k - 2tdy - k + - k2 - r2 = 0
t2 dx2 + dy2 ) +
2t( exdx + eydy - dx - h - dyk ) +
ex2 + ey2 -
2exh - 2eyk + h2 + - k2 - r2 = 0
t2( _d * _d ) + 2t( _e * _d - _d * _c ) + _e * _e - 2( _e*_c ) + _c * _c - r2 = 0
*Wo _d ist der Vektor d und * ist das Skalarprodukt.*
t2( _d * _d ) + 2t( _d * ( _e - _c ) ) + ( _e - _c ) * ( _e - _c ) - r2 = 0
t2( _d * _d ) + 2t( _d * _f ) + _f * _f - r2 = 0
So erhalten wir:
t2 * (d PUNKT d) + 2t*( f PUNKT d ) + ( f PUNKT f - r2 ) = 0
So lösen Sie die quadratische Gleichung:
InformationsquelleAutor der Antwort bobobobo
Niemand scheint zu überlegen, Projektion, bin ich völlig aus der Bahn hier?
Projekt der Vektor
AC
aufAB
. Der projizierte Vektor,AD
gibt der neue PunktD
.Wenn der Abstand zwischen
D
undC
ist kleiner als (oder gleich)R
haben wir eine Kreuzung.Wie diese:
InformationsquelleAutor der Antwort Mizipzor
Ich würde den Algorithmus zur Berechnung der Distanz zwischen einem Punkt (Mittelpunkt des Kreises) und eine Linie (Linie AB). Dies kann dann verwendet werden zum bestimmen der Schnittpunkte der Linie mit dem Kreis.
Lassen Sie uns sagen, wir haben die Punkte A, B, C. Ax und Ay sind die x-und y-Komponenten der Punkte. Dasselbe für B und C. Das Skalar R ist der Kreisradius.
Hier ist der Algorithmus
InformationsquelleAutor der Antwort chmike
Okay, ich werde nicht geben Sie den code, aber da haben Sie tagged Algorithmusich glaube nicht, dass wird die Ihnen wichtig sind.
Erste, Sie haben, um einen Vektor senkrecht zu der Linie.
Haben Sie eine unbekannte variable in
y = ax + c
(c
unbekannt sein wird )Zu lösen, Berechnen Sie den Wert, wenn die Linie geht durch den Mittelpunkt des Kreises.
Ist,
Stecker in die Position des Mittelpunkts der Linie Gleichung zu lösen und für
c
.Dann berechnen Sie den Schnittpunkt der ursprünglichen Linien-und das ist normal.
Diese geben Sie den nächsten Punkt auf der Linie des Kreises.
Berechnen Sie die Entfernung zwischen diesem Punkt und dem Mittelpunkt des Kreises (mit der Größe des Vektors).
Wenn dieser kleiner ist als der radius der Kreis - voila, wir haben eine Schnittmenge!
InformationsquelleAutor der Antwort a_m0d
Andere Methode verwendet das Dreieck ABC area-Formel. Die Kreuzung test ist einfacher und effizienter als die Projektions-Methode, aber die Suche nach den Koordinaten des schnittpunkts mehr Arbeit erfordert. Zumindest wird es verzögert werden, bis zu dem Punkt es erforderlich ist.
Die Formel zur Berechnung der Dreiecks-Bereich ist : Fläche = bh/2
wo b ist die Basis-Länge und h die Höhe. Wir entschieden uns für die Strecke AB um die Basis, so dass h ist die kürzeste Entfernung von C, der Mittelpunkt des Kreises, auf die Linie.
Da das Dreieck kann auch berechnet werden, indem ein Vektor-Skalarprodukt können wir bestimmen h.
UPDATE 1 :
Könnte man den code optimieren, indem Sie mit der fast inverse square root-Berechnung beschrieben hierum eine gute approximation von 1/LAB.
Computing-der Schnittpunkt ist nicht so schwierig. Hier geht es
Wenn h = R, dann die Linie AB ist Tangente an den Kreis und den Wert dt = 0 und E = F. Die Koordinaten sind die von E und F.
Sollten Sie überprüfen, dass A ist Verschieden von B und die segment-Länge ist nicht null, wenn dies kann passieren, in Ihrer Anwendung.
InformationsquelleAutor der Antwort chmike
Diese Lösung, die ich gefunden schien ein wenig leichter zu Folgen, als einige der anderen.
Unter:
Ich würde lösen der Gleichung der Linie in den Hang-Achsenabschnitt form. Aber ich wollte nicht zu haben, um mit schwierigen Gleichungen mit
c
als einen Punkt, so dass ich nur verschob das Koordinatensystem über, so dass der Kreis an0,0
Übrigens, wenn ich subtrahieren Punkte von einander, ich bin die Subtraktion der
x
's und dann die Subtraktion dery
's, und setzen Sie in einen neuen Punkt, nur für den Fall jemand nicht wusste.Jedenfalls habe ich nun lösen Sie die Gleichung der Linie mit
p3
undp4
:Ok. Jetzt muss ich diese Gleichungen gleich. Zuerst muss ich die lösen die Kreis Gleichung für
x
Dann setze ich Sie gleich:
Und lösen der quadratischen Gleichung (
0 = ax^2 + bx + c
):Nun habe ich meine
a
b
undc
.Damit ich dies in die quadratische Formel:
Sind und ersetzt Sie durch Werte dann vereinfachen Sie soweit wie möglich:
Das ist fast genauso weit wie möglich vereinfachen. Schließlich trennen sich zu Gleichungen, die mit den ±:
Dann stecken Sie einfach das Ergebnis der beiden Gleichungen in die
x
immx + b
. Zur Klarstellung, ich schrieb einige JavaScript-code, um zu zeigen, wie Sie diese nutzen:Ich hoffe, das hilft!
P. S. Wenn jemand findet, etwaige Fehler oder hat irgendwelche Vorschläge, bitte kommentieren. Ich bin ganz neu und begrüße alle Hilfe/Vorschläge.
InformationsquelleAutor der Antwort multitaskPro
Ich ein kleines Skript geschrieben, um zu testen Kreuzung mit der Projektierung von Kreis, Mittelpunkt Punkt auf der Linie.
http://jsfiddle.net/ercang/ornh3594/1/
Wenn Sie überprüfen müssen, um die Kollision mit dem Teil, Sie müssen auch prüfen, circle center Entfernung zu start-und end-Punkte.
https://jsfiddle.net/ercang/menp0991/
InformationsquelleAutor der Antwort ercang
Finden Sie einen Punkt auf einer unendlichen Linie, die am nächsten zum Mittelpunkt des Kreises wird durch projizieren der Vektor AC auf Vektor AB. Berechnen Sie die Entfernung zwischen diesem Punkt und Kreismittelpunkt. Wenn es größer ist als R, es gibt keinen Schnittpunkt. Wenn der Abstand gleich R, ist die Linie eine Tangente an den Kreis und den Punkt am nächsten Kreis-center ist eigentlich der Schnittpunkt. Wenn die Entfernung weniger als R, dann gibt es 2 Schnittpunkte. Sie liegen in der gleichen Entfernung von dem Punkt am nächsten Kreis-center. Die Entfernung kann leicht berechnet werden, den Satz des Pythagoras. Hier ist der Algorithmus in pseudocode:
EDIT: code Hinzugefügt, um zu überprüfen, ob die gefundenen Schnittpunkte tatsächlich sind innerhalb der Linie segment.
InformationsquelleAutor der Antwort Juozas Kontvainis
Komischerweise kann ich beantworten, aber nicht ein Kommentar...
Ich mochte Multitaskpro Ansatz der Verlagerung alles, um das Zentrum des Kreises fallen auf den Ursprung. Leider gibt es zwei Probleme, die in seinem code. Zunächst in der unter-dem-Quadrat-Wurzel-Teil, das Sie benötigen, um entfernen Sie die doppelte power. Also nicht:
var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));
aber:
var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);
In der final-Koordinaten vergisst er eine Verschiebung der Lösung zurück. Also nicht:
var i1 = {x:t1,y:m*t1+b}
aber:
var i1 = {x:t1+c.x, y:m*t1+b+c.y};
Die ganze Funktion wird dann:
InformationsquelleAutor der Antwort Duq
Müssen Sie einige mathematische hier:
Angenommen, A = (Xa, Ya), B = (Xb, Yb) und C = (Xc, Yc). Jeder Punkt auf der Linie von A nach B hat die Koordinaten (alpha*Xa + (1-alpha)Xb, alphaYa + (1-alpha)*Yb) = P
Wenn der Punkt P hat den Abstand R zu C, es muss sich auf dem Kreis. Was Sie wollen, ist zu lösen
ist
wenn Sie die ABC-Formel, um diese Gleichung zu lösen, die es für alpha, und berechne die Koordinaten von P mit Hilfe der Lösung(en) bei alpha erhalten Sie die Schnittpunkte, sofern vorhanden.
InformationsquelleAutor der Antwort Martijn
Wenn Sie den Abstand zwischen dem Mittelpunkt der Kugel (da es sich um 3D-ich nehme an, du meinst Sphäre und nicht der Kreis) und die Linie sind, dann prüfen Sie, ob dieser Abstand kleiner als der radius, der wird den trick tun.
Kollision Punkt ist natürlich der nächste Punkt zwischen der Linie und die Kugel (die werden berechnet wenn Sie die Berechnung der Distanz zwischen Kugel und Linie)
Abstand zwischen einem Punkt und einer Linie:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
InformationsquelleAutor der Antwort Martin
In diesem Beitrag mit der circle line Kollision geprüft werden, durch überprüfen der Entfernung zwischen dem Kreis-Mittelpunkt und Punkt auf dem Liniensegment (Ipoint) , stellen Sie den Schnittpunkt zwischen der normalen N (Bild 2) von circle center-line segment.
(https://i.stack.imgur.com/3o6do.png)
Auf Bild 1 ist ein Kreis und eine Linie angezeigt, Vektor Einen Punkt zu Linie Startpunkt, Vektor, B-Punkt, Linie, Ende, Punkt, Vektor C Punkt zum Mittelpunkt des Kreises. Nun müssen wir finden Vektor E (ab Zeile Startpunkt zum Kreismittelpunkt) und dem Vektor D (von Zeile Startpunkt der Linie Endpunkt) diese Berechnung ist auf Bild 1.
(https://i.stack.imgur.com/7098a.png)
In Bild 2 sehen wir, dass der Vektor E ist, wird auf einem Vektor D durch das "Skalarprodukt" des Vektors E und der Einheitsvektor D, das Ergebnis des skalarprodukts ist Skalar Xp vertreten, dass die Entfernung zwischen dem start Punkt und Schnittpunkt (Ipoint) der Vektor N und Vektor-D.
Nächste Vektor X wird durch Multiplikation der Einheitsvektor D und Skalare Xp.
Nun müssen wir finden Vektor Z (Vektor Ipoint), ist es einfach, seine einfache addition der Vektor A (start Punkt auf der Linie) und der Vektor X. als Nächstes brauchen wir die Auseinandersetzung mit speziellen Fällen müssen wir prüfen, ist die Ipoint on line segment, falls nicht, müssen wir herausfinden, ist es Links oder rechts, verwenden wir vector nächsten, um zu bestimmen, welcher Punkt am nächsten ist Kreis.
(https://i.stack.imgur.com/p9WIr.png)
Wenn die Projektion Xp ist negativ Ipoint ist Links der Strecke, Vektor am nächsten ist gleich Vektor von line start Punkt, wenn die Projektion Xp größer ist dann die Größenordnung der Vektor D dann Ipoint ist rechts von der Linie segment dann am nächsten Vektor gleich Vektor der geraden-Endpunkts in jedem anderen Fall am nächsten Vektor gleich Vektor Z.
Nun, wenn wir am nächsten Vektor , den wir brauchen, um zu finden Vektor vom Mittelpunkt des Kreises zu Ipoint (dist Vektor), seine einfache, wir brauchen nur zu subtrahieren nächste Vektor vom Zentrum Vektor. Weiter nur prüfen, ob Vektor dist Größenordnung kleiner als der Kreisradius, wenn es dann stoßen Sie zusammen, wenn nicht gibt es keine Kollision.
(https://i.stack.imgur.com/QJ63q.png)
Ende, wir können wieder einige Werte für die Auflösung der Kollision , der einfachste Weg ist die Rückkehr überlappung der Kollision (subtrahieren radius von Vektor dist Größenordnung) und Rückgabe Achse der Kollision, dessen Vektor D. Auch Schnittpunkt ist der Vektor Z, wenn nötig.
InformationsquelleAutor der Antwort FunDeveloper89
Wenn die Linie die Koordinaten A. x, A. y-B. x, B. y, und die Kreise center ist C. x, C. y, dann ist die Zeilen-Formeln sind:
x = A. x * t + B. x * (1 - t)
y = A. y * t + B. y * (1 - t)
wobei 0<=t<=1
und der Kreis ist
(C. x - x)^2 + (C. y - y)^2 = R^2
wenn Sie ersetzen x und y Formeln der Zeile, in die Kreise Formel erhalten Sie einen zweiten, um die Gleichung von t und Ihre Lösungen sind die Schnittpunkte (falls vorhanden). Wenn Sie erhalten ein t, die kleiner als 0 oder größer als 1 ist, dann ist das keine Lösung, aber es zeigt, dass die Zeile "zeigen", um die Richtung des Kreises.
InformationsquelleAutor der Antwort Gábor Hargitai
Nur eine Ergänzung zu diesem thread...
Unten ist eine version des Codes geschrieben von pahlevan, aber für C#/XNA und aufgeräumt, ein wenig:
InformationsquelleAutor der Antwort Rob
InformationsquelleAutor der Antwort A.J.Bauer
Ich habe diese Funktion für iOS nach der Antwort
chmike
InformationsquelleAutor der Antwort Aqib Mumtaz
Hier ist eine Implementierung in Javascript. Mein Ansatz ist, zuerst konvertieren Sie die Zeile segment in eine unendliche Linie, dann finden Sie den Schnittpunkt(s). Von dort aus habe ich prüfen, ob die Stelle(N) gefunden werden auf der Linie segment. Der code ist gut dokumentiert, Sie sollten in der Lage sein zu Folgen zusammen.
Können Sie versuchen, den code hier auf dieser live-demo.
Der code stammt von meinem algorithmen repo.
InformationsquelleAutor der Antwort will.fiset
Diese Java Funktion gibt eine DVec2 Objekt. Es dauert eine DVec2 für den Mittelpunkt des Kreises, der radius des Kreises, und eine Linie.
InformationsquelleAutor der Antwort pahlevan
Andere in c# (Teil-Circle-Klasse).
Getestet und funktioniert wie ein Charme.
Erforderlich:
InformationsquelleAutor der Antwort Eric Ouellet
Kreis ist wirklich ein schlechter Kerl ist 🙂 Also ein guter Weg ist, um zu vermeiden, true Kreis, wenn Sie können. Wenn Sie das tun, Kollisionsprüfung für Spiele, die Sie gehen können, mit einigen Vereinfachungen und haben nur 3-dot-Produkte, und ein paar Vergleiche.
Ich nenne das den "Fetten Punkt" oder "thin-Kreis". seine Art eine ellipse mit null-radius in einer Richtung, die parallel zu einem segment. aber full radius in einer Richtung, die senkrecht zum segment
Zuerst würde ich prüfen, umbenennen und wechseln Koordinatensystem zu vermeiden übermäßige Daten:
Zweiten, index h in hvec2f bedeutet als Vektor müssen zugunsten horizontaler Operationen, wie dot()/det(). Was bedeutet, dass seine Komponenten werden in einer separaten xmm-Register, um zu vermeiden, mischen/hadd 'Ing/hsub' Ing. Und hier gehen wir, mit den meisten performante version der einfachste Kollisionserkennung für die 2D-Spiel:
Ich bezweifle, optimieren Sie weiter. Ich benutze es für neuronale Netzwerk-driven-car-Rennen Kollisionserkennung, zu verarbeiten Millionen iterationsschritte.
InformationsquelleAutor der Antwort xakepp35
Hier ist eine Lösung geschrieben, in golang. Die Methode ist ähnlich wie einige andere Antworten hier gepostet, aber nicht ganz das gleiche. Es ist einfach zu implementieren, und wurde getestet. Hier sind die Schritte:
Die Werte für A, B und C für die quadratische abgeleitet werden, hier, wo (n-et) - und (m-dt) sind die Gleichungen für die Linie die x-und y-Koordinaten, beziehungsweise. r ist der radius des Kreises.
Daher A = ee+dd, B = - 2(en +, - dm), und C = nn + mm - rr.
Hier ist der golang code für die Funktion:
Getestet habe ich es mit dieser Funktion, die bestätigt, dass die Lösung, die Punkte sind innerhalb des Liniensegment und dem Kreis. Es macht einen test-segment und kehrt es um die gegebenen Kreis:
Hier ist die Ausgabe des test:
Schließlich die Methode ist leicht erweiterbar auf den Fall von einem Strahl ab in einem Punkt, gehen durch die anderen und die Erweiterung auf infinity, durch die sich nur testen, wenn t > 0 oder t < 1, aber nicht beide.
InformationsquelleAutor der Antwort Steller