1

n 個の線分が与えられたときにすべての交点を見つけるアルゴリズムを探しています。以下は、 http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdfからの疑似コードです。

入力 S[1 .. n] は線分の配列です。label[i] は、i 番目の左端のエンドポイントのラベルです。

sort the endpoints of S from left to right
create an empty label sequence
for i ← 1 to 2n
    line ← label[i]
    if isLeftEndPoint[i]
        Insert(line)
        if Intersect(S[line], S[Successor(line)])
            return TRUE
        if Intersect(S[line], S[Predecessor(line)])
            return TRUE
    else
        if Intersect(S[Successor(line)], S[Predecessor(line)])
            return TRUE
        Delete(label[i])

return FALSE

以下に設定されたラインにアルゴリズムを適用します。1 つの交点のみがチェックされます。他の 2 つの交点の存在を知るにはどうすればよいですか? ここに画像の説明を入力

  1. 行[1]が入ります
  2. line[2] が入り、line[1] と line[2] の交点がチェックされます。
  3. line[3] が入り、line[2] と line[3] の交点がチェックされます。
  4. line[4] が入り、line[4] と line[1] の交点がチェックされます。交差点 A が見つかりました。
  5. line[4] が終了し、何もチェックされません。
  6. line[1] が終了し、何もチェックされません。
  7. line[2] が終了し、何もチェックされません。
  8. line[3] が終了し、何もチェックされません。
4

1 に答える 1

1

標準直線方程式 Ax+By=C

等式の標準直線で定義される直線の傾き(m)は

m = -(A/B)

点-勾配線方程式 y-y1=m(x-x1)

m = (-A/B) をポイント-スロープ ライン方程式 y2-y1 = (A/-B)*(x2-x1) に代入します。

(y2-y1)/(x2-x1) = A/-B

したがって：

A = y2-y1
B = x1-x2 C = Ax+By

x = (C-By)/A

y = (C-Ax)/B

方程式 A1x1+B1y1=C1 と A2x2+B2y2=C2 の 2 つの直線が与えられます。
次に、線の交点は、
A1x+B1y-C1 = A2x+B2y-C2となる点によって指定されます。

A1x+B1y=C1
A2x+B2y=C2

A1B2x+B1B2y=B2C1 (最初の式に B2 を掛ける)
A1B2x+B1B2y-B2C1=0

A2B1x+B1B2y=B1C2 (第 2 式に B1 を掛ける)
A2B1x+B1B2y-B1C2=0

2 つの式
A1B2x+B1B2y-B2C1=A2B1x+B1B2y-B1C2
A1B2x+B1B2y-B2C1-A2B1x-B1B2y+B1C2=0
A1B2x-B2C1-A2B1x+B1C2=0
A1B2x-A2B1x=B2C1-B1C2
x(A2B1)2-A =B2C1-B1C2

x = (B2C1-B1C2)/A1B2-A2B1

A1x+B1y=C1
A2x+B2y=C2

A1A2x+A2B1y=A2C1 (最初の式に A2 を掛ける)
A1A2x+A2B1y-A2C1=0

A1A2x+A1B2y=A1C2 (第 2 式に A1 を掛ける)
A1A2x+A1B2y-A1C2=0

2 つの方程式を等しくする

A1A2x+A2B1y-A2C1=A1A2x+A1B2y-A1C2
A1A2x+A2B1y-A2C1-A1A2x-A1B2y+A1C2=0
A1C2-A2C2=A1B2y-A2B1y
A1B2y-A2B1y=A1C2-A2C2y (
A1B2-A2B1)=2C1C2y
A1B2-A2B1)=A1C2-A2C1
y = (A1C2-A2C1)/(A1B1-A2B1)

y と x の分母は同じなので、分母 = A1B1-A2B1

したがって：

x = (B2C1-B1C2)/分母
y = (A1C2-A2C1)/分母

これらは、点 (x1, y1)、(x2, y2)
および (x3, y3)、(x4, y4)との 2 つの直線の交点の x および y 座標です。

線分の場合は同じですが、x または y 座標が両方の線分にあることを確認する必要があります。つまり、小さい値を持つ両方のセグメントの x 座標と大きい値を持つ両方のセグメントの x 座標の間を意味します。

これは、セグメントが交差する場合は true を返し、交差しない場合は false を返す C++ プログラムです。セグメントが交差する場合、変数 i に交点が格納されます。

struct Point
{
    float x, y;
};

//p1 and p2 are the points of the first segment
//p3 and p4 are the points of the second segment
bool intersection(Point p1, Point p2, Point p3, Point p4, Point &i)
{
    float max1; //x-coordinate with greater value in segment 1
    float min1; //x-coordinate with lesse value in segment 1
    float max2; //x-coordinate with greater value in segment 2
    float min2; //x-coordinate with lesser value in segment 2
    float A1 = p2.y - p1.y;
    float B1 = p1.x - p2.x;
    float C1 = A1 * p1.x + B1 * p1.y;
    float A2 = p4.y - p3.y;
    float B2 = p3.x - p4.x;
    float C2 = A2 * p3.x + B2 * p3.y;
    float denom = A1 * B2 - A2 * B1;

if (denom == 0.0) //When denom == 0, is because the lines are parallel
    return false; //Parallel lines do not intersect

i.x = (C1 * B2 - C2 * B1) / denom;
i.y = (A1 * C2 - A2 * C1) / denom;

if (p1.x > p2.x)
{
    max1 = p1.x;
    min1 = p2.x;

}
else
{
    max1 = p2.x;
    min1 = p1.x;
}

if (p3.x > p4.x)
{
    max2 = p3.x;
    min2 = p4.x;

}
else
{
    max2 = p4.x;
    min2 = p3.x;
}

//check if x coordinate is in both segments
if (i.x >= min1 && i.x <= max1 &&
    i.x >= min2 && i.x <= max2)
    return true;
return false; //Do no intersect, intersection of the lines is not between the segments

}

これで、すべてのセグメントをループで比較し、交点を配列に保存するだけで済みます。

于 2015-11-23T07:36:53.027 に答える