algorithm - 点到多边形的距离

Question

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

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

我发现了一个类似的问题:Distance from a point to a polyhedron or to a polygon .然而，在我的例子中，空间是二维的，多边形可以是凹的，所以它与那个多边形有些不同。

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

如果有任何算法、代码或提示可供我谷歌搜索，我们将不胜感激。

Answer 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)