12

4 つの 2D ポイントの凸包を計算するアルゴリズムが欲しいです。一般化された問題のアルゴリズムを見てきましたが、4 点の簡単な解決策があるのだろうかと思います。

4

8 に答える 8

20

3 つの点を取り、それらの三角形が時計回りか反時計回りかを判断します。

triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)

右手座標系の場合、この値は ABC が反時計回りの場合は正、時計回りの場合は負、同一線上にある場合はゼロになります。ただし、方向が相対的であるため、次の例は左手座標系でも同様に機能します。

4 番目の点を含む 3 つの三角形の比較可能な値を計算します。

triangle_ABD= (A.y-B.y)*D.x + (B.x-A.x)*D.y + (A.x*B.y-B.x*A.y)
triangle_BCD= (B.y-C.y)*D.x + (C.x-B.x)*D.y + (B.x*C.y-C.x*B.y)
triangle_CAD= (C.y-A.y)*D.x + (A.x-C.x)*D.y + (C.x*A.y-A.x*C.y)

{ABD,BCD,CAD} の 3 つすべてが ABC と同じ符号を持つ場合、D は ABC の内側にあり、ハルは三角形 ABC です。

{ABD,BCD,CAD} のうち 2 つが ABC と同じ符号を持ち、1 つが反対の符号を持つ場合、4 つの点すべてが極値であり、ハルは四角形 ABCD です。

{ABD,BCD,CAD} の 1 つが ABC と同じ符号を持ち、2 つが反対の符号を持つ場合、凸包は同じ符号を持つ三角形です。残りのポイントはその中にあります。

三角形の値のいずれかがゼロの場合、3 つの点は同一線上にあり、中間点は極値ではありません。4 つの点すべてが同一線上にある場合、4 つの値はすべてゼロである必要があり、ハルは線または点のいずれかになります。これらの場合、数値のロバスト性の問題に注意してください!

ABC が正の場合:

ABC  ABD  BCD  CAD  hull
------------------------
 +    +    +    +   ABC
 +    +    +    -   ABCD
 +    +    -    +   ABDC
 +    +    -    -   ABD
 +    -    +    +   ADBC
 +    -    +    -   BCD
 +    -    -    +   CAD
 +    -    -    -   [should not happen]
于 2010-01-23T08:34:17.303 に答える
3

4 点に固有のよりアドホックなアルゴリズムを次に示します。

  • 最小 X、最大 X、最小 Y、最大 Y を持つポイントのインデックスを見つけ、これから一意の値を取得します。たとえば、インデックスは 0、2、1、2 の場合があり、一意の値は 0、2、1 になります。
  • 4 つの一意の値がある場合、凸包は 4 つの点すべてで構成されます。
  • 3 つの一意の値がある場合、これらの 3 つの点は確実に凸包内にあります。4 番目の点がこの三角形内にあるかどうかを確認します。そうでない場合は、凸包の一部でもあります。
  • 2 つの一意の値がある場合、これらの 2 つのポイントはハル上にあります。残りの 2 点のうち、この 2 点を結ぶ線から離れた点は、確実に船体上にあります。三角形の封じ込めテストを実行して、他の点も船体にあるかどうかを確認します。
  • 一意の値が 1 つある場合、4 つの点はすべて一致しています。

蝶ネクタイの形にならないように 4 つの点がある場合は、それらを正しく順序付けるためにいくつかの計算が必要です。うーん....一般化されたアルゴリズムを使用することを正当化するのに十分な特別なケースがあるようです。ただし、これを調整して、一般化されたアルゴリズムよりも高速に実行できる可能性があります。

于 2010-01-23T06:33:08.510 に答える
3

または、単にJarvis marchを使用します。

于 2010-01-24T01:36:27.343 に答える
0

ルックアップ テーブルを使用して、comingstorm の回答の高速な実装を作成しました。4 つの点すべてが同一線上にある場合は、アプリケーションで必要ないため、処理されません。ポイントが同一線上にある場合、アルゴリズムは最初のポインター point[0] を null に設定します。point[3] が null ポインターの場合、ハルには 3 つのポイントが含まれます。それ以外の場合、ハルには 4 つのポイントがあります。船体は、y 軸が上を指し、x 軸が右を指す座標系に対して反時計回りの順序になっています。

const char hull4_table[] = {        
    1,2,3,0,1,2,3,0,1,2,4,3,1,2,3,0,1,2,3,0,1,2,4,0,1,2,3,4,1,2,4,0,1,2,4,0,
    1,2,3,0,1,2,3,0,1,4,3,0,1,2,3,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
    1,4,2,3,1,4,3,0,1,4,3,0,2,3,4,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,1,2,4,0,1,3,4,0,1,2,4,0,1,2,4,0,
    0,0,0,0,0,0,0,0,1,4,3,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,4,0,0,0,0,0,0,0,0,0,
    1,4,2,0,1,4,2,0,1,4,3,0,1,4,2,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,2,4,3,0,1,3,4,0,1,3,4,0,1,3,2,4,
    0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,1,3,2,0,1,3,4,0,1,3,2,0,1,3,2,0,
    1,4,2,0,1,4,2,0,1,4,3,2,1,4,2,0,1,3,2,0,1,3,2,0,1,3,4,2,1,3,2,0,1,3,2,0
};
struct Vec2i {
    int x, y;
};
typedef long long int64;    
inline int sign(int64 x) {
    return (x > 0) - (x < 0);
}
inline int64 orientation(const Vec2i& a, const Vec2i& b, const Vec2i& c) {
    return (int64)(b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}

void convex_hull4(const Vec2i** points) {
    const Vec2i* p[5] = {(Vec2i*)0, points[0], points[1], points[2], points[3]};
    char abc = (char)1 - sign(orientation(*points[0], *points[1], *points[2]));
    char abd = (char)1 - sign(orientation(*points[0], *points[1], *points[3]));
    char cad = (char)1 - sign(orientation(*points[2], *points[0], *points[3]));
    char bcd = (char)1 - sign(orientation(*points[1], *points[2], *points[3]));

    const char* t = hull4_table + (int)4 * (bcd + 3*cad + 9*abd + 27*abc);
    points[0] = p[t[0]];
    points[1] = p[t[1]];
    points[2] = p[t[2]];
    points[3] = p[t[3]];
}
于 2016-07-27T15:53:17.547 に答える