从点到多边形的距离

Question

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

如果该点位于多边形内或多边形外部,其距离小于用户定义的常量d,则该过程应返回True; False除此以外.

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

我想应该有一个方法比偏移多边形更简单,d并确定它在多边形内部或外部.

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

Answer 1

根据@ jcaron的评论进行了修正

您最好的选择是迭代所有线并找到从点到线段的最小距离.

要找到从点到线段的距离,首先要通过拾取任意点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))

  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)

Answer 2

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