点到多边形的距离 [英] Distance from a point to a polygon

问题描述

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

I am trying to determine the distance from a point to a polygon in 2D space. The point can be inside or outside the polygon; The polygon can be convex or concave.

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

If the point is within the polygon or outside the polygon with a distance smaller than a user-defined constant d, the procedure should return True; False otherwise.

我发现了一个类似的问题:点到多面体或多边形的距离.但是，在我的情况下，空间是 2D 的，并且多边形可以是凹的，所以它与那个空间有些不同.

I have found a similar question: Distance from a point to a polyhedron or to a polygon. However, the space is 2D in my case and the polygon can be concave, so it's somehow different from that one.

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

I suppose there should be a method simpler than offsetting the polygon by d and determining it's inside or outside the polygon.

任何算法、代码或提示我都可以用谷歌搜索.

Any algorithm, code, or hints for me to google around would be appreciated.

推荐答案

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

Your best bet is to iterate over all the lines and find the minimum distance from a point to a line segment.

要求点到线段的距离，首先要在直线上选取任意点P1和P2来求点到直线的距离(使用端点可能是明智的).然后将矢量从 P1 带到您的点 P0 并找到 (P2-P1) .(P0 - P1) 其中 . 是点积.将此值除以 ||P2-P1||^2 并得到一个值 r.

To find the distance from a point to a line segment, you first find the distance from a point to a line by picking arbitrary points P1 and P2 on the line (it might be wise to use your endpoints). Then take the vector from P1 to your point P0 and find (P2-P1) . (P0 - P1) where . is the dot product. Divide this value by ||P2-P1||^2 and get a value r.

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

Now if you picked P1 and P2 as your points, you can simply check if r is between 0 and 1. If r is greater than 1, then P2 is the closest point, so your distance is ||P0-P2||. If r is less than 0, then P1 is the closest point, so your distance is ||P0-P1||.

如果0，那么你的距离是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)

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