まず、これにどのキーワードを使用すればよいかわかりません。おそらく間違ったキーワードを使用してグーグルで検索していると思います。
私の問題は次のとおりです。家の計画内の「部屋」を見つける必要があります。たとえば、次のジオメトリを使用します。
必要なアルゴリズムは、どの頂点が各部屋を区切っているかを教えてくれます。したがって、この例では次のようになります。
入力データとして頂点とエッジがあります。編集：エッジデータは次のとおりです（エッジ8、1、2）：
XY
47 196
47 85
258 85
ピクセル座標です。
情報を共有するループを切断したため、グラフ理論はあまり役に立ちませんでした。たとえば、[1 2 9 10 3 4 5 8 1] AND [11 12 14 13 11]。そのため、最終的には、塗りつぶし 1 ピクセルの境界線を拡張し、塗りつぶされた画像内にある頂点を特定するためにブール演算を実行するときに、画像塗りつぶしを実行することになりました。
考えられる解決策の 1 つは、この領域を三角形分割して、すべての入力エッジが三角形のエッジになるようにすることです。次に、三角形を接続されたセットに分割し、それらの境界を見つけます。
三角測量にはいくつかのアルゴリズムがあります: イヤークリッピング、ドロネー...
これは平面グラフです。V 頂点、E エッジ、および F = E - V + 2 つの面 (外面を含む) があります。すべての面のエッジ リストを決定する必要があります。すべてのエッジは、これらのリストで 2 回使用されます (順方向と逆方向)。
メイン アーク リストを作成し、すべてのアークを追加します (つまり、1-2 無向エッジの場合、1-2 および 2-1 有向アークの両方を追加します)。
一番下の頂点を見つけます。そのような点が複数ある場合は、一番左の点 (ここでは 7 番目) を選択します。外側の面 (輪郭) を CCW 方向に移動します (すべての頂点で右端の円弧を選択します): 7-6-5-4-3-2-1-7. 訪問したアークをメイン リストから削除します。
メイン リストからアークを取得し、最初の内側の面を移動し、右手の法則 (つまり 7-8-5-6-7) に従い、訪問したアークを削除します。
メイン リストが空になるまで繰り返します。
切断されたコンポーネントに対してすべての手順を繰り返します (11-12-13-14)