Sec*_*ish 6 computational-geometry
给定凸多边形作为n个顶点的逆时针列表,给出O(lgn)算法以确定给定点是否在多边形内.假设基本操作采用O(1).
我认为一个方向:如果一个点位于凸多边形内,那么这些点与所有椎体或边缘之间的特殊关系是什么？此外,我猜这里的技巧是凸多边形,使算法lgn.
AnT*_*AnT 12
我所知道的这个问题的唯一解决方案需要O(n)多边形预处理时间.然后,O(lg n)及时处理针对预处理多边形的每个查询点.
只需P在多边形内部取一个点(让我们称之为"极点"),并为每个顶点绘制一条从P顶点出来并穿过顶点的光线.将其视为原点为的极坐标系,P整个极面由这些光线细分为扇区.现在,根据您的查询点,您只需将其转换为极坐标,原点位于极点P.然后只执行二进制搜索以确定包含查询点的特定扇区.扇区内的最终内/外检查(点对边测试)是一项简单的O(1)操作.每个查询都在O(lg n)二进制搜索所需的时间内处理.
这种方法实际上适用于更大类的多边形,而不仅仅是凸多边形.它涵盖了所谓的星形多边形类,即具有一个点的多边形,多边形的整个内部可以从该点看到或"观察".
在O(n)预处理时间来自于需要事先确定极点的位置.
PS我不得不考虑更普遍的情况.如果多边形是凸的,则可以简单地使用其任何顶点作为极点.这样您就可以立即获得O(lg n)算法,无需预处理.