7

長方形が凹多角形と交差するかどうかを調べようとしています。私はこのアルゴリズムを見つけました：

double determinant(Vector2D vec1, Vector2D vec2){
    return vec1.x*vec2.y-vec1.y*vec2.x;
}

//one edge is a-b, the other is c-d
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
    double det=determinant(b-a,c-d);
    double t=determinant(c-a,c-d)/det;
    double u=determinant(b-a,c-a)/det;
    if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION;
    return a*(1-t)+t*b;
}

これを4回（上から右、上から左下、上から右下、下から右）実行すると、*（ポリゴンのすべてのエッジ）、長方形に凹面の一部またはすべてがあるかどうかが効果的かつ正確にわかります。中のポリゴン？そうでなければ、何が欠けているでしょうか？

ありがとう

4

3 に答える 3

13

このコードは、AB と CD の 2 つのセグメントの交点を見つけようとします。

これらの操作をどのように解釈するかに応じて、それがどのように行われているかを説明するさまざまな方法があります。

点 A の座標が (xa, ya)、B - (xb, yb) などであるとします。まあ言ってみれば

dxAB = xb - xa
dyAB = yb - ya
dxCD = xd - xc
dyCD = yd - yc

次の 2 つの線形方程式系

| dxAB dxCD |   | t |   | xc-xa |
|           | * |   | = |       |
| dyAB dyCD |   | u |   | yc-ya |

tとについて解けば、ライン AB (値) とライン CD (値)u上の交点の比例位置が得られます。これらの値は、ポイントが対応するセグメントに属している場合は の範囲内にあり、ポイントがセグメントの外側 (セグメントを含むライン上) にある場合はその範囲外にあります。tu[0, 1]

この連立一次方程式を解くために、よく知られているCramer の規則を使用できます。そのためには、行列式が必要です

| dxAB dxCD |
|           |
| dyAB dyCD |

これはまさにdeterminant(b - a, c - d)あなたのコードからのものです。（実際にはdeterminant(b - a, d - c)、ここにあるのは ですが、この説明の目的にとってはそれほど重要ではありません。投稿したコードは、何らかの理由で C と D を交換しています。以下の PS ノートを参照してください）。

また、行列式も必要になります

| xc-xa dxCD |
|            |
| yc-ya dyCD |

これはまさにdeterminant(c-a,c-d)あなたのコードからのものであり、

| dxAB xc-xa |
|            |
| dyAB yc-ya |

これはまさにdeterminant(b-a,c-a)です。

Cramer の規則に従ってこれらの行列式を分割するtとu、 と の値が得られます。これは、投稿したコードで行われていることとまったく同じです。

次に、コードは と の値をテストしt、uセグメントが実際に交差しているかどうか、つまり と の両方が範囲tにu属しているかどうかを確認し[0, 1]ます。もしそうなら、それは評価することによって実際の交点を計算しますa*t+b*(1-t)(同等に、それは を評価することができc*u+d*(1-u)ます)。(繰り返しますが、以下の PS ノートを参照してください)。

PSc - d元のコードでは、ポイント D と C は、コードが行うという意味で「交換」されていd - cます。しかし、符号に注意している限り、これはアルゴリズムの一般的な考え方には何の違いもありません。

a*(1-t)+t*bこの C 点と D 点の交換も、交点を評価するときに式が使用される理由です。通常、私の説明のように、そこに何かが表示されると予想されますa*t+b*(1-t)。（ただし、これについては疑問がありa*t+b*(1-t)ます。あなたのバージョンでもそこにあると思います。バグである可能性があります。）

PPSコードがチェックを忘れたdet == 0(または 0 に非常に近い) 場合の作成者。これは、セグメントが並列である場合に発生します。

于 2010-08-11T22:30:41.533 に答える
2

私は次のことがうまくいくと思います：

(1) for each e1 in rectangle_edges, e2 in polygon_edges
    (1.1) if edgeIntersection(e1,e2) != NO_INTERSECTION
        (1.1.1) return true
(2) if (max_polygon_x < max_rectangle_x) and (min_polygon_x > min_rectangle_x) and (max_polygon_y < max_rectangle_y) and (min_polygon_y > min_rectangle_y)
    (2.1) return true
(2) return false

編集：ポリゴンが長方形の内側にあるかどうかのチェックを追加しました。

于 2010-08-11T22:12:33.010 に答える
0

ざっと見た限りでは、2 つの線分が交差するかどうか、交差する場合は交点の座標を判断しようとします。

いいえ、四角形と多角形が交差しているかどうかを判断するだけでは十分ではありません。多角形が完全に四角形の内側にある場合や、その逆の場合を見逃す可能性があるからです。

于 2010-08-11T22:56:31.190 に答える