论坛 › K05：Mathematica › 如何判断平面上任意一点是否在凸多边形范围内？

FreddyMusic 发表于 2011-8-20 23:09:28

如何判断平面上任意一点是否在凸多边形范围内？

平面上已知一个凸包多边形，现有任意一点，

如何判断该点是否在凸多边形范围内？

http://mathworld.wolfram.com/ConvexHull.html

eigen 发表于 2011-8-24 23:33:27

本帖最后由 eigen 于 2011-8-24 23:37 编辑

关于版主提出的这个问题我有两个想法，给大家抛砖引玉。如果有错误，请大家批评指正。

一. 几何方面：
1. 判断这个点P是否在这个平面凸多边形的边上。如果不是，就转到2；
2. 过这个点P引一条直线l, 判断直线l是否交于这个凸多边形的两条边。如果是，则设交点分别为Q,M，转到3；
3. 判断点P是否在线段QM的内部，如果是，则点P在这个凸多边形的内部。

二. 线性代数方面：
1. 设这个平面凸多边形的顶点分别是P_1,P_2,...,P_n，原点为O。判断向量OP是否能由向量组OP_1,OP_2,...,OP_n所线性表示。如果能，则转到2；
2. 判断以上线性表示的系数是否都在半闭半开区间[0,1)内。如果是，并且至少有2个系数不为0，则点P在这个凸多边形的内部。

FreddyMusic 发表于 2011-8-25 09:47:47

看这个, http://demonstrations.wolfram.com/AmIInAPolygon/

但是这里面有些小 Bug .

guocong89 发表于 2011-8-25 14:14:39

计算几何里最常用的方法是射线法。自该点向明显位于该多边形外部的一点做射线，判断该射线与多边形的交点数目，若为奇数即为在多边形内部，对非凸多边形也成立，算法复杂度为O(n)，如果恰好通过顶点，要么考虑换个方向重新做射线，要么只考虑一条边。

查看完整版本: 如何判断平面上任意一点是否在凸多边形范围内？