Najczęstszy sposób obliczania przecięcia linii między wierszami C++?

Question

Wydaje się there is no way to compute line line intersection using boost::geometry, ale zastanawiam się, jaki jest najczęstszy sposób to zrobić w C++?

potrzebne algorytmy przecięcia obu nieskończonych linii w 2D, jeśli będzie szybciej może mieć dwie różne funkcje, takie jak:

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

P.S. Naprawdę staram się unikać wynalezienia koła, więc pochyl się, żeby użyć jakiejś biblioteki.

Answer 1

Ten kod powinien zadziałać. Możesz być w stanie zoptymalizować go trochę:

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

najlepsze algorytmy, które znalazłem na znalezienie przecięcie linii są w: Real Time Collision Detection by Christer Ericson, egzemplarz książki można znaleźć here.

Rozdział 5 ze str 146 r opisuje, jak znaleźć najbliższy punkt linii 3D, który jest również przejście linii 2D ... z przykładowym kodem w C

Uwaga: uważaj równoległych linii, oni może powodować dzielenie przez zero błędów.

Answer 3

ekspresowe jedna z linii w postaci parametrycznej a drugi w postaci niejawnej:

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

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

Przez liniowość relacji, trzeba

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

Od tego masz t iz t współrzędne skrzyżowania.

Zajmuje w sumie 15 dodawania, 6 mnożeń i jeden podział.

Degeneracja jest oznaczona jako S1 == S0, co oznacza, że ​​linie są równoległe. W praktyce współrzędne mogą nie być dokładne z powodu błędów skracania lub innych, więc test równości do 0 może się nie udać. Aby obejść ten problem, należy rozważyć test dla małego.

Answer 4

Być może powszechnym sposobem jest przybliżenie nieskończoności? Z mojej biblioteki przy użyciu boost :: Geometria:

// 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); 

następnie można przetestować, czy „” linie przecinają się tak:

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

extendSeg() prostu rozszerza segment w obu kierunkach przez daną ilościach.

---

Także pamiętać - aby wspierać nieskończony linia arytmetycznej z punkt typu powinny również wspierać wartość nieskończoną. Jednak tutaj zakłada się, że szukasz rozwiązania numerycznego!

Answer 5

Możesz wypróbować mój kod, używam boost::geometry i umieszczam małą próbkę w głównej funkcji.

Definiuję linię klasy z dwoma punktami jako atrybutami.

Produkt krzyżowy to bardzo prosty sposób sprawdzenia, czy dwie linie przecinają się. W 2D można obliczyć produkt perp dot (patrz funkcja perp), który jest rzutowaniem iloczynu krzyżowego na normalnym wektorze płaszczyzny 2D. Aby to obliczyć, musisz uzyskać wektor kierunkowy dla każdej linii (patrz metoda getVector).

W 2D można uzyskać punkt przecięcia dwóch linii za pomocą produktu perp dot i parametrycznego równania linii. Znalazłem wyjaśnienie here.

Funkcja intersect zwraca wartość boolowską, aby sprawdzić, czy dwie linie przecinają się. Jeśli się przecinają, oblicza punkt przecięcia przez odniesienie.

#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: więcej szczegółów na iloczynu i sprawca iloczynu skalarnego + Delete tol argumentu (off topic)