liub1979 发表于 2004-11-30 12:45:00

问一个问题@_@!

如何判断点在多边形内,还是在多边形外.

lichh_2003 发表于 2004-11-30 15:30:00

这还不容易：经过者点画一条铅垂线，如果有偶数个点，则说明在内部，反之在外嘛。呵呵

lichh_2003 发表于 2004-11-30 15:52:00

liub1979 发表于 2004-12-1 12:57:00

谢谢.我也这样想过,可交点这么求啊

lichh_2003 发表于 2004-12-1 15:32:00

你哪个点为X=a,多边形的各顶点坐标都知道吧，知道两点不就可以建立直线方程了，再就是求交点了

liub1979 发表于 2004-12-29 22:27:00

有更好的方法?铅垂线,"射线"?难咯

mccad 发表于 2004-12-29 22:53:00

画条线应该很容易的事。<BR>求交点也应该很容易的事。<BR>这些在论坛上已经不知发过多少次了。

zfbj 发表于 2005-1-3 20:27:00

点在外部同样可能会有偶数个交点，必须对多个角度的射线或者构造线进行判断。

laoliu09 发表于 2005-1-4 12:01:00

我有一个方法，好不好大家评评看吧！呵呵！只对凸多边形有效）


将多边形各点排列好，存为两个点数组，排列规则都是X坐标最小的点排在第一位，X坐标最大的点排在最后一位，两数组分别按多边形点的顺时针和逆时针排列，就可得到多边形上半区和下半区的点数组，可组成上下半区的直线组，多边形内的点必然在所有上半区直线之下和所有下半区直线之上！这样就可以判断了！


这个方法只对凸多边形有效！呵呵！

laoliu09 发表于 2005-1-4 13:35:00

我的上面那个方法是垃圾！！！


其实有最简单的办法！例如：判断点a是否在n边形内，可以先将n边形的各顶点排好顺序，顺时针或逆时针都可以，然后将a点和n边形各个顶点连结起来，这样就形成n个以点a为顶点的三角形了，如果各三角形顶角之和为360度，则点a在n边形内，否则点a在n边形外！


不知道这个方法是不是最简单的！
页: [1]
查看完整版本: 问一个问题@_@!