几何算法问题

来源：百度知道 编辑：UC知道 时间：2024/07/04 12:32:52
一个N边形，给定所有顶点的坐标（x，y）。又知道一个点(a,b)。求该点是否在多边行中。请提供一个你认为最简的算法。

希望一个最好的算法。顶点坐标和已知点坐标都是实数。

首先判断该点是否恰好在多边形的某条边上
如果不在，那么取一个与多边形的所有的边都不平行的方向向量，从(a,b)沿着之前取的向量出发可以得到一条射线
统计该射线与多边形的交点数，如果是奇数，(a,b)就在多边形内，否则在多边形外

统计方法：
用两个整形变量A和B作计数器，先清零
用一个循环顺次处理多边形的每一条边，判断是否和射线相交
如果不相交，不记录
如果相交于这条边的端点，也就是多边形的顶点，又不属于下面所说的特殊情况，那么计数器A增加1
如果相交于边的中间，那么计数器B增加1
最终的交点数是A/2+B个

统计交点的时候有这种特殊情况：
如果射线与多边形恰好相交于多边形的某个顶点，且射线在该顶点两侧的部分都在多边形内侧或外侧，那么忽略这个交点

整个算法时间复杂度是线性的

上面的算法相当的好啊