geometry - 多角形から四角形を減算

Question

単純な凹面多角形から四角形を減算し、残りの多角形を返すアルゴリズムを探しています。四角形が多角形を囲む場合、残りは null です。ほとんどの場合、長方形と多角形の間で少なくとも 1 つのエッジが共有されるように見えます。

私はインターネットを掘り下げてきましたが、良い手がかりが見つかりませんでした.

誰かが私を正しい方向に向けることができますか?

Answer 1

それは簡単です: 長方形と単純な多角形のエッジの間の交点を見つけて、そこでセグメントを切り取ります。これは、ポリゴンの 4 つのエッジが一定の要素であるため、空間検索構造を必要としないため、線形時間で実行されます。

次に、すべてのセグメントの制約付き Delaunay 三角形分割を計算し、シード ポイントを使用して領域を拡大します。領域を適切に組み合わせます (単純な多角形の内側の三角形から、長方形の内側の三角形から外側の三角形を引いたものを差し引いたものです。残った三角形が結果であり、境界エッジが結果のポリゴンのエッジです。

編集：答えが短すぎたらごめんなさい。下の図はその考え方を示しています。
a) 2 つの入力ポリゴン
b) (カットされた) セグメントの挿入後の CDT
c) 成長した領域
d) 緑の領域から赤の領域を引いたもの
e) d の領域の境界エッジ。