21

stackowerflow では、線分の交点について多くの質問が寄せられていますが、もう 1 つ質問があります。申し訳ありませんが、交点の計算方法を理解するのに助けが必要です. ここでいくつかの質問を読み、他のウェブサイトでいくつかの例を見ましたが、まだ混乱していてわかりません! 物事がどのように機能するかを知らずに、コードをコピーして貼り付けるのは好きではありません。

これまでのところ、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
4

3 に答える 3

31

あなたが示す最初のコードは、ベクトルのクロス積に基づいています。これについては、こちらで説明されています。非常に詳細に。

IMO、それを理解する簡単な方法は、連立方程式を解くことです。最初に線を全体的に見てから、それらからセグメントを切り取ります。以下では、特定のセグメント((x1, x2), (y1, y2))と((x3, x4), (y3, y4)).

  1. いずれかの線が垂直 (x1 == x2またはx3 == x4) になっているかどうかを確認します。

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

    b. 両方とも垂直 との場合、 とが重なっているx1 == x3かどうかを確認します。(y1, y2)(y3, y4)

    c. 1 つだけが垂直である場合 (たとえば、最初の 1 つ)、2 番目の線の方程式を作成し (以下に概説するように)、(2 番目の線の方程式に代入することによって) 2 つの線が交差する点を見つけ、x1この点が両方のセグメント内 (手順 5 と同様)。

    d. そうでない場合は、続行します。

  2. 点の座標を使用して、線の方程式を形式で作成しますy = a*x + b(ここのように)。

    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 つのポイントでさえあります)。注: フロートを使用している場合は、少しトリッキーになりますが、これは無視した方がよいと思います。a1 = a2次と同等かどうかをチェックする整数のみがある場合：

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

  4. 線が平行でない場合。交点は、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). はいの場合、あなたの線は交差します!

于 2013-05-01T07:09:48.730 に答える
5

私は本当に@sashkelloの答えであり、ベクトル実装よりも直感的で説明しやすいことがわかりました。特に、この種のコードをコード ベースに追加する場合。

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があなたのためです. :)

于 2016-12-21T19:34:34.537 に答える
1 
public void fixData()
{
    slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
    yInt = p1.getY() - slope * p1.getX();
    xInt = (-yInt) / slope;
}
于 2016-11-07T15:57:10.337 に答える