26

我正在尝试确定二维空间中点到多边形的距离。该点可以在多边形内部或外部；多边形可以是凸的或凹的。

如果该点在多边形内或多边形外且距离小于用户定义的常数d，则程序应返回True；False否则。

我发现了一个类似的问题：Distance from a point to a polyhedron or to a polygon。但是，在我的情况下，空间是 2D 的，并且多边形可以是凹的，所以它与那个不同。

我想应该有一种比将多边形偏移d并确定它在多边形内部还是外部更简单的方法。

我将不胜感激任何算法、代码或提示。

4

6 回答 6

29

最好的办法是遍历所有线并找到从点到线段的最小距离。

要找到从点到线段的距离，首先通过选择任意点P1和线上的点来找到从点到线的距离P2（使用端点可能是明智的）。然后将向量从P1到您的点P0并找到点积(P2-P1) . (P0 - P1)在哪里。.将此值除以||P2-P1||^2得到一个值r。

现在，如果您选择P1和P2作为您的点，您可以简单地检查是否r在 0 和 1 之间。如果r 大于 1，那么P2是最近的点，所以您的距离是||P0-P2||。如果r小于 0，那么P1是最近的点，所以你的距离是||P0-P1||。

如果0<r<1，那么你的距离是sqrt(||P0-P1||^2 - (r * ||P2-P1||)^2)

伪代码如下：

for p1, p2 in vertices:

  var r = dotProduct(vector(p2 - p1), vector(x - p1))
  //x is the point you're looking for

  r /= (magnitude(vector(p2 - p1)) ** 2)

  if r < 0:
    var dist = magnitude(vector(x - p1))
  else if r > 1:
    dist = magnitude(vector(p2 - x))
  else:
    dist = sqrt(magnitude(vector(x - p1)) ^ 2 - (r * magnitude(vector(p2-p1))) ^ 2)

  minDist = min(dist,minDist)
于 2012-06-11T16:32:11.453 回答
2

如果你有一个工作点到线段的距离函数，你可以用它来计算从点到多边形每个边的距离。当然，您必须首先检查该点是否在多边形内。

于 2012-06-11T16:27:19.297 回答
1

您需要快速还是简单？
在边缘情况下它是否必须始终绝对正确，或者大多数时候足够好就可以了？

典型的解决方案是找到每个顶点的距离并找到具有最小值的对（请注意，对于凸多边形外部的点，这些点可能不相邻），然后检查每个线段的点到线交叉点。

对于大型复杂形状，您还可以存储近似多边形边界框（矩形或六边形）并在检查更多细节之前找到最近的边。

您可能还需要代码来处理恰好在一行中的特殊情况。

于 2012-06-11T16:37:07.170 回答
1

如果这对其他人有帮助，我对doverbin 的答案进行了逆向工程，以了解为什么它以图形方式显示这三个案例正在计算的内容。（doverbin，如果您愿意，请随时将其合并到您的答案中。）

多弗宾答案的图形描述

于 2021-12-05T21:39:56.070 回答
0

我可以帮助你解决这个问题：

和一些评论：

  • 正如马丁贝克特的回答指出的那样，您应该只检查最近的点，因为另一段可以“预测”非常接近，但实际上并不需要接近。
于 2012-06-11T16:53:48.943 回答
0

我不知道其他答案的性能差异，但在 boost C++ 库中有一个名为distance的通用实现。它在每种情况下都有关于复杂性的信息，在您的问题情况下它是线性的。

几天前我也在寻找这个问题的解决方案，我想分享这个发现。希望它对某人有所帮助。

于 2019-07-30T08:18:48.560 回答