algorithm - アウトラインプロットアルゴリズム

Question

私は妻からこの仕事を与えられたので、最優先事項です:-)

私はポイントのコレクションを持っています (実際には Northings と Eastings ですが、実際には問題ではありません)。これらの点を取り、アウトラインを表す一連のベクトルを作成して、Google Earth にプロットできるようにします。

したがって、次のようなものです：

  #                       #
           #             #       #
#             #    #
      #   #

            #

与えます：

  #-----------------------#--
 /                            \ --#
#                  #------------/
 \-----#         /
         \     /
            #

私が思いついた可能な解決策は、すべてのポイント間のベクトルを計算し、別のベクトルが重なっているすべてのベクトルを破棄することです。私はこれをまだ実装していませんが (方法はよくわかりません)、他の方法があるかどうか疑問に思いました。

アルゴリズムは数回実行するだけでよいため、1 回の実行に 1 時間かかり、RAM が何ギガもかかっても問題ありません。

score 7 · Accepted Answer

候補ポリゴンの定式化

そのようなポリゴンを探しているようです

これにより、ポイントセットに関して実行可能な候補ポリゴンのセットが定義されます。

目的関数の 1 つは、「これらのポリゴンの中から、頂点の数が最小のものを選択する」です。それがポイントセットの凸包になります。他の回答はそのアプローチに対処しているため、それについてはこれ以上述べません。

しかし、選択できる目的関数はこれだけではありません。たとえば、代わりに、頂点の数を減らす、総面積を減らす、頂点の角度をあまり鋭くしないというトレードオフを行うことができます。その問題に対する既存の名前付きアルゴリズムは知りませんが、間違いなく興味深いものです。

1 つのアプローチは、凸包を見つけることから始めて、余分な頂点のコストよりも総面積が少ないという利点が勝る場所の内側の頂点にエッジを「引き込む」ことです。

たとえば、次のようになります。

ここに画像の説明を入力

上部に沿ってエッジを引っ張ると、次のようになります。

ここに画像の説明を入力

この 2 番目のポリゴンは、ポイントセットの凸包ではありませんが、ポイントセットにより「自然」に適合する可能性があります。