5

私は次のように定義されているクワッドタイプを持っています：

typedef struct __point {
    float x;
    float y;
} point_t;

typedef struct __quad {
    point_t p1;
    point_t p2;
    point_t p3;
    point_t p4;
} quad_t;

同じ平面上にこれらのクワッドが2つある場合、それらのクワッドの交点を計算できるようにしたいと思います。たとえば、クワッドAとクワッドBがある場合、BのポイントのいずれかがAの外側にあると、アルゴリズムは次の図に示すようにポイントを持つクワッドを生成する必要があります（Aは赤、Bは紫）。

例

編集：ポイントの順序は重要ではありません。後でこれらのポイントを使用して、A内に描画されるクワッドを作成するためです。

4

4 に答える 4

1

これを行う唯一の理由が結果のポリゴンを描画することである場合は、GPUを使用して作業を行ってみませんか？結局のところ、OpenGLを使用しています。したがって、交差点の構築方法を混乱させる代わりに、次のようにします。-

Set Z values of Polygon A and Polygon B to some constant

Set Z test to no testing (always write Z regardless)

Disable Z test
Enable Z writes
Disable colour writes
Render Polygon A

Set Z test to z equal

Enable Z test
Disable Z write
Enable colour write
Render Polygon B

ねえプレスト、交差点ポリゴン！

OpenGL 4に制限し、利用可能なさまざまなシェーダーを使用すると、これをはるかに効率的にすることができます。

于 2012-08-31T15:03:54.717 に答える
0

凸多角形の場合、私はお勧めします：

1：分離軸方式との交点確認（高速）

2： O'Rourkeの本からアルゴリズムとの交差点を見つける（Cコードが利用可能）

于 2012-08-31T16:33:39.700 に答える
0
  • クワッドは自己交差しないことが保証されていますか?
  • クワッドは凸面であることが保証されていますか?

それらが凸状である場合、交差は最大で 8 つの頂点を持つ単一のポリゴンになると思います。それらが凸状でない可能性がある場合、交差点として 2 つの分離したポリゴンになる可能性があります。

凸であると仮定すると、結果の頂点のセットは、線の交点のセットと、もう一方に含まれる入力クワッドの頂点のセットになると思います (ただし検証はしていません)。交点は、これらの頂点の (凸) ハルになります。

この時点で、これらのセットを効率的に取得するだけの問題です。

于 2012-08-31T14:47:36.870 に答える
0

完全な実装ではありませんが:

  1. 2 つの線分の交点を見つけるルーチンを作成します。intersect_segment

    bool segments_intersect(
    point_t a0, point_t a1,
    point_t b0, point_t b1,
    /*out*/ point_t* intersection
)

  2. クワッドルーチンでポイントを書き、point_in_quad

    bool point_in_quad(point_t p, quad_t q)

  3. segments_intersect最初が赤いクワッドにあり、2 番目が紫のクワッドにあるセグメントの各ペアに適用します (全体で 16 テスト)

    point_t temp;
if(segments_intersect(red.p1, red.p2, purple.p1, purple.p2, &temp)))
    found_point(temp);
if(segments_intersect(red.p1, red.p2, purple.p2, purple.p3, &temp))
    found_point(temp);
if(segments_intersect(red.p1, red.p2, purple.p3, purple.p4, &temp))
    found_point(temp);

//10 more

if(segments_intersect(red.p4, red.p1, purple.p2, purple.p3, &temp))
    found_point(temp);
if(segments_intersect(red.p4, red.p1, purple.p3, purple.p4, &temp))
    found_point(temp);
if(segments_intersect(red.p4, red.p1, purple.p4, purple.p1, &temp))
    found_point(temp);

  4. point_in_quad紫のクワッドをテストする赤のクワッドのすべてのポイントに適用します。

    if(point_in_quad(red.p1, purple)) found_point(red.p1);
if(point_in_quad(red.p2, purple)) found_point(red.p2);
if(point_in_quad(red.p3, purple)) found_point(red.p3);
if(point_in_quad(red.p4, purple)) found_point(red.p4);

  5. point_in_quad赤いクワッドをテストする紫色のクワッドのすべてのポイントに適用します。

    if(point_in_quad(purple.p1, red)) found_point(purple.p1);
if(point_in_quad(purple.p2, red)) found_point(purple.p2);
if(point_in_quad(purple.p3, red)) found_point(purple.p3);
if(point_in_quad(purple.p4, red)) found_point(purple.p4);
于 2012-08-31T14:38:01.597 に答える