凸多边形的豪斯多夫距离 [英] Hausdorff Distance Between Convex Polygons

问题描述

我感兴趣的计算豪斯多夫距离的2个多边形（特别是四边形这几乎是矩形）通过其顶点定义的。它们可以重叠。

I'm interested in calculating the Hausdorff Distance between 2 polygons (specifically quadrilaterals which are almost rectangles) defined by their vertices. They may overlap.

召回$ d_H（A，B）= \最大值（D（A，B），D（B，A））$其中$ D $是豪斯多夫半度量 $ D（A，B）= \ sup_ {甲A \} \ inf_ {B \在B} D（A，B）$。

Recall $d_H(A,B) = \max(d(A,B), d(B,A))$ where $d$ is the Hausdorff semi-metric $d(A,B) = \sup_{a\in A}\inf_{b\in B}d(a,b)$.

这是真的，鉴于$有限不相交的覆盖$，$ {A_I} $，$ D（A，B）= \最大{D（A_I，B）} $？其中的一个推论是，$ D（A，B）= D（A \ setminus B，B）$。

Is it true that, given a finite disjoint covering of $A$, ${A_i}$, $d(A,B)=\max{d(A_i,B)}$? A corollary of which is that $d(A,B)=d(A\setminus B,B)$.

我已经找到了论文阿塔拉<一href="http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1362&context=cstech&sei-redir=1&referer=http%3A%2F%2Fscholar.google.co.uk%2Fscholar_url%3Fhl%3Den%26q%3Dhttp%3A%2F%2Fdocs.lib.purdue.edu%2Fcgi%2Fviewcontent.cgi%253Farticle%253D1362%2526context%253Dcstech%26sa%3DX%26scisig%3DAAGBfm2KBgx4gRLwPm_PuNgeO-bP1KLiKA%26oi%3Dscholarr%26ei%3D87PRT4Ft6KPRBaGoua8E%26ved%3D0CAYQgAMoADAA#search=%22http%3A%2F%2Fdocs.lib.purdue.edu%2Fcgi%2Fviewcontent.cgi%3Farticle%3D1362%26context%3Dcstech%22"相对=nofollow> 1（PDF）。我很感兴趣，在Python工作，将开放给任何preprogrammed解决方案。

I have found a paper by Atallah 1 (PDF). I'm interested in working in Python and would be open to any preprogrammed solutions.

推荐答案

在凸多边形的情况下， D（A，B）是从距离最大 A 的顶点任何一点 B 。因此，豪斯多夫距离不是太硬来计算，如果你可以计算出从任意点的距离为凸多边形。

In the case of convex polygons, d(A, B) is the maximum of the distances from vertices of A to any point in B. Therefore the Hausdorff distance is not too hard to calculate if you can calculate the distance from an arbitrary point to a convex polygon.

要计算从一个点到一个凸多边形的距离必须首先测试点是否在多边形内部（如果这样的距离为0），然后，如果它没有发现的最小距离的任何边界的线段。

To calculate the distance from a point to a convex polygon you first have to test whether the point is inside the polygon (if so the distance is 0), and then if it is not find the minimum distance to any of the bounding line segments.

回答你的其他查询是否定的。作为一个例子，让A和B都被集中在原点同一2x2平方。分区A为4个1x1的方格。从每个A <子>豪斯多夫距离我以B为的sqrt（2），但是从A到B的距离为0。

The answer to your other query is no. As an example let A and B both be the same 2x2 square centered at the origin. Partition A into 4 1x1 squares. The Hausdorff distance from each A_i to B is sqrt(2), but the distance from A to B is 0.

更新：关于顶点的索赔不能立竿见影，所以我会画出一个证明，是维任意数量有限不错。结果我想证明的是，在计算 D（A，B）既多边形和 B 凸，它足以找到从 A 的顶点的距离为 B 。 （最接近的点 B 可能不是一个顶点，但最远的点之一 A 必须是一个顶点。）

UPDATE: The claim about the vertices is not immediately obvious, therefore I'll sketch a proof that is good in any finite number of dimensions. The result I am trying to prove is that in calculating d(A, B) with both polygons and B convex, it suffices to find the distances from the vertices of A to B. (The closest point in B might not be a vertex, but one of the farthest points in A must be a vertex.)

由于两者都是有限的封闭图形，它们是紧凑。从紧凑，也必须存在于 A 点 P 就是尽可能从乙。从紧凑，必须存在一个点①在 B 是尽可能接近到 A 。

Since both are finite closed shapes, they are compact. From compactness, there must exist a point p in A that is as far as possible from B. From compactness, there must exist a point q in B that is as close as possible to A.

这距离为0仅当 A 和 B 是相同的多边形，在这种情况下，很显然，我们实现这一目标的距离为 A 的顶点。因此，不失一般性，我们可以假定有一个从 P 积极的​​距离①。

This distance is 0 only if A and B are the same polygon, in which case it is clear that we achieve that distance at a vertex of A. So without loss of generality we may assume that there is a positive distance from p to q.

绘制平面（在更高层次，某种超平面）触及①垂直于从 P 到①。可以在 B 任何时候跨过这架飞机？那么，如果有一个，说研究，那么每一个点上的线段从①到研究必须在 B ，因为 B 是凸的。但它是容易证明，必须有这个线段更接近 P 比① A点，矛盾①的定义。因此 B 无法跨越这架飞机。

Draw the plane (in higher dimensions, some sort of hyperplane) touching q that is perpendicular to the line from p to q. Can any point in B cross this plane? Well if there was one, say r, then every point on the line segment from q to r must be in B because B is convex. But it is easy to show that there must be a point on this line segment that is closer to p than q is, contradicting the definition of q. Therefore B cannot cross this plane.

显然 P 不能是内部点，因为如果它，然后继续沿着从①的射线 P ，你会发现在 A 点是从的平面远的乙的背后是有界的，矛盾 P 的定义。如果 P 是 A 的一个顶点，那么结果就是平凡真实的。因此，唯一有趣的例子是，如果 P 是 A 的边界，但不是一个顶点。

Clearly p cannot be an interior point, because if it was, then continue along the ray from q to p and you find points in A that are farther from the plane that B is bounded behind, contradicting the definition of p. If p is a vertex of A, then the result is trivially true. Therefore the only interesting case is if p is on a boundary of A but is not a vertex.

如果是这样，那么 P 是在表面上。如果表面不平行构建了飞机，这将是很容易沿着表面移动，离我们有界 B 后面的飞机，并找到点越来越远从 B 比 P 。因此该表面必须是平行于该平面。由于 A 是有限的，即表面必须在顶点终止的地方。这些顶点从平面 P 相同的距离，因此，至少从 B，据为 P 。因此，存在的 A 就是尽可能从 B 。

If so, then p is on a surface. If that surface were not parallel to the plane we constructed, it would be easy to travel along that surface, away from the plane we have bounded B behind, and find points farther away from B than p. Therefore that surface must be parallel to that plane. Since A is finite, that surface must terminate in vertices somewhere. Those vertices are the same distance from that plane as p, and therefore are at least as far from B as p. Therefore there exists at least one vertex of A that is as far as possible from B.

这就是为什么它足以找到从多边形的其他多边形的顶点的距离的最大值。

That is why it sufficed to find the maximum of the distances from the vertices of the polygons to the other polygon.

（我离开构造一对多边形与①不是一个顶点作为一个有趣的练习留给读者。）

(I leave constructing a pair of polygons with q not a vertex as a fun exercise for the reader.)

这篇关于凸多边形的豪斯多夫距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！