geometry - 囲まれたエリア内のポイントを見つける

Question

ポイントが整数の正の座標を持つxyグリッドがあります。これらのポイントは、x 座標と y 座標の差が 2 未満の場合、「隣り合っている」ということになります。

このグリッドで、ある領域を囲むパスを見つけました。パス内のすべてのポイントは、前のポイントと次のポイントに隣接しているため、囲まれた領域を歩き回るように並べ替えられます。また、その囲まれたエリアを巡る最短経路であるため、前後の段差はありません。囲まれた領域は凸状である必要はないため、パス上のランダムな 2 点を 1 本の線で結ぶと、その線はその領域から完全に外れることがあります。

問題は、囲まれたパスの任意のポイントに隣接する、囲まれた領域内の少なくとも 1 つのポイントを見つける必要があることです。

簡単に聞こえるかもしれませんが、それを決定するための確かなアルゴリズムは見つかりませんでした。

※すみません、説明不足でした。囲まれた領域に「空の部分」はありません。囲まれた領域に 3 つのポイントがある場合、その周りのパスは、それらの 3 つのポイントをキャプチャする最小のパスです。この図では、赤いパスが最短で、黒いパスが長すぎます。これらを検出する必要はありません。

Answer 1

質問を理解していることを確認するための観察:

• そのような内部ポイントがない可能性があります。
• 連続するパス ポイントが隣接する場合、接続角度は 45° の倍数になります。

基本的な考え方は、パスを歩き、内側と外側の隣人を追跡することです。

どちらの側が内側であるかを判断するには、パスを歩き、累積ターン角度を追跡します。最終的な量は 360° または -360° になり、定義した正と負の角度に応じて、内部が左または右にあることを示します。

その最初のパス中に、パス上のポイントのハッシュ セットも収集しますonPathPoints。

1. 他の 2 つのハッシュ セットを空に初期化します:exteriorPointsとpossibleInteriorPoints.
2. パスを歩き、各ポイントについて:
   • を。パス上の前のポイントと次のポイントの相対位置に基づいて、8 つの隣接ポイントをパス上、内側、または外側に分類します。
   • b. の各点についてonPathPoints、無視します。
   • c. 内側で距離が 1 の任意の点については、その点を結果として返します。
   • d. 距離が 1 より大きい内側の各点 (対角線上の隣接点) について、それを に追加しpossibleInteriorPointsます。
   • e. 外側と距離 1 の各点について、それを に追加しexteriorPointsます。
3. ウォークの最後に、possibleInteriorPoints任意のポイントから削除しますexteriorPoints(減算を設定します)。に残っている任意の点possibleInteriorPointsを内部点として返します。
4. それ以外の場合、内部ポイントはありません。

はpossibleInteriorPoints、パスが元のポイントと元のポイントの間でループバックしない限り、内部にある斜めに隣接するポイントを表します (この場合、新しいパス パーツの外部ポイントになります)。

たとえば下の画像で、(2,2) を訪れて (3,3) に向かうと、内部は右側にあります。(3,1) は内点の可能性がありますが、(4,1) を訪れた後の散歩では、(3,1) は外点であることがわかり、 から削除されpossibleInteriorPointsます。

技術的には、この例では、アルゴリズムは (4,3) を訪問し、(4,2) を距離 1 の内部点として認識したときに停止します。