そこに仲間のプログラマーをアバスト！
私は次の問題を抱えています：
下の写真のように2つの長方形が重なっています。
点ABCDEFで構成される多角形を理解したいと思います。
別のクリスマスの説明：赤いクッキーカッターが黒いクッキーを少し切り取っています。ブラッククッキーを計算したい。
各長方形は、4つの2次元頂点を持つデータ構造です。
これを達成するための最良のアルゴリズムは何ですか？
Nailer
質問する
2895 次
4 に答える
5
これは、一般的な 2D ポリゴン クリッピングの特殊なケースです。出発点としては、Weiler-Atherton アルゴリズムが適しています。 ウィキペディアには、要約と元の論文へのリンクがあります。アルゴリズムは、あなたが説明したデータ構造とかなりよく一致しているようです。
穴の開いた四角形 (赤が黒の中に完全に入っている場合) または 2 つの四角形 (たとえば、赤が黒よりも背が高くて細い場合) になる可能性が非常に高いことに注意してください。黒い四角形の内側に赤い四角形の角が 1 つしかないことが確実な場合、解決策ははるかに簡単になります。
于 2008-12-22T15:15:09.943 に答える
2
于 2008-12-22T15:05:59.493 に答える
2
座標はどのくらい正確ですか？四角形がかなり小さい場合、最も簡単な方法は、最初に黒の四角形、次に赤の四角形をキャンバスにペイントすることです。キャンバス上の残りの黒いピクセルは、残っているポリゴンです。
もう 1 つの方法は、座標グリッドを長方形のすべての辺に基づいて多数の長方形に分割することです (境界のない長方形は数えません。元の長方形が 2 つある場合、最大 9 つの長方形が生成されます)。次に、特定のポリゴンのメンバーシップについてこれらの各長方形からの代表点をテストして、どの長方形が入っていてどれが外れているかを判断します。
于 2008-12-22T15:20:12.710 に答える
0
ここで使用できるものをいくつか見つけました：
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html
この質問を投稿する前に、実際にCGALソースをダウンロードしましたが、詳しく調べてみると思います。
于 2008-12-22T15:18:42.133 に答える