怎么判断一个点在某个凸多边型的内部？
怎么判断一个点在某个凸多边型的内部？
不规则的多边形
边的条数
顶点都指知道
怎么快速判断给定的一个点在不在其内部？
———–
过一个点作一条直线，求与多边形的交点
———–
[color=Red]我给出的算法：
把顶点和给定点连起来，用向量代数计算夹角。
如果点在多边形内部，那么夹角应该逐渐增大至360度；
如果点在外部，那么夹角应该先增大然后减小到0度。
———–
这个好像是本科图形学的算法，不过计算和各顶点的夹角的算法应该是最简单的了～
———–
计算几何中有的，射线法。
设点为p1，无穷远处某点设为p2，然后逆时针遍历凸多边形的所有边，求交点数
当然改点在边上最好了，否则总的交点数为奇数则p1在凸多边形内部，为偶则在凸多边形的外部。
涉及到其余关于：点在线段上的判断，两线段相交的判断，叉积等等，建议搂主把所有基本关于点，线段，直线等基本算法实现之，然后有关多边形的算法就可简单的调用搞定。
———–
作一条平行于水平(或竖直)轴的直线.如果与多边形没有交点即在外面.如果有一个交点,看点是否在多边形上.如果有两个交点,比三个点横坐标的关系.如果原来的点横坐标在交点之间,则在内,否则在外.
具体的复杂度请各位分析一下?
———–
凸多边形~~
漏了一种情况,这条线和某条边重合.
谢谢~还有吗
———–
画了画没有看到会遗漏啥.
不过还总是要扫描n-1条边获得所有交点信息再判断的.
———–
是的.用计算机处理的话最简单的好像还是计算角度的方法.
———–