如何判断一个点（坐标已知）是在一个多边形（包括凸多边形和凹多边形）内部还是外部？(200分)

zht · 2001-05-18

在进行判断时，如果是凸多边形，比较容易，可以通过判断经过此点的水平，或
垂直线的在此点一侧的交点个数，进行判断，但是如果是凹多边形，情况就比较
复杂，包含各种情况，所以请各位大侠赐教，不胜感激，200大洋双手送上

creation-zy · 2001-05-18

计算机图形学的书上肯定有的。
以前也讨论过：LID=093903
用“多边形”搜索一下离线数据库的CHM嘛。

redcony · 2001-05-18

如果用射线法凸多边形和凹多边形是一样的啊？只不过遇到水平线与边的交点在多边形顶点
时需要加以区别才是

sportsman · 2001-05-18

这样：
先在待测点和多边形之外的一个已知点之间作一条直线线段。（找外点可以取x坐标小于
所有多边形各顶点的x坐标的最小值）然后计算该直线线段与多边形各边的相交次数。
如果为奇数则点在多边形内，反之则在多边形内。

sportsman · 2001-05-18

补充：
如果交点同时也是多边形的顶点，必须察看该顶点相遇的两邻边的另外两个端点的情况。
如果这两个端点都在所作的直线线段的同测，那么该顶点相交的次数应按照偶数计算。
如在两侧，按奇数计算！

sportsman · 2001-05-18

呵呵，又看了一遍图形学，觉得虚度大学时光真是一种莫大的浪费：（

卷起千堆雪tyn · 2001-05-19

你可以运用API函数：PtInRegion来判断！
多边形点的坐标你已经知道，那么就创建一个区域：CreatePolygonRgn！
明白了么？？？

zht · 2001-05-20

我的问题已经解决，就是使用卷起千堆雪tyn所说的方法，不论是凸多边形还是
凹多边形都是可以可以使用这种方法，是我原来使用上有问题，我一直用Delphi
现在用vb做，不是很熟，但是谢谢大家的热情，分数的分配还算可以吧，希望
能多多交流，我这是第一次问问题。