判断平面多边形和平面上一点的位置关系

pacoyang

平面上有个多边形，不一定是凸多边形。平面上还有一点。如何判断点在多边形内？或外？或在多边形上。

xuxu1457

这点和n边形的每一边组成三角形，如果这n个三角形面积之和大于多边形的面积就在多边形外；反之就在多边形内

lin2009

容易验证2#的论述仅对凸多边形的情况成立。
其它情况不成立。

bainhome

刚才搜索了一下，这个问题好像十分棘手，似乎思路都是基于凸多边形假设，在此基础上才考虑剩余条件。

feynmand

本帖讨论基于如下假设：

已知多边形各顶点的顺时针或者逆时针排列顺序。也就是说顺着边走知道下一个顶点是哪个顶点，所对应的坐标是什么。


推论：可以通过计算各边的斜率，进行比较可以得到这个多边形是凸的还是凹的。（凸边形斜率变化是“单调”的）


如果是凸边形的话：通过该点和与边一个端点做直线，比较这个直线和所对应边的斜率大小，可以得到这个点在边的“左边”还是“右边”的逻辑值，比较点和所有边的关系，求逻辑与，如果这个点在所有边的左边或者右边那么它就在四边形内部。如果不符合就在外部。


---------------------------不确定的分界线---------------------------------

下面的想法不成熟，未证明是否严谨
如果是凹的N边形，
1，那么判断的时候如果点在N-1边的左边，其中1条边的右边，那么这个点也是在N边形内的。
2，如果在所有边的左边或者右边同凸边形一样，也是在N边形内部的。

按照我说的这样子编程的时候只需要将各顶点坐标按照正确的顺序循环相减相比应该就差不太多了，不会需要太多额外其他公式，计算量应该比较小。

xuxu1457

如果有一个凹角还好办，关键是如果有多个凹角 还真是没什么好办法，看来最好是把凹多边形分割成多个凸多边形 然后判断
先顺序n个边，判断是不是凹角，是凹角就连接凹角节点和初始节点分割成两个 然后定凹角处节点为初始节点 以此类推可以把凹多边形分割为多个凸多边形

然后判断点是不是在某一分割好的凸多边形内 如果都不在则点在原多边形外 反之在多边形内

feynmand

之前我没有考虑多个凹角的情况，这样的情况该如何做还有待考虑。

qibbxxt

我觉得可以借鉴一下window系统自带的画图的填充功能，当你在任意图形的面部点一下的时候，就会填充内部，点在外部就会填充外部

rocwoods

doc inpolygon

bainhome

今天出去顺道遛了遛书城，以为是个图论的问题，找了半天也没找到相关内容，倒是自己想到自点向上竖个单位法向量，然后算夹角，也不知道可行否。
没想到MATLAB有现成命令，甚至居然还是MATLAB Toolbox关于graphic的函数，郁闷。
再谢rocwoods，今天的MVP，呵呵。

penultimate

1. 从该点向：上/下/左/右 任意一个方向左射线
  其实，只要从该点向任意方向作射线都可以，之所以选择4个特殊方向，是为了后续的求交点
  方便。4个特殊方向的求交点运算可以直接通过判断坐标大小实现，不需要真的进行计算。
2. 对多边形每个边的线段，求和射线的交点，统计交点的个数
  如果交点在边界上，就可以直接退出，不需要继续判断了
3. 如果交点的个数为奇数了，说明该节点在区域内；否则，在区域外。
以上算法适用于任意单连通域，对凸凹没有任何限值

rocwoods

10# bainhome
呵呵，MVP谈不上，主要是工作用过这个函数，老是要圈一个区域判断哪些点在区域内哪些点不在。MATLAB的inpolygon效率还是不错，判断几十万个点是否在一个8变形内很快就完成了。网上应该也有现成的一些C++函数

bainhome

我想很多射击游戏，网络地图等，一定都要用到此函数的算法。
刚看了看，inpolygon函数还不是built-in，如果如你所述，效率还是很拽的。

pacoyang

matlab很强大，论坛也很强大。
谢谢各位