3

ccw (反時計回り) アルゴリズムを理解するのに問題があります。

int ccw (Point P0, Point P1, Point P2) {
    dx1 = P1.x - P0.x;
    dx2 = P2.x - P0.x;
    dy1 = P1.y - P0.y;
    dy2 = P1.y - P0.y;

    if (dy1 * dx2 > dy2 * dx1) return -1;
    if (dx1 * dy2 > dy1 * dx2) return 1;
    if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) return 1;
    if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) return -1;
    return 0;
}

このコードは、2 つの線が交差するかどうかを確認するために使用されます。

bool intersect (Vector2D l1, Vector2D l2) {
    return (((ccw(l1.start, l1.end, l2.start) * ccw(l1.start, l1.end, l2.end)) <= 0)
    && ((ccw(l2.start, l2.end, l1.start) * ccw(l2.start, l2.end, l1.start)) <= 0))
}

intersect 関数内のコードは理解できますが、ccw 関数内のコードはよくわかりません。

外積を使用しないのはなぜですか？

4

1 に答える 1

5

関数内のコードccwはかなりアドホックな方法で書かれていますが、クロス積の 2D バージョンと非常に非公式に呼ばれることがあるものを使用しています。2 つのベクトルの場合(dx1, dy1)、(dx2, dy2)その積は次のスカラー値として定義されます。

CP = dx1 * dy2 - dx2 * dy1;

(形式的に正しい用語では、CPは実際にはベクトルとの古典的な 3D 外積の符号付きの大きさです。) 明らかに、その値は単純にスカラー(ドット) 積であり、ベクトルの 1 つがその垂線に置き換えられています。(dx1, dy1, 0)(dx2, dy2, 0)

の値が正の場合、からまでCPの最短半径スイープは反時計回りになります。マイナスは時計回りのスイープを意味します。ゼロインは共線ベクトルを示します。(これはすべて、Y 軸が上を向き、X 軸が右を向いていることを前提としています。)(dx1, dy1)(dx2, dy2)CPCP

明らかに、CP > 0条件は条件と同等でdx1 * dy2 > dx2 * dy1あり、CP < 0と同等dx1 * dy2 < dx2 * dy1です。それはまさに、関数が最初の 2 つの sccwでチェックするものです。if

残りifの は、同一線上にある状況を扱っています。

ベクトルが反対方向を指している場合 (3 番目の によって検出されますif)、つまりとP0の間P1にP2ある場合、関数は常に を返し1、反時計回りの順序を示します。まあ、それはコード作成者が想定している慣習にすぎないと思います。

最後に、2 つのベクトルが同じ方向を指している場合、つまりセグメントのP0外側にある場合、決定はベクトルの長さに基づいて行われます (4 番目の)。が よりも近い場合、時計回りの順序が報告されます。そうではなく、が近い場合は、反時計回りの順序が報告されます。これは、コード作成者が想定している規則でもあります。P1-P2ifP1P2P0P2

そして、コードの残りの部分から判断すると、それは 2 つの線の交差に関するものではありません。2 つのセグメントの交差についてです。

于 2014-10-11T17:40:45.450 に答える