2つの凸多角形があります。ポリゴンは、頂点の循環リストとして実装されます。この2つのポリゴンの交点を見つけるには?2つの凸多角形の交点
答えて
For each edge V1-V2 in the first polygon,
Let H := Half-plane tangenting V1-V2, with the remaining
vertices on the "inside".
Let C := New empty polygon.
For each edge V3-V4 in the second polygon,
Let X := The intersection between V3-V4 and H.
If V3 inside H, and V4 is outside H then,
Add V3 to C.
Add X to C.
Else if both V3 and V4 lies outside H then,
Skip.
Else if V3 outside H, and V4 is inside H then,
Add X to C.
Else
Add V3 to C.
Replace the second polygon with C.
これは単純な使い方で十分です。すべてのフレームを再計算しません。 — O(N )ここで
はいくつかのリンクです:
あなたがいるという事実から恩恵を受けることができます両方のポリゴンが凸です。この知識を使って、次の掃引線アルゴリズムを使用して、O(n)時間を達成することができます。
両方のポリゴンのトッパポイントを見つけます。簡単にするため、水平なエッジがないとします。ポリゴンの左と右の境界に寄与するエッジのリストを作成します。
飛行機を掃除している間に、4つのエッジが保存されます。 left_edge_C1、right_edge_C1、left_edge_C2、right_edge_C2。エッジを描画するのに複雑なものは必要ありません。そのうち4つしかないからです。すべての可能なオプションを反復するだけで、次のイベントポイントを見つけることができます。
各イベントポイントで、交差点の境界にエッジが表示されます。基本的に、各イベントポイントで無料のケースの1つを持つことができます(写真を参照)。
Yolaの素敵な平面スイープ記述@に加え「イベントポイント」とはどういう意味ですか? – TJM
、 Computational Geometry in Cで説明した線形時間アルゴリズムが存在し、第7章とC & Javaコードは(同じリンクで)入手可能です。 2つのポリゴンがある点で交差する場合、または交差点がセグメントである場合など、いくつかのトリッキーな縮退の場合があります。
- 1. 凸多角形のベクトルの交点の度合いを調べる
- 2. 主成分凸多角形
- 3. OpenGLの非凸多角形の概要
- 4. Cudaの凸多角形アルゴリズムですか?
- 5. 凸多角形の生成方法
- 6. 単純凸と単純非凸多角形の差
- 7. 最も速い水平線<->凸多角形交差アルゴリズムですか?
- 8. 多数の小さな凸多角形の中に一般的な多角形を細分する
- 9. ランダム凸多角形の生成方法は?
- 10. 重複する凸多角形の検索
- 11. 連結された凸多角形のグラフを生成
- 12. 線の交点矩形 - 交点を見つける方法?
- 13. 2つの矩形の交点の面積を求める
- 14. 非凸多角形のジオ座標からエリアを計算する
- 15. C++の2つの円の交差点
- 16. 単調多角形のDelaunay三角形
- 17. レイと矩形の交点
- 18. 多角形のグループからのSTConvexHull()多角形
- 19. 点集合から四角形の頂点を見つける
- 20. OpenGL正多角形
- 21. 多対多および多対多の交差点
- 22. C++での線と矩形の交点
- 23. 矩形の2Dセグメントの交点
- 24. Mathematicaで2つのListLinePlotの交点を見つける
- 25. 2つの配列の交点を見つける
- 26. 雲の点から形成された2つの線の交点を検出する方法
- 27. 同一平面上に三角形の交差点オリヴィエDevillers、フィリップGuigue
- 28. 三角形メッシュと平面の交点から輪郭を作成
- 29. 凸多面体の重心
- 30. MySQLのグレートサークル交差点(2つの道路が交差するのですか?)
ケース3ではV3を交差点に追加する必要がありますか?間違っているようです。 – DaZzz
私はそれをSutherland-Hudgmanアルゴリズムと一直線になるように書き直しました。 –