点在多边形算法说明

嗨我碰到这个算法从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坐标。

来源

2015-04-07 Simon Hanks

似乎射线给我。变量x1,y1,x2,y2是相对于X排列的多边形端点。条件(xnew < xt) == (xt <= xold)测试来自点xt,yt的Y平行线是否符合边。条件的另一部分测试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)

来源

2015-04-07 07:01:33 CiaPan

谢谢@CiaPan，现在对我来说更加清晰。 Ray-casting的这种实现看起来相当简单。它在点位于多边形内时起作用，但当点位于边或顶点时不起作用。 –

点在多边形算法说明

回答

相关问题