0

軸に沿った長方形 R が素敵な四角形 Q と交差するかどうかを効率的にテストするにはどうすればよいでしょうか?

  • 良い意味: Q は凸型 (シェブロンではない) であり、自己交差していません (蝶ネクタイでも縮退でもない)。
  • ただの二次元。
  • はい/いいえ。実際の交差領域は必要ありません。
  • 編集: Q と R は、開いていても閉じていてもかまいません。

明らかに、Q の各エッジについて、それが R と交差するかどうかをテストできます。これにより、問題は 次のようになります。.

しかし、R の軸整列性が Liang-Barsky によって Cohen-Sutherland よりも高速になるように利用されているように、Q のプロパティは、Liang-Barsky を複数回実行するよりも高速な何かを取得するために利用される可能性があります。

したがって、多角形と長方形の交差アルゴリズムである Sutherland-Hodgman、Vatti、および Greiner-Hormann はすべて、Q を非凸にするアルゴリズムであり、最適である可能性は低いです。

R の軸整列性を利用していなくても、長方形と長方形の交差部分は有望に見えます。

4

2 に答える 2

2

Q が R を完全にカバーする場合、またはその逆の場合を無視しないように注意してください。エッジ テストでは偽陰性が生じるためです。

概念的には、1 つのアプローチ:

  • R を、2 つの軸に整列した無限バンド、垂直バンド [x0,x1] と水平バンド [y0,y1] の交点と見なします。
  • xmin と xmax は、Q と水平バンド [y0,y1] との交点の範囲を表します。[xmin,xmax] ∩ [x0,x1] が空でない場合、Q は R と交差します。

実装に関して：

  1. xmin を初期化します:= +inf; xmax := -inf

  2. Q の各エッジpqに対して、 p =(px,py) q =(qx,qy)、py ≥ qy の場合:

    を。qy > y1 または y0 > py の場合、このエッジを無視して次のエッジを調べます。

    b. py > y1 の場合、(x,y1) をpqと水平線 y = y1 の交点とする。それ以外の場合、x を px とします。

    c. xmin = min(xmin,x); を更新します。xmax = max(xmax,x)。

    d. y0 > qy の場合、(x,y0) をpqと水平線 y = y0 の交点とする。そうでなければ、x を qx とする。

    e. xmin = min(xmin,x); を更新します。xmax = max(xmax,x)。

  3. xmin < x1 かつ xmax > x0 の場合、Q は R と交差します。

于 2015-03-05T21:35:17.223 に答える
0

1) Q の軸に沿ったバウンディング ボックスを構築します。R と交差しないことをテストします。

2) Q のすべてのエッジ E について、R の 4 つの頂点すべてが E のサポート ラインの外側にあることをテストします。(エッジの暗黙の式 を使用しA.x + B.y + c <> 0ます。)

これらのテストのいずれかが成功した場合にのみ、交差はありません。

于 2015-03-06T15:09:02.643 に答える