Häufigste Methode zur Berechnung der Linienkreuzung C++?

Question

Scheint there is no way to compute line line intersection using boost::geometry, aber ich frage mich, was ist der gängigste Weg, es in C++ zu tun?

Ich brauche Schnittalgorithmen für zwei unendliche Linien in 2D, wenn es schneller sein, wird es zwei verschiedene Funktionen wie sein können:

bool line_intersection(line,line); 
point line_intersetion(line,line); 

P. S. Ich versuche wirklich, eine Rad-Erfindung zu vermeiden, also neige dazu, eine Bibliothek zu benutzen.

Answer 1

Dieser Code sollte für Sie arbeiten. können Sie in der Lage sein, es ein wenig zu optimieren:

template <class Tpoint> 
    Tpoint line<Tpoint>::intersect(const line& other) const{ 
     Tpoint x = other.first - first; 
     Tpoint d1 = second - first; 
     Tpoint d2 = other.second - other.first; 

     auto cross = d1.x*d2.y - d1.y*d2.x; 

     auto t1 = (x.x * d2.y - x.y * d2.x)/static_cast<float>(cross); 
     return first + d1 * t1; 

    } 

Answer 2

Die besten Algorithmen, die ich für die Suche nach den Schnittpunkt der Linien in sind gefunden haben: Real Time Collision Detection by Christer Ericson, kann eine Kopie des Buches here finden.

Kapitel 5 ab Seite 146 ff beschrieben, wie den nächsten Punkt von 3D-Linien zu finden, die von 2D-Linien auch der Kreuzungspunkt ist ... mit Beispielcode in C

Hinweis: passen sie von parallelen Linien, sie kann durch Null Fehler verursachen.

Answer 3

Express eine der Leitungen in parametrischer Form und die andere in impliziter Form:

X = X0 + t (X1 - X0), Y= Y0 + t (Y1 - Y0) 

S(X, Y) = (X - X2) (Y3 - Y2) - (Y - Y2) (X3 - X2) = 0 

Durch Linearität der Beziehungen, Sie haben

S(X, Y) = S(X0, Y0) + t (S(X1, Y1) - S(X0, Y0)) = S0 + t (S1 - S0) = 0 

Daraus Sie t erhalten, und von t die Koordinaten der Kreuzung.

Es werden insgesamt 15 Additionen, 6 Multiplikationen und eine einzelne Division benötigt.

Die Entartung wird durch S1 == S0 angezeigt, was bedeutet, dass die Linien parallel sind. In der Praxis sind die Koordinaten möglicherweise aufgrund von Abschneidefehlern oder anderen nicht exakt, so dass der Test auf 0 fehlschlägt. Eine Abhilfe ist der Test

|S0 - S1| <= µ |S0| 

für kleine µ zu betrachten.

Answer 4

Vielleicht ist ein gemeinsamer Weg, die Unendlichkeit zu approximieren? Aus meiner Bibliothek mit boost :: Geometrie:

// prev and next are segments and RAY_LENGTH is a very large constant 
// create 'lines' 
auto prev_extended = extendSeg(prev, -RAY_LENGTH, RAY_LENGTH); 
auto next_extended = extendSeg(next, -RAY_LENGTH, RAY_LENGTH); 
// intersect! 
Points_t isection_howmany; 
bg::intersection(prev_extended, next_extended, isection_howmany); 

dann könnte man prüfen, ob die ‚Linien‘ wie folgt schneiden:

if (isection_howmany.empty()) 
    cout << "parallel"; 
else if (isection_howmany.size() == 2) 
    cout << "collinear"; 

extendSeg() erstreckt sich einfach das Segment in beiden Richtungen durch die angegebenen Beträge.

---

Auch bedenken - eine unendliche Linie Arithmetik des Punkt Typen unterstützen sollte auch einen unendlichen Wert unterstützen. Aber hier ist die Annahme, dass Sie nach einer numerischen Lösung suchen!

Answer 5

Sie können meinen Code versuchen, ich verwende boost::geometry und ich legte einen kleinen Testfall in die Hauptfunktion.

Ich definiere eine Klasse Linie mit zwei Punkten als Attribute.

Cross-Produkt ist sehr einfach zu wissen, ob zwei Linien schneiden. In 2D können Sie das Perp-Punkt-Produkt berechnen (siehe perp Funktion), das eine Projektion des Kreuzprodukts auf den Normalenvektor der 2D-Ebene ist. Um es zu berechnen, müssen Sie einen Richtungsvektor jeder Linie erhalten (siehe getVector Methode).

In 2D können Sie den Schnittpunkt von zwei Linien mit Hilfe von Perp-Punkt-Produkt und parametrische Gleichung der Linie erhalten. Ich fand eine Erklärung here.

Die Funktion intersect gibt einen booleschen Wert zurück, um zu prüfen, ob sich zwei Linien schneiden. Wenn sie sich schneiden, berechnet sie den Schnittpunkt als Referenz.

#include <cmath> 
#include <iostream> 
#include <boost/geometry/geometry.hpp> 
#include <boost/geometry/geometries/point_xy.hpp> 

namespace bg = boost::geometry; 

// Define two types Point and Vector for a better understanding 
// (even if they derive from the same class) 
typedef bg::model::d2::point_xy<double> Point; 
typedef bg::model::d2::point_xy<double> Vector; 

// Class to define a line with two points 
class Line 
{ 
    public: 
    Line(const Point& point1,const Point& point2): p1(point1), p2(point2) {} 
    ~Line() {} 

    // Extract a direction vector 
    Vector getVector() const 
    { 
     Vector v(p2); 
     bg::subtract_point(v,p1); 
     return v; 
    } 

    Point p1; 
    Point p2; 
}; 

// Compute the perp dot product of vectors v1 and v2 
double perp(const Vector& v1, const Vector& v2) 
{ 
    return bg::get<0>(v1)*bg::get<1>(v2)-bg::get<1>(v1)*bg::get<0>(v2); 
} 

// Check if lines l1 and l2 intersect 
// Provide intersection point by reference if true 
bool intersect(const Line& l1, const Line& l2, Point& inter) 
{ 
    Vector v1 = l1.getVector(); 
    Vector v2 = l2.getVector(); 

    if(std::abs(perp(v1,v2))>0.) 
    { 
    // Use parametric equation of lines to find intersection point 
    Line l(l1.p1,l2.p1); 
    Vector v = l.getVector(); 
    double t = perp(v,v2)/perp(v1,v2); 
    inter = v1; 
    bg::multiply_value(inter,t); 
    bg::add_point(inter,l.p1); 
    return true; 
    } 
    else return false; 
} 

int main(int argc, char** argv) 
{ 
    Point p1(0.,0.); 
    Point p2(1.,0.); 
    Point p3(0.,1.); 
    Point p4(0.,2.); 
    Line l1(p1,p2); 
    Line l2(p3,p4); 

    Point inter; 
    if(intersect(l1,l2,inter)) 
    { 
    std::cout<<"Coordinates of intersection: "<<inter.x()<<" "<<inter.y()<<std::endl; 
    } 

    return 0; 
} 

EDIT: weitere Einzelheiten über Kreuzprodukt und perp Skalarprodukt + löschen tol Argument (off topic)