Question

求问Matlab里inpolygon函数的数学原理。

因为需要在fortran里判断一个点是否在多变形区域内，所以想把inpolygon函数改写成fortran程序……但是只能看懂函数里单个语句的意思，完全不明白原理。在matlab论坛里看其他inpolygon函数相关的帖子，有人说：
“可以这样实现， 首先给定该多边形顺时针采样的序列： C{c1, ..., cn}

令待求点为p, 计算p的特征行列式序列：{|pci, pc(i+1)|}如果这个序列恒正， 则p在多边形内， 否则位于多边形外。这种方法还可以推广到多维， 如一个点是否在一个n维的几何体内。”

虽然不明白，但是我感觉inpolygon用的好像就是这种方法，里面有计算点乘和叉乘的语句。求解释！

如果有更好的方法也请说明……

Answer 1

 首先给定该多边形顺时针采样的序列： C{c1, ..., cn}；
令待求点为p, 计算p的特征行列式序列：{|pci, pc(i+1)|}；

如果这个序列恒正， 则p在多边形内， 否则位于多边形外。这种方法还可以推广到多维， 如一个点是否在一个n维的几何体内。

Examples

L = linspace(0,2.*pi,6); xv = cos(L)';yv = sin(L)';

xv = [xv ; xv(1)]; yv = [yv ; yv(1)];

x = randn(250,1); y = randn(250,1);

in = inpolygon(x,y,xv,yv);

plot(xv,yv,x(in),y(in),'r+',x(~in),y(~in),'bo')

Answer 2

如果多边形的每个角的点已经按一顺时针排列（逆时针也可以）
matlab里用的有叉乘的，是用向量计算的办法

要判断某点P(x,y)是否在多边形内C｛c1,c2,...cn}内
可以计算P到顺序相邻两点的向量的差乘值 Pc1Xc2 Pc2XPc3 .... Pcn-1XPcn PcnXPc1

如果在多边形里面 这些叉积都是 取相同符号的
如果符号相同中还有0值，表示在多边形边上
如果有正，有负表明点P在多边形外

Answer 3

一般用转角法（弧长法）来判别被测点与多边形的关系
方法是以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其在单位圆上弧长的代数和
其实就是点乘向量的arccos函数值之和
外部是0，内部是2π，边上为π
这里有源代码，不过是C++的
http://wenku.baidu.com/link?url=BVISYea6fMtlvNABa0t4lu6XK3E2ALqJ5zH-JYuekHsrnXdbcxLfPDr3hwLuhVGugsuv6UuPrmzzkJy5B8j7i58umBq19lu7QYSrCmDf0de