点到多边形的距离

一尘不染

点到多边形的距离

algorithm

我试图确定2D空间中从点到多边形的距离。该点可以在多边形内部或外部。多边形可以是凸的或凹的。

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

我发现了一个类似的问题：从点到多面体或多边形的距离。但是，在我的情况下，该空间为2D，多边形可以是凹形的，因此与该多边形有所不同。

我想应该有一种比通过d确定多边形的内部或外部偏移多边形更简单的方法。

任何算法，代码，或提示我谷歌周围将不胜感激。

阅读 578

2020-07-28

共1个答案

一尘不染

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

要找到从点到线段的距离，您首先要通过选择任意点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)

2020-07-28