仕事
重複していない (しかし接触している) 多角形のセットから双対グラフを計算します。
例
ポリゴンA、B、およびC、それらの部分的に共有された座標 1 ～ 22 (黄色) および双対グラフ (青色)。
データ
ポリゴンのセットSがあります。すべてのポリゴンP iは、座標の順序付きリストとして表されます。ポリゴンP iのエッジa_b は、 P i,(a,b) で表されます。
考え
多角形は面を表し、したがって双対グラフのノードを表します。ポリゴンP iの隣接する面を識別するには、P iのすべてのエッジを他のすべてのポリゴンP jのすべてのエッジと比較します。エッジが他の多角形と共有されている場合、P iとP jは隣接しています。
これにより、後で削除できる大量の複数のエッジが作成されます。
問題
このアルゴリズムは、 O(E 2 )で実行されるため、あまり効率的ではありません。ここで、Eは多角形のセットSのエッジの数を示します。
改善案
最初のステップでエッジ インデックスを作成します。これにより、実行時間がO(2×E) = O(E)に短縮されます
次数 2 のすべてのノードを削除します (これはデュアル グラフには影響しないと思いますか?)
質問
- 私は正しい軌道に乗っていますか？
- このタスクに対して承認されたアルゴリズムはありますか?