多边形算法解释中的点

Question

您好，我从 Mathhelpforum 了解到这个算法，它确定一个点是在多边形内部还是外部。到目前为止，代码运行良好，但我不完全理解其中的逻辑。如果你这样做，请提供解释，特别是在方法上......无论是光线投射，还是缠绕数等。谢谢。

function [ inside ] = inpoly(polygon,xt,yt)

rows = size(polygon);
npoints = rows(1);
disp (npoints);
inside = 0;

xold = polygon(npoints,1);
yold = polygon(npoints,2);

for i = 1:1:npoints

   xnew = polygon(i,1);
   ynew = polygon(i,2);

      if (xnew > xold) 
         x1=xold;
         x2=xnew;
         y1=yold;
         y2=ynew;
      else 
         x1=xnew;
         x2=xold;
         y1=ynew;
         y2=yold;
      end

      if ((xnew < xt) == (xt <= xold) & (yt-y1)*(x2-x1) < (y2-y1)*(xt-x1) ) 
               inside=~inside;
      end

      xold=xnew;
      yold=ynew;

end

endfunction

测试功能，例如:

inpoly([p,q],x,y)

其中p和q是多边形的顶点和点的x、y坐标。

Answer 1

对我来说似乎是光线投射。变量 x1、y1、x2、y2 是根据 X 排序的多边形边的端点。条件 (xnew < xt) == (xt <= xold) 测试 Y 平行线是否来自xt,yt 点与边相接。条件的另一部分测试 xt,yt 是否位于多边形一侧的正确一侧。

条件

(yt-y1)*(x2-x1) < (y2-y1)*(xt-x1)

等同于

(yt-y1)*(x2-x1) - (y2-y1)*(xt-x1) < 0

这是一个矩阵行列式

| yt-y1  xt-x1 |
|              | < 0
| y2-y1  x2-x1 |

矩阵是向量叉积

(pointT - point1) times (point2 - point1)

多边形算法解释中的点

Point in polygon algorithm explanation

algorithm

matlab

point

polygon