Einführung
Sehr oft wird es bei der Entwicklung von Spielen notwendig, den Schnittpunkt von Linien, Segmenten, Strahlen usw. zu finden. Wie Sie dies auf einfachste Weise implementieren, erfahren Sie in diesem Artikel.
Beliebte Methoden und ihre Kritik
Vielleicht erinnern sich viele an einen Weg aus der Schulalgebra - Gleichungen aus zwei geraden Linien zu erstellen, ihre rechten Seiten gleichzusetzen, x zu finden und es in die Gleichung einer geraden Linie zu setzen, um y zu finden ( Weitere Details hier ).
Diese Methode wird jedoch beim Schreiben von Code ziemlich umständlich (vielleicht lesen Sie diesen Artikel deshalb gerade). Außerdem ist sie nicht universell: Wenn eine der Geraden parallel zur Y-Achse verläuft, erhalten wir bei der Berechnung der Steigung einen Fehler durch Null, und wir müssen Registrieren Sie einen Code für diesen Fall. Wenn zwei Zeilen parallel sind, müssen Sie auch an der Bearbeitung dieses Falls basteln. Ein solcher Code wird lang und hässlich.
Auf der Suche nach einer eleganteren Lösung für dieses Problem bin ich auf sehr interessante Wege gestoßen, die auf der Vektormultiplikation basieren (habr.com/ru/post/267037 ) und Ray Casting ( ru.wikipedia.org/wiki/Ray_casting#Concept ). Aber meiner Meinung nach sind sie rechnerisch unnötig komplex. Deshalb präsentiere ich Ihrer Aufmerksamkeit (und Kritik) meine Methode.
Meine Art
Aufgabe
Die Koordinaten zweier Segmente sind angegeben. Sie müssen herausfinden, ob und an welchem Punkt sich die Segmente schneiden. Zu diesem Zweck schreiben wir eine Funktion.
Entscheidung
Legende zur Vermeidung von Missverständnissen: a - Vektor a, a (y) - Projektion des Vektors a auf die Y-Achse, a {x1, y1} - Vektor a, angegeben durch die Koordinaten x1, y1.
Stellen wir unsere Segmente in Form von zwei Vektoren dar: a {x2-x1; y2-y1} und b {x3-x4; y3-x4}. Beachten Sie, dass der Vektor b entgegengesetzt zu der erwarteten Richtung ist. Lassen Sie uns einen Vektor c {x3-x1; y3-y1}. Man beachte, dass a * k + b * n = c ist, wobei k, n einige Koeffizienten sind. So erhalten wir ein Gleichungssystem:
a (x) * k + b (x) * n = c (x)
a (y) * k + b (y) * n = c (y)
Unsere Aufgabe ist darauf beschränkt, diese Koeffizienten zu finden (Um die Wahrheit zu sagen, es reicht aus, nur einen von ihnen zu finden).
Ich schlage vor, beide Seiten der unteren Gleichung mit q = -a (x) / a (y) zu multiplizieren. Nachdem wir zwei Gleichungen hinzugefügt haben, werden wir k sofort los. Das Finden von n wird auf das Lösen einer gewöhnlichen linearen Gleichung reduziert. Es ist wichtig zu beachten, dass n möglicherweise keine Lösung hat.
Der aufmerksame Leser wird feststellen, dass bei a (y) = 0 eine Fehlermeldung angezeigt wird. Schreiben wir die Verzweigung in der Phase, in der ein (y) gefunden wird. Dieser Fall ist noch einfacher, weil wir sofort eine Gleichung mit einem Unbekannten erhalten.
Ich empfehle, n selbst zu drucken, damit klarer wird, woher der folgende Code stammt.
Wenn Sie n kennen, können Sie den Schnittpunkt finden. Dazu subtrahieren wir den Vektor b * n von der Koordinate des Punktes (x3, y3).
Etwas zusammensetzen
float dot[2]; //
bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
float n;
if (y2 - y1 != 0) { // a(y)
float q = (x2 - x1) / (y1 - y2);
float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; } // c(x) + c(y)*q
float fn = (x3 - x1) + (y3 - y1) * q; // b(x) + b(y)*q
n = fn / sn;
}
else {
if (!(y3 - y4)) { return 0; } // b(y)
n = (y3 - y1) / (y3 - y4); // c(y)/b(y)
}
dot[0] = x3 + (x4 - x3) * n; // x3 + (-b(x))*n
dot[1] = y3 + (y4 - y3) * n; // y3 +(-b(y))*n
return 1;
}Diese Funktion nimmt die Koordinaten der Scheitelpunkte und gibt den Wert 1 zurück, wenn sich die geraden Linien der Segmente (nämlich gerade Linien) schneiden, andernfalls 0. Wenn Sie die Koordinaten der Scheitelpunkte benötigen, können Sie sie aus dem Array dot [] übernehmen.
Wichtig: Wenn zwei zusammenfallende Linien eingeführt werden, zeigt der Algorithmus keinen Schnittpunkt an. Der Algorithmus findet den Schnittpunkt der Linien, auf denen die Liniensegmente liegen, sodass der Punkt möglicherweise außerhalb des Segments liegt (den Sie in Ihrem Code einchecken müssen).
Wenden wir die Funktion an:
int main() {
if (cross(1,1,7,2, 7,3,5,6)) {
std::cout << dot[0] << " " << dot[1] << std::endl;
}
else {
std::cout<<"Not cross!"<<std::endl;
}
return 0;
}Nachwort
Obwohl ich beim Googeln meines Problems nicht auf diese Methode gestoßen bin und den Algorithmus selbst entwickelt habe, gebe ich nicht vor, vollständig originell (und korrekt) zu sein. Willkommen zu den Kommentaren!