2D グリッド上の正方形のタイルで構成されるポリゴンを扱っています。ポリゴンは単純にタプルのリストとして格納され、各タプルはタイルの座標を表します。ポリゴンは常に連続しており、穴はありません。
私ができるようにしたいのは、どのタイルがポリゴンの境界に沿った頂点を表しているかを判断することです。これにより、後で各タイル間をトレースしてポリゴンの境界を生成したり、2 つの連続する頂点間の距離を決定して長さを見つけたりすることができます。サイドなど
多角形の例を次に示します (5x4 の長方形と左上から 3x2 の長方形を差し引いたもので、後方の「L」が生成されます)。
polygon_tiles = [(3, 0), (4, 0), (3, 1), (4, 1), (0, 2), (1, 2), (2, 2), (3, 2),
(4, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
理想的には、私が求めているアルゴリズムは次のような結果を生成します。
polygon_verts = [(3, 0), (4, 0), (4, 3), (0, 3), (0, 2), (3, 2)]
頂点が順番にリストされ、境界線を時計回りにトレースします。
いくつかのテストケースをいじるだけで、この問題は私が思っていたよりもはるかに複雑なようです。特に、ポリゴンに 1 タイル幅の押し出しがあるような奇妙な状況では (この場合、タイルの 1 つが頂点として 2 回保存されますか??)。
私はPythonで作業していますが、疑似コードであっても洞察をいただければ幸いです。