ライン・ラインの交点C++を計算する最も一般的な方法は？

Question

there is no way to compute line line intersection using boost::geometryと思われますが、C++で最も一般的な方法は何ですか？

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

P.S.：

は、私はそれが可能かどう速く、それは次のように2つの異なる機能することができ、2Dで2つの無限ラインの交点のアルゴリズムを必要とします私は本当にホイールの発明を避けようとしていますので、いくつかのライブラリを使用するように傾けてください。

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を見つけることができます。ページ146から

第5章では、以降C.例コードで...

注2D線の交点でもある3Dラインの最も近い点を見つける方法について説明します、平行線の彼らの注意しますゼロエラーで割り切れることがあります。暗黙の形で

Answer 3

エクスプレスパラメトリック形式のラインの一つとその他：

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

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

関係の直線性によっては、あなたがtを得る。このことから

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

を持っている、とtから交差点の座標。

合計15回、6回の乗算、1回の除算が必要です。

縮退は、S1 == S0で示され、線が平行であることを意味する。実際には、切り捨てエラーなどの理由で座標が正確ではない可能性があるため、0と等しいかどうかのテストが失敗する可能性があります。回避策は、テストを検討することです。µの場合は、テストを検討することです。の場合は、テストを検討します。

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を使用しています。私はmain関数に小さなテストケースを入れます。

2つのポイントを属性とするクラスLineを定義します。

クロス積は、2本の線が交差しているかどうかを知る簡単な方法です。 2Dでは、2D平面の法線ベクトル上の外積の投影である垂れ下がりドットプロダクト（perp関数を参照）を計算することができます。それを計算するには、各行の方向ベクトルを取得する必要があります（getVectorメソッドを参照）。

2Dでは、perpドット積とパラメトリック方程式を使用して2つの線の交点を得ることができます。私は説明hereを見つけた。

intersect関数は、2つの線が交差するかどうかを確認するブール値を返します。交差する場合は、参照によって交点を計算します。

#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：詳細外積とPERP内積+上のあなたがリンクする、またはライブラリのための勧告を求めている場合（トピックオフ）tol引数