3

重複の可能性:
ポリゴン交差の単純なアルゴリズム

2 つの任意の向きの四角形の交点をすばやく計算する方法の概要を探しています (事前に設定された角の角度や辺の長さの制約はありません)。それらが交差しているかどうかを単純に確認するつもりはありませんが、結果の交差領域を構成するポイントを取得したいと考えています。一般に、ポリゴンの交差は些細な問題ではなく、適切に機能するライブラリが利用できることを知っています。

しかし、この特別なケースでは 4 辺の形状のみに関心があるため、アプリケーションに追加のライブラリ全体を含めずに使用できる簡単な方法があるかどうか疑問に思っていました。

これまでのところ、私が考えたのは次のとおりです。

  1. お互いに関して両方の形状で「ポリゴン内のポイント」を実行します
  2. 各ポリゴンの各エッジを互いに交差させます

上記の 2 つの手順で、結果の交差領域を構成するすべてのポイントを確実に取得できますか? より良い使用方法はありますか？

また、結果の領域を構成するポイントの正しい順序を取得できればいいと思います。これは必須ではありません。このビットを実行する巧妙な/迅速な方法 (凸包?) を知っている場合は、提案をいただければ幸いです。

4

2 に答える 2

4

あなたは2つの四文字が凸状であるかどうかを述べていませんでした。そうである場合は、 http： //www.iro.umontreal.ca/~plante/compGeom/algorithm.htmlなどの正多角形交差アルゴリズムを使用できます。

私が収集できることから、それはエキゾチックなデータ構造や操作を必要としないので、実装するのは難しいことではないはずです。

于 2012-10-30T07:19:47.677 に答える
2

凸多角形の交差は比較的簡単です。それをグーグルで検索してください。SOと他の場所の両方に多くのリソースがあります。

ただし、すべての四角形が凸であるとは限りません。凸でない 2 つの四角形が交差すると、いくつかの切断されたポリゴンが生じる可能性があります。それらのポイントだけではほとんど得られませんが、それが必要な場合は、先に進んでエッジの各ペアを交差させてください。一般的な方法よりもはるかに簡単で高速です

凸形状の場合でも、愚かな総当たり法の方が高速な場合があります。自分に最適なものを見つけるには、いくつかのテストを行う必要があります。

于 2012-10-30T09:51:06.030 に答える