Наиболее распространенный способ вычисления пересечения линий линии C++?

Question

Похоже, there is no way to compute line line intersection using boost::geometry, но мне интересно, какой самый распространенный способ сделать это на C++?

мне нужно перекрестков алгоритмы для двух бесконечных линий в 2D, если это будет быстрее, это может быть две различные функции, как:

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

P.S. Я действительно стараюсь избегать изобретения на колесах, поэтому склоняюсь к использованию какой-либо библиотеки.

Answer 1

Этот код должен работать на вас. Вы можете быть в состоянии оптимизировать его немного:

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

Лучшие алгоритмы, которые я нашел для нахождения пересечения линий находятся в: Real Time Collision Detection by Christer Ericson, копию книги можно найти here.

Глава 5 со страницы 146 и далее описывает, как найти ближайшую точку 3D-линии, которая также является точкой пересечения 2Д ... с примерами кода на C.

Примечание: остерегайтесь параллельных линий, они может привести к делению на нулевые ошибки.

Answer 3

Экспресс одна из линий в параметрической форме, а другая в неявном виде:

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

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

По линейности отношений, то есть

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

От этого вы получаете t и от t координаты пересечения.

Требуется в общей сложности 15 добавлений, 6 умножений и один разрыв.

Вырождение указывается S1 == S0, что означает, что линии параллельны. На практике координаты могут быть неточными из-за ошибок усечения или других, поэтому проверка на равенство 0 может потерпеть неудачу. Обойти это можно рассматривать Тест

|S0 - S1| <= µ |S0| 

для малого µ.

Answer 4

Возможно, общий способ заключается в приближении бесконечности? Из моей библиотеки с использованием повышение :: геометрии:

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

, то вы можете проверить, пересекаются ли «линии», как это:

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

extendSeg() просто расширяет сегмент в обоих направлениях по данной суммы.

---

иметь также в виде - для поддержки бесконечной линии арифметики точки типа должен также поддерживать в бесконечном значении. Однако здесь предполагается, что вы ищете численное решение!

Answer 5

Вы можете попробовать мой код, я использую boost::geometry, и я положил небольшой тестовый пример в основную функцию.

Я определяю класс Line с двумя точками в качестве атрибутов.

Крест продукта - очень простой способ узнать, пересекаются ли две линии. В 2D вы можете вычислить продукт точки перпа (см. Функцию perp), который представляет собой проекцию поперечного произведения на нормальный вектор двумерной плоскости. Чтобы вычислить его, вам нужно получить вектор направления каждой строки (см. Метод getVector).

В 2D вы можете получить точку пересечения двух линий, используя продукт точки перпа и параметрическое уравнение линии. Я нашел объяснение here.

Функция intersect возвращает логическое значение, чтобы проверить, пересекаются ли две линии. Если они пересекаются, он вычисляет точку пересечения по ссылке.

#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: более подробно на перекрестном продукте и ПЭРП скалярного произведения + удалить tol аргумент (не по теме)