从点到多边形距离 [英] 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 ，程序应该返回小真; 假否则。

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.

我找到了一个类似的问题：<一href="http://stackoverflow.com/questions/2433298/distance-from-a-point-to-a-polyhedron-or-to-a-polygon">Distance从点到多面体或多边形。但是，空间的二维在我的情况和多边形可以是凹的，所以它是从一个有些不同。

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.

任何算法，code，或暗示对我来说，谷歌周围将AP preciated。

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），其中 的点积。通过 || P0-P1 || ^ 2 除以这个值，并获得价值研究。

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 ||P0-P1||^2 and get a value r.

现在，如果你选择 P1 和 P2 为你的观点，你可以简单地检查研究介于0和1。如果研究大于1，则 P2 是最接近的点，所以你的距离 || P0-P2 || 。如果研究小于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℃，为r 1 ，那么你的距离的sqrt（|| P0-P1 || ^ 2 - R * || P2 -P1 || ^ 2）

伪code是如下：

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(x - p1))

  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屋！