だから私は表面を近似する三角形のメッシュを持っています。
これは、次のプロパティを持つグラフのようなものです。
- グラフの境界線上の頂点は簡単に識別できます。(隣接する頂点の数 > 含まれる三角形の数)
- 任意の 2 つの頂点間の距離を簡単に計算できます。(ユークリッド距離)
- 任意の頂点vについて、 vの隣接点ではない頂点は、vの隣接点の少なくとも 1 つよりもvまでの距離が大きくなければなりません。つまり、 vの近傍リング内に非隣接頂点が出現することはありません。
各頂点vについて、v から任意の境界頂点までの最小距離を計算したいと考えています。
私は力ずくでこれを行い、すべての境界頂点のリストを作成し、vの距離をそれぞれと比較し、最小値を維持することができます。しかし、これは非効率的です。
単一の頂点vごとに最も効率的な方法は、最上位の要素がvに最も近い優先キューを持つことだと思います。キューはvの隣人で初期化されます。キューの上部は境界頂点ではありませんが、上部をポップし、ポップされた頂点のすべての隣接をプッシュします。
頂点vに 6 つの隣接点があるとします。6 つのそれぞれの最小境界距離を計算し、6 つの隣接点の最小値を与える正確な境界頂点を記録しました。これらのいずれかがvの最小境界値も与える必要があることを私は知っています。これを証明することはできませんが、直感的だと思います。vが隣接する頂点に囲まれている場合、 vに最も近い境界頂点は、隣接する頂点の 1 つに最も近い境界頂点でなければなりません。
この知識を使用して、グラフの各ポイントの最小値を効率的に計算する方法があるかどうかを知りたいです。各頂点からの幅優先検索よりも効率的です。