線分間の交点の計算

Question

ここでは線分間の交差点について、stackowerflowで多くの質問があります。申し訳ありませんが、交差点を計算する方法を理解するためには助けが必要です。私はここでいくつかの質問を読んで、他のウェブサイトのいくつかの例を見てきましたが、私はまだ混乱しており、それを手に入れません！私は物事の仕組みがなくてもコードをコピー＆ペーストするのは好きではありません。

これまでAx、Ay、Bx、By、Cx、Cy、Dx、Dyのような各線分の点を比較するつもりです。誰かが私が計算しようとしていることを私に説明してもらえますか、交差点があれば計算の結果はどうなりますか？

これは私が見たサンプルコードの1つです。線が交差するかどうかを知るために、交差点は必要ないと思います。

public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { 
    double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); 
    if (denom == 0.0) { // Lines are parallel. 
    return null; 
    } 
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom; 
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom; 
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) { 
     // Get the intersection point. 
     return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1))); 
    } 

    return null; 
    } 

このコード例のように中央値を計算する必要がありますか？

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on 

Answer 1

あなたが表示されたコードの最初の部分は、ここでHow do you detect where two line segments intersect?詳細に説明したベクトルのクロス積に基づいています。

IMO、これを理解するためのより簡単な方法は、方程式系を解くことです。最初に線を一般的に見てから、線分を切ります。以下では、与えられたセグメント((x1, x2), (y1, y2))と((x3, x4), (y3, y4))の表記を使用します。

1. チェック線のいずれかが垂直である場合（x1 == x2又はx3 == x4）。

   a。両方が垂直でx1 != x3の場合、交差点はありません。

   b。両方とも垂直でx1 == x3の場合は、(y1, y2)と(y3, y4)が重複していないかどうかを確認してください。

   c。もし1つだけが垂直（例えば最初のもの）ならば、2行目の方程式を作成し（2行目の方程式にx1を代入することによって）、2つの線が交差する点を見つけて、両方のセグメント内にあります（手順5と同様）。

   d。そうでない場合は、進みます。

2. 形y = a*x + bのような線方程式を構築するために点座標を使用します（hereなど）。

   a1 = (y2-y1)/(x2-x1) 
   b1 = y1 - a1*x1 
   a2 = (y4-y3)/(x4-x3) 
   b2 = y3 - a2*x3 
   

3. 線が平行（同じ傾きa）であるかどうかを確認。はいの場合は、それらが同じインターセプトbを持っているかどうかを確認してください。はいの場合は、1Dセグメント(x1, x2)と(x3, x4)が重複していないか確認してください。はいの場合、セグメントは重複します。線が平行である場合はあいまいな場合があります。それらが重なっている場合は、交差点と見なすことができます（端が接触している場合でも1つのポイントになることがあります）。注：浮動小数点数を使って作業している場合は、少しトリッキーですが、これを無視したいと思います。行が平行でない場合

   if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3)) 
   

4. ：ケースでは、a1 = a2と等価であるかどうかをチェックする整数のみを持っています。交差点は、2つの線を表す方程式系の解と等価である。実際に交差するy = a1*x + b1とy = a2*x + b2は、基本的にこれらの式の両方が成り立つことを意味します。 2つの右辺を等しくすることによってこのシステムを解くと、交差点が得られます。実際には、あなたは（それを描き、あなたはなぜ表示されます）の交点の座標だけxが必要になります。

   x0 = -(b1-b2)/(a1-a2) 
   

5. 最終ステップは、交点x0は、両方のセグメント内にあるかどうかを確認することです。つまり、min(x1, x2) < x0 < max(x1, x2)とmin(x3, x4) < x0 < max(x3, x4)です。はいの場合、あなたの線は交差します！ sashkelloの答え@

Answer 2

public void fixData() 
{ 
    slope = (p2.getY() - p1.getY())/(p2.getX() - p1.getX()); 
    yInt = p1.getY() - slope * p1.getX(); 
    xInt = (-yInt)/slope; 
} 

Answer 3

私は本当に、それを見つけるには、ベクトルの実装よりも説明することが、より直感的かつ容易になります。特に、この種のコードをコードベースに追加する場合。

私は、あなたがJavaのLine2Dヘルパーメソッドを利用できると言ってそれに注意します。ザ・だけ引く

Line2D.linesIntersect(double x1, double y1, 
         double x2, double y2, 
         double x3, double y3, 
         double x4, double y4) 

は、それは彼らがちょうど（エンドポイントとライン自体の両方に）触れている場合でも、交差するようにセグメントを検討する必要があることです。

たとえば、以下の行はポイント（1,1）を共有するため、交差していると見なされます。

L1 = [(0,0),(1,1)] 
L2 = [(1,1),(2,3)] 

問題が発生した場合は、ポイントが等しいかどうかを確認するために4つのチェックを追加できます。

ポイント内にポイントが落ちることが懸念されている場合は、もう少し作業が必要になるため、アルゴリズム自体をチェックすることができます。

これらのエッジケースのどれもあなたに影響しない場合は、Line2D.linesIntersectです。 :)