最常用的计算线条交点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线的最近点，这也是二维线的交叉点......与示例代码中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

也许一种常见的方法是近似无穷大？从使用boost ::几何我的图书馆：

// 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，我在主函数中放了一个小测试用例。

我定义了一个具有两个点作为属性的类。

交叉产品是知道两条线是否相交的非常简单的方法。在2D中，您可以计算perp dot产品（参见perp函数），该产品是2D乘法平面法向量上叉积的投影。要计算它，你需要得到每一行的方向矢量（见getVector方法）。

在2D中，可以使用perp点积和线的参数方程得到两条线的交点。我找到了一个解释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; 
} 

编辑：跨产品和PERP积+详细删除tol参数（题外话）