3

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で作業していますが、疑似コードであっても洞察をいただければ幸いです。

4

3 に答える 3

4

形状に内部穴がないと仮定します。

一番上の行を見つけます。この行の一番左のタイルを選びます。これにより、コーナーから開始することが保証されます。

このタイルから、まっすぐ右に行こうとします。それができない場合は、方向を選択するまで、まっすぐ下に、またはまっすぐ下に進みます。これにより、ポリゴンの時計回りの周囲をトレースできることが保証されます

選択した方向に進み続けます。各ステップの後:

  • 次のステップがタイル上にある場合は、反時計回りに回転させてもう一度見てください。
  • 次のステップが空のスペースにある場合は、時計回りに回転してもう一度見てください。

空のスペースに移動したら、回転を停止し、再びタイルに戻ります。

最初の方向から回転した場合、頂点に立っている必要があります。そのようにマークします。

通過する他のすべてのタイルをエッジの一部としてマークします。

最初のタイルに到達するまで端を歩き続けます。1 つのタイルの押し出しの場合、タイルの上を複数回歩くことができます。

このアルゴリズムが頭の中で意味をなさない場合は、紙を取り出して手で追ってみてください:)

于 2013-02-12T08:07:58.487 に答える
0

頂点間の線の傾きを計算するだけです

# Do sort stuff

vertices = []
for position, polygon in enumerate(polygon_tiles):
    # look for IndexErrors
    try:
         polygon_tiles[position+1]
    except IndexError:
         break

    try:
        polygon_tiles[position+2]
    except IndexError:
        # Bad practice
        position = position - 1

    # calculate the slope of the line between of vertex 1 and vertex 2  
    s1 = (polygon_tiles[position+1][1] - polygon[1]) / (polygon_tiles[position+1][0] - polygon[0])
    # calculate the slope of vertex 2 and vertex 3
    s2 = (polygon_tiles[position+2][1] - polygon_tiles[position+1][1]) / (polygon_tiles[position+2][0] - polygon_tiles[position+1][0])
    # if the slopes differ then you have a vertex
    if d1 != d2:
        vertices.append(polygon_tiles[position+1])
于 2013-02-12T08:11:59.663 に答える