Hausdorff 볼록 다각형 사이의 거리

Question

두 개의 다각형 (특히 거의 직사각형 인 사변형) 사이의 Hausdorff 거리를 계산하는 데 관심이 있습니다. 중복 될 수 있습니다.

$ d_H (A, B) = \ max (d, B), d (B, A)) $ 여기서 $ d $는 Hausdorff 반 미터법입니다. $ 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). 저는 파이썬으로 작업하는 것에 관심이 있으며 사전 프로그래밍 된 솔루션에 개방적입니다.

Answer 1

볼록 다각형의 경우 A의 정점에서 B까지의 모든 점까지의 거리의 최대 값은 d(A, B)입니다. 따라서 Hausdorff 거리는 임의의 점에서 볼록한 다각형까지의 거리를 계산할 수 있다면 계산하기가 너무 어렵지 않습니다.

점에서 볼록한 다각형까지의 거리를 계산하려면 먼저 점이 다각형 안에 있는지 테스트해야합니다 (거리가 0 인 경우). 경계선 세그먼트.

다른 검색어에 대한 답변은 '아니오'입니다. 예를 들어, A와 B 둘 다 원점을 중심으로하는 동일한 2x2 정사각형이되도록하십시오. A를 4 개의 1x1 사각형으로 분할합니다. B에 A는 각각 _내가에서 하우스 도르프 거리 sqrt(2)이지만, A와 B의 거리가 0이

UPDATE입니다 : 정점에 대한 주장은 즉시 명확하지 않다, 그러므로 나는 증거를 스케치 것이다 그 어떤 유한 수 차원에서도 좋습니다. 내가 증명하려고하는 결과는 d(A, B)과 B 볼록을 모두 계산할 때 A의 정점에서 B까지의 거리를 찾는 것으로 충분합니다. B의 가장 가까운 점은 정점이 아니지만 A의 가장 먼 점 중 하나가 꼭지점이어야합니다.

둘 다 한정된 닫힌 모양이므로 컴팩트합니다. 간결함에서 가능한 한 B 인 A에 p 점이 있어야합니다. 간결함에서 가능한 한 A에 가깝게 의 B에 점이 있어야합니다.

A과 B이 같은 다각형 인 경우에만이 거리가 0이며,이 경우 해당 거리가 A의 꼭지점에서 달성된다는 것은 분명합니다. 일반성을 잃지 않고 p에서 q까지 양의 거리가 있다고 가정 할 수 있습니다.

는 p에서 q에 선에 수직 q 터치 평면 (초평면보다 높은 차원에서 일종)를 그린다. B의 어떤 지점이이 비행기를 건너 뛸 수 있습니까? 글쎄요, 만약 r이라면, q에서 r까지의 모든 선분은 B이 볼록이기 때문에 B이어야합니다. 그러나 q의 정의와 상반되는 q보다 p에 더 가까운이 선분에 포인트가 있어야한다는 것을 보여주는 것은 쉽습니다.따라서 B은이 평면을 가로지를 수 없습니다. 그것이 있다면, p에 q에서 선을 따라 계속하고 멀리 B이 p의 정의 모순 뒤에 묶여 비행기에서 있습니다 A에 포인트를 찾을 수 있기 때문에

분명히 p는 인테리어 포인트가 될 수 없습니다. p이 A의 정점이면 결과는 사실입니다. 따라서 p이 A의 경계에 있지만 꼭지점이 아닌 경우에만 흥미로운 경우입니다.

그렇다면 p이 표면에 있습니다. 그 표면이 우리가 만든 비행기와 평행하지 않다면, 그 비행기를 따라 가면 B 뒤에있는 비행기에서 멀리 이동하고 B에서 멀리 떨어진 지점을 p보다 더 쉽게 찾을 수 있습니다. 따라서 그 표면은 그 평면과 평행해야합니다. A이 유한이기 때문에 그 표면은 어딘가에 꼭지점에서 끝나야합니다. 그 정점들은 그 평면으로부터 같은 거리이고, 따라서 B으로부터 최소한 p만큼 멀리 떨어져 있습니다. 따라서 B에서 가능한 한 멀리있는 A의 꼭지점이 하나 이상 있습니다.

그 이유는 다각형의 정점에서 다른 다각형까지의 거리를 찾는 것이 충분했기 때문입니다.

는 (나는 독자를위한 재미 운동으로 q되지 정점과 다각형의 한 쌍을 구성 둡니다.)