2

頂点によって定義される2つのポリゴン(具体的にはほぼ長方形である四角形)間のハウスドルフ距離を計算することに興味があります。それらは重複する可能性があります。

$ d_H(A、B)= \ max(d(A、B)、d(B、A))$を思い出してください。ここで、$ d$はハウスドルフセミメトリック$d(A、B)= \ sup_{a\です。 in A} \ inf_ {b \ in B} d(a、b)$。

$ A $、$ {A_i} $、$ d(A、B)= \ max {d(A_i、B)} $の有限の互いに素なカバーを考えると、それは本当ですか?その当然の結果は、$ d(A、B)= d(A \ setminus B、B)$です。

Atallah 1(PDF)の論文を見つけました。私はPythonでの作業に興味があり、事前にプログラムされたソリューションを利用できます。

4

1 に答える 1

2

凸多角形の場合、はの頂点からの任意の点までd(A, B)の距離の最大値です。したがって、任意の点から凸多角形までの距離を計算できれば、ハウスドルフ距離を計算するのはそれほど難しくありません。AB

ポイントから凸多角形までの距離を計算するには、最初にポイントがポリゴンの内側にあるかどうかをテストする必要があります(その場合、距離は0です)。次に、境界線セグメントのいずれかまでの最小距離が見つからない場合。

他の質問に対する答えはノーです。例として、AとBの両方を原点を中心とする同じ2x2の正方形とします。Aを4つの1x1の正方形に分割します。各AiからBまでのハウスドルフ距離はですsqrt(2)が、AからBまでの距離は0です。

更新:頂点に関する主張はすぐには明らかではないため、有限数の次元で適切な証明をスケッチします。私が証明しようとしている結果はd(A, B)、ポリゴンと凸面の両方で計算する場合、の頂点からBの距離を見つけるだけで十分であるということです。(の最も近いポイントは頂点ではない可能性がありますが、の最も遠いポイントの1つは頂点である必要があります。)ABBA

どちらも有限の閉じた形状であるため、コンパクトです。コンパクトさから、そこから可能な限り離れた点pが存在しなければなりません。コンパクトさから、可能な限りに近い点が存在しなければなりません。ABqBA

この距離は、ABが同じポリゴンである場合にのみ0になります。この場合、の頂点でその距離を達成することは明らかですA。したがって、一般性を失うことなく、からpへの距離が正であると想定できqます。

qからの線に垂直な平面(高次元では、ある種の超平面)に接するように描画pqます。Bこの平面を横切る点はありますか?たとえば、1つある場合は、からまでrの線分のすべての点が凸であるため、中にある必要があります。しかし、この線分には、の定義と矛盾する、より近い点が存在する必要があることを示すのは簡単です。したがって、この平面を横切ることはできません。qrBBpqqB

明らかpに内部の点になることはできません。内部の点である場合は、からの光線に沿って続行qすると、背後にある境界の平面から遠く離れたp点が見つかり、の定義と矛盾します。がの頂点である場合、結果は自明に真になります。したがって、唯一の興味深いケースは、が頂点の境界上にあるが頂点ではない場合です。ABppApA

もしそうなら、それからp表面にあります。そのサーフェスが作成した平面と平行でない場合、背後にある平面から離れて、そのサーフェスに沿って移動し、よりもB遠くにあるポイントを見つけるのは簡単です。したがって、その表面はその平面に平行でなければなりません。は有限であるため、そのサーフェスはどこかの頂点で終了する必要があります。これらの頂点は、その平面からと同じ距離にあるため、少なくとも。と同じ距離にあります。したがって、から可能な限り離れた頂点が少なくとも1つ存在します。BpApBpAB

そのため、ポリゴンの頂点から他のポリゴンまでの距離の最大値を見つけるだけで十分でした。

q(読者にとって楽しい演習として、頂点のないポリゴンのペアを作成することはお任せします。)

于 2012-06-08T14:58:53.170 に答える