Python和科学计算认证群组 - 讨论区
标题：如何编程判
2012年02月05日 星期日 00:20
这应该算是一个数学问题。拿到这里来请教大家，是因为我在编程中遇到了，我想知道有没有简单的实现方法。
不知道题目说清楚了没有，我再举个例子：
已知4个点坐标分别为：P(0,0),A(1,0),B(-1,1),C(0,1)，ABC三点构成凸多边形（三角形），问点P是否在该多边形内部？
数据是动态的，多边形的顶点会改变，边数会改变。有没有一种普适的且易于编程实现的判别方法。
2012年02月05日 星期日 05:20
如果是凸多边形：
对于任意边AB ，找出离AB最远的顶点M，通过方程 M+t×MP = H 计算t（t是数量）， H在AB上。如果对于任意AB如果t>0则 P在内，否则在外。
这是我突然想到的。希望各位高人指正。。
2012年02月05日 星期日 06:56
matplotlib提供了这样的函数，你可以参考：
http://matplotlib.sourceforge.net/faq/howto_faq.html#test-whether-a-point-is-inside-a-polygon
如果是算法的话，可以看看：
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
2012年02月05日 星期日 17:19
1.对比x和y的值，不在range(x),range(y)内直接PASS
2.在内的话，三个点就按三个的算，多于三个的直接以坐标最靠外四个点做四边形，判断。
2012年02月05日 星期日 21:31
非常感谢楼上三位的帮忙!
我最终使用了若愚大哥说的matplotlib函数。
请教1楼：你说的方法好像不是对任意边AB，而是至少存在一个这样的边AB。（H在AB内部）
请教3楼：感觉你的思路挺好！我对“最靠外四个点”不太理解是何意，能否再解释一下
2012年02月06日 星期一 00:58
我也没太看懂3楼第二步所说。。。希望能具体说一下。
2012年02月06日 星期一 01:05
对于你所说的三角形， 如果点（0，0.5），对于CA边CA边算出t为正，但是对于BA边算出t为负
另外我又想了想，不用每条边运算。
只用选任意一顶点V，计算VP与所有边Vi-Vj的交点H_ij（当然含点V的边除外），对于点H_ij ∈ ViVj
然后算t，然后判断。
刚才5的回复有点问题。。又删不掉，请管理员帮忙。
2012年02月06日 星期一 01:22
另外一种方法
对于多边形Pn，找到P_x(i)>=P_x>P_y(i+1) P_x(j)<=P_x<P_y(j+1) 说明在x上的投影在内
只用判断P是否在四边形P(i)P(i+1)P(j)P(j+1)内就行了。
2012年02月06日 星期一 08:28
最外缘四个点：
A:min(x)
B:min(y)
C:max(x)
D:max(y)
2012年02月10日 星期五 10:34
好像有一个扩展到n边行的方法，我2006年的时候见过。我帮你找找。
2012年02月10日 星期五 10:41
因为是凸边行，所以：
如果定点位于内部，则顺时针顶点和定点的连线间的顺时针夹角之和等于360度；
如果定点位于外侧，则顺时针顶点和定点的连线间的顺时针夹角之和必然大于360度。
2012年02月10日 星期五 13:42
感谢11楼周正！这方法很帅！
2012年02月10日 星期五 22:13
凸边行是使问题得以简化的关键所在。我06年见过的那个关于地理信息系统(GIS)的问题好像不只是凸边行的。当时，我也是假装数学专家，给学习GIS的MM讲解了很久。终于明白了。你有空可以去查查。GIS方面好像对这个问题有很深入的研究。
Zeuux © 2024
京ICP备05028076号