基于减治的点与凸多边形位置关系判定算法

张 浩， 沈 华,2， 谌 刚

(1湖北工业大学计算机学院， 湖北 武汉 430068；2 桂林电子科技大学广西可信软件重点实验室，广西 桂林 541004)

随着位置感知移动终端的普及，基于位置的服务(Location-Based Service, LBS)给人们的生活带来了极大的便利[1]。近年来，几何范围查询在LBS应用中被广泛应用。判断点与凸多边形的位置关系是几何范围查询的一种基本操作。例如LBS的典型应用——近邻检测服务，该服务允许用户在地图上选择一个特定的几何范围，然后询问他的朋友是否在这个范围内。通常将用户选定的几何范围抽象为凸多边形，将用户朋友的位置抽象为一个点，通过判断点与凸多边形的位置关系来解决近邻检测问题。目前判断点与凸多边形位置关系的方法有：计算点的方位[2]、射线法[3]、夹角法[4]、面积法[5]等。相关工作见文献[6-17]。但这些方法普遍存在计算效率不高的问题。目前，人们通常通过移动设备(如智能手机、平板电脑、手环等)去请求LBS，移动设备存在资源受限的特点，因此，上述方法都不适合直接应用于LBS。在射线法中，通过给定点引出一条射线，计算该射线与凸多边形的交点数，若交点的数为奇数，则坐标点在凸多边形内部，否则坐标点在凸多边形外。但当给定点位于凸多边形边上时，该方法存在误判的可能性。因此，设计轻量级算法正确求解点与凸多边形位置关系判定问题是一个值得研究的问题。

为了减少算法的计算开销，本文运用了减治思想，通过减少问题求解过程中与点进行位置关系判断的边的条数来达到提高问题求解效率的目标。基于该思路，本文提出了一种轻量级点与凸多边形位置关系判定算法(称为LRDA)。算法LRDA首先提取凸多边形的四个特征顶点，根据这四个特征顶点对凸多边形进行区域划分，通过判断给定点落在哪个分区内将原问题的判断范围从凸多边形缩小到凸多边形的局部区域，然后调用该分区对应的判断条件对给定点进行位置判定，最终得到点与凸多边形的位置关系。

1 算法阐述

1.1 问题描述

假设给定的凸多边形L具有n个顶点，从纵坐标最大的顶点开始依次进行逆时针编号，假设为{P1,P2,…,Pn}，其坐标分别为(xi,yi)，i=1,2,…,n，并给定一个点P(xp,yp)，判断点P与该凸多边形之间的位置关系，即判断点P是位于凸多边形外部还是位于凸多边形内部。点P位于凸多边形内部包括点P在凸多边形边上的情况。

1.2 算法设计

1.2.1凸多边形区域划分首先找出凸多边形L的最上顶点、最左顶点、最下顶点、最右顶点四个特征顶点，分别表示为P1、Pl、Pd、Pr(图1)。根据问题描述中的顶点编号规则可知1≤l≤d≤r≤n。然后，过最左顶点Pl(xl,yl)和最右顶点Pr(xr,yr)作与X轴平行的直线，过最上顶点P1(x1,y1)和最下顶点Pd(xd,yd)作与Y轴平行的直线，将凸多边形L划分为图2所示的5个区域。第1个分区对应于图2中的空白区域，如果点P落入这个区域，则说明点P在凸多边形的外部。第2个分区对应于图2中标注为Ⅰ的阴影区域、第3个分区对应于图2中标注为Ⅱ的阴影区域、第4个分区对应于图2中标注为Ⅲ的阴影区域、第5个分区对应于图2中标注为Ⅳ的阴影区域，如果点P落入这些区域，则需要进一步判断点P与凸多边形的位置关系。

图1 凸多边形示意图

图2 凸多边形划分示意图

1.2.2点的区域判断这里分别给出点P落入上述5个区域的判断条件。

判断条件1：点落入空白区域。如果ypy1或者xpxr，那么点P(xp,yp)落入空白区域(图3)。

图3 点P落入空白区域示意图

判断条件2：点落入阴影区域Ⅰ。如果xi≤xp≤x1且yl≤yp≤yi，那么点P(xp,yp)落入阴影区域Ⅰ(图4)。

(a)点在区域Ⅰ的凸多边形内

(b)点在区域Ⅰ的凸多边形外图4 点P落入阴影区域Ⅰ示意图

判断条件3：点落入阴影区域Ⅱ。如果xi≤xp≤xd且yd≤yp

(a)点在区域Ⅱ的凸多边形内

(b)点在区域Ⅱ的凸多边形外图5 点P落入阴影区域Ⅱ示意图

判断条件4：点落入阴影区域Ⅲ。如果xd≤xp≤xr，即点P(xp,yp)落入阴影区域Ⅲ(图6)。

(a)点在区域Ⅲ的凸多边形内

(b)点在区域Ⅲ的凸多边形外图6 点P落入阴影区域Ⅲ示意图

判断条件5：点落入阴影区域Ⅳ。如果x1≤xp≤xr且yr≤yp≤y1，那么点P(xp,yp)落入区域Ⅳ(图7)。

(a)点在区域Ⅳ的凸多边形内

(b)点在区域Ⅳ的凸多边形外图7 点P落入阴影区域Ⅳ示意图

1.2.3点的位置关系判断根据点落入不同的区域对点与凸多边形的位置关系进行判断。

情况1：如果判断条件1成立，则说明给点P位于凸多边形L的外部。

情况2：如果判断条件2成立，则调用子算法1。子算法1：点的位置关系判断(阴影区域Ⅰ)。

输入：凸多边形顶点{P1,P2,…,Pl}和点P。

输出：点P与凸多边形的位置关系。

Step1.在顶点{P1,P2,…,Pl}中找到相邻的两个顶点Pi和Pi+1，使得xi+1≤xp≤xi，其中1≤i≤l-1；

Step2.计算过顶点Pi和Pi+1的直线，用符号f1(x)表示该直线；

情况3：如果判断条件3成立，则调用子算法2。

子算法2：点的位置关系判断(阴影区域Ⅱ)

输入：凸多边形顶点{Pl,Pl+1,Pl+2,…,Pd}和点P。

输出：点P与凸多边形的位置关系

Step1.在顶点{Pi,Pl+1,Pl+2,…,Pd}中找到相邻的两个顶点Pi和Pi+1，使得xi≤xp≤xi+1，其中l≤i≤d-1；

Step2.计算过顶点Pi和Pi+1的直线，用符号f2(x)表示该直线；

Step3.如果yp≥f2(xp)(对应图5a所示情况)，则点P位于凸多边形L的内部，否则(对应图5b所示情况)点P位于凸多边形L的外部。

情况4：如果判断条件4成立，则调用子算法3。

活性炭的吸附性能在很大程度上取决于孔结构特征。根据用途和应用领域的要求对活性炭的孔结构进行调控，定向制备活性炭，已成为目前活性炭领域研究的热点。

子算法3：点的位置关系判断(阴影区域Ⅲ)

输入：凸多边形顶点{Pd,Pd+1,Pd+2,…,Pr}和点P

输出：点P与凸多边形的位置关系

Step1.在顶点{Pd,Pd+1,Pd+2,…,Pr}中找到相邻的两个顶点Pi和Pi+1，使得xi≤xp≤xi+1，其中d≤i≤r-1。

Step2.计算过顶点Pi和Pi+1的直线，用符号f3(x)表示该直线；

Step3.如果yp≥f3(xp)(对应图6a所示情况)，则点P位于凸多边形L的内部，否则(对应图6b所示情况)点P位于凸多边形L的外部。

情况5：如果判断条件5成立，则调用子算法4。

子算法4：点的位置关系判断(阴影区域Ⅳ)

输入：凸多边形顶点{Pr,Pr+1,Pr+2,…,Pn,P1}和点P

输出：点P与凸多边形的位置关系

Step1.若x1≤xp≤xn，则选中顶点Pn和P1，否则在顶点{Pr,Pr+1,Pr+2,…,Pn}中找到相邻的两个顶点Pi和Pi+1，使得xi+1≤xp≤xi，其中r≤i≤n-1；

Step2.若选中的顶点为Pn和P1，则计算过顶点Pn和P1的直线，否则计算过顶点Pi和Pi+1的直线，用符号f4(x)表示计算得到的直线；

Step3.如果yp≤f4(xp)(对应图7a所示情况)，则点P位于凸多边形L的内部，否则(对应图7b所示情况)点P位于凸多边形L的外部。

1.2.4算法描述所提出的基于减治思想的点与凸多边形位置判定算法描述如下。

算法LRDA：(点与凸多边形的位置关系判断)

输入：具有n个顶点的凸多边形和点P

输出：点P与凸多边形的位置关系

Step1.对给定凸多边形进行区域划分；

Step2.判断点落在哪个区域；

Step3.如果点落在空白区域，则立即返回点P位于凸多边形外部；如果点P落在阴影区域Ⅰ，则调用子算法1；如果点P落在阴影区域Ⅱ，则调用子算法2；如果点P落在阴影区域Ⅲ，则调用子算法3；如果点P落在阴影区域Ⅳ，则调用子算法4。

2 算法分析

本小节给出算法LRDA的时间复杂度分析。算法LRDA中Step1的时间开销主要花费在找最上顶点、最下顶点、最左顶点和最右顶点上。可以先将所有顶点按照x坐标和y坐标分别进行排序，此过程可以在O(nlogn)时间内容完成；然后，我们可以在O(1)时间内找到上述四个特征顶点。因此，算法LRDA中Step1的时间复杂度为O(nlogn)。显然，算法LRDA中Step2的时间开销为O(1)。算法LRDA中Step3的时间开销分析需要考虑点落到5个分区的概率分布。用E1表示点落在空白区域(即图2中的空白区域)的事件，用E2表示点落在非空白区域(即图2中的4个阴影区域)的事件，则有:

3 算法实施

实施场景1：基于位置服务中的近邻好友判断。

场景描述：用户A在某商圈逛街，想知道其好友B是否也在该商圈范围内。此场景下，算法LRDA在位置服务器上运行，算法的输入分别来自用户A和用户B，其中用户A的输入被抽象为一个凸多边形，用户B的输入被抽象为一个点。

实施场景2：移动服务站最佳运营路线。

场景描述：服务型公司C为了更好地服务于其客户，决定设置移动服务站点。为了充分发挥移动服务站的作用，需要给出移动服务站每个时间段的最佳服务地点。公司C可以通过执行算法LRDA获得移动服务站的最佳运营路线。首先，公司C确定时间段和选出几个候选区域范围；然后，公司C通过执行算法LRDA统计出不同时间段出现在候选区域内的客户人数；最后根据统计结果得到移动服务站的最佳运营路线。此场景下，公司C执行在给定的时间段内执行算法LRDA，算法的输入分别为公司C选定的候选区域和客户的当前位置。

4 结束语