[1]张 浩,沈 华,谌 刚. 基于减治的点与凸多边形位置关系判定算法[J].湖北工业大学学报,2022,(5):33-37.
　ZHANG Hao,SHEN Hua,SHEN Gang. Judgment Algorithm for the Position Relationship between Point and Convex Polygon Based on Reduction and Rule[J].,2022,(5):33-37.
点击复制

 基于减治的点与凸多边形位置关系判定算法()
分享到：

《湖北工业大学学报》[ISSN:1003-4684/CN:42-1752/Z]

卷:
期数:
2022年第5期
页码:
33-37
栏目:
湖北工业大学学报
出版日期:
2022-10-25

文章信息/Info

Title:
 Judgment Algorithm for the Position Relationship between Point and Convex Polygon Based on Reduction and Rule
文章编号:
1003-4684(2022)05-0033-05
作者:
 张 浩1;  沈 华1; 2;  谌 刚1
1 湖北工业大学计算机学院， 湖北 武汉 430068；
2 桂林电子科技大学广西可信软件重点实验室，广西 桂林 541004
Author(s):
 ZHANG Hao1;  SHEN Hua 1; 2;  SHEN Gang1
1 School of Computer Science, Hubei Univ. of Tech., Wuhan 430068, China;
2 Guangxi Key Laboratory of Trusted Software, Guilin Univ. of Electronic Tech., Guilin 541004, China
关键词:
 ; 减治法;  凸多边形;  区域判断;  位置关系判定算法
Keywords:
 ; decrease-and-conquer;  convex polygon;  region judgment;  position relation determination algorithm
分类号:
TP3
文献标志码:
A
摘要:
 人们利用移动设备享用的很多位置服务涉及点与凸多边形位置判定问题。移动设备资源受限的客观条件使得设计轻量级算法解决该问题成为当务之急。寻找一种轻量级的判定算法是必要的，减少与点进行操作的边的条数成为一种可行思路。因此，基于减治思想提出了一种轻量级点与凸多边形位置关系判定算法。算法包括三个模块：区域划分、点的区域判断和点与凸多边形的位置关系判断。算法通过将点与凸多边形的位置关系判断转化为点与凸多边形的部分区域位置关系判断，减少了时间开销。通过将凸多边形的顶点编序并划分为多个子区域作为算法的预处理部分，算法的时间开销可以达到O(log〖KF(〗n〖KF)〗)。本算法可以适用在移动设备资源受限的场景下快速进行点与凸多边形的位置关系判断。
Abstract:
 Many location-based services used by people involve the problem of determining the positional relation between points and convex polygons. The limited resources of mobile devices make lightweight algorithms designed to resolve the above issue to be an urgent problem. Therefore, finding a lightweight decision algorithm is necessary, and reducing the number of edges that operate on points has become a feasible idea. Therefore, a lightweight algorithm of position relationship determination between a point and a convex polygon is proposed based on reduction and governance. The algorithm includes: region division, region judgment of a point, and position relationship judgment between a point and a convex polygon. The algorithm converts the position relationship judgment between a point and a convex polygon into the position relationship judgment between the point and a part of the convex polygon, which reduces the time cost. By sorting vertexes of the part of the convex polygon beforehand, the time cost of our algorithm can achieve O(logn). This algorithm can be applied to determine quickly the position relationship between points and convex polygons in scenarios where mobile device resources are limited.

参考文献/References:

[1] SHEN H, ZHANG M W, WANG H, et al. A lightweight privacy-preserving fair meeting location determination scheme[J]. IEEE Internet of Things Journal, 2020, 7(4): 3038-3093.
[2] FEITO F, TORRES J C, UREA A. Orientation, simplicity, and inclusion test for planar polygons[J]. Compute. Graph., 1995, 19(4): 595-600.
[3] GALETZKA M, GLAUNER P O. A simple and correct even-odd algorithm for the point-in-polygon problem for complex polygons[C]. ∥The 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017). Porto, Portugal, 2017，175-178.
[4] HORMANN K, AGATHOS A. The point in polygon problem for arbitrary polygons[J]. Computational Geometry, 2001, 20(3): 131-144.
[5] 陈振华, 李顺东, 黄琼, 等. 两个保密位置判断问题的新解法[J]. 计算机学报, 2018, 41(2): 336-348.
[6] ZHU H, WANG F, LU R, et al. Efficient and privacy-preserving proximity detection schemes for social applications[J]. IEEE Internet of Things Journal, 2018, 5(4): 2947-2957. 
[7] 孙爱玲, 赵光华, 赵敏华,等. 基于sign(x)函数的点在多边形内外判别算法及应用[J]. 计算机工程与科学, 2017, 39(4): 785-790.
[8] 马晨,张毅.一种改进的点与多边形关系的叉乘判别法[J]. 测绘科学, 2013, 38(1): 125-127.
[9] 柳珍. 一种夹角和法结合叉乘法判定点与任意多边形位置关系方法:中国, CN106991698A[P]. 2017-07-28.
[10] 沈陈华. 平面上点与多边形包含关系的Q算法[J]. 扬州大学学报(自然科学版), 1999(4): 24-26.
[11] 刘梁. 确定点与多边形以及多边形中顺时针或逆时针拓扑关系的优化算法[J]. 测绘与空间地理信息, 2007, 30(1): 84-86.
[12] 张宏, 温永宁, 刘爱利. 地理信息系统算法基础[M]. 北京：科学出版社, 2006: 129-131.
[13] 董秀山, 刘润涛. 判断点与简单多边形位置关系的新算法[J]. 计算机工程与应用, 2009, 45(2): 185-186.
[14] 翟艳, 徐卫亚, 张强. 点与多边形或多面体的拓扑关系判断[J]. 计算机工程与设计, 2015(4): 972-976.
[15] 章磊,何芬,李鸿赟.一种基于奇异射线法检测点在多边形内的方法[J]. 计算机应用研究, 2020, 37(S2): 133-135.
[16] 李楠, 肖克炎. 一种改进的点在多边形内外判断算法[J]. 计算机工程, 2012, 38(5): 30-34.
[17] 王盛春,王文成,等.加强局部简便计算的点在多边形内的高效判定[J]. 图学学报, 2019, 40(2): 267-273.

相似文献/References:

[1]熊韧,曹海印,王焱清,等.非牛顿润滑静压轴承的节流器流量方程修正[J].湖北工业大学学报,2019,34(5):6.
　XIONG Ren,CAO Haiyin,WANG Yanqing,et al.Modified restrictor flow equations of hydrostatic bearings ubricated by non-Newtonian fluids[J].,2019,34(5):6.
[2]王照远,曹 民,王 毅,等. 场景与数据双驱动的隧道图像拼接方法[J].湖北工业大学学报,2020,(4):11.
　WANG Zhaoyuan,CAO Min,WANG Yi,et al. Tunnel Image Stitching Method based on Scene and Data[J].,2020,(5):11.
[3]潘 健,梁佳成,陈凤娇,等. 单电流闭环多重PR控制的LCL型逆变器[J].湖北工业大学学报,2020,(4):16.
　PAN Jian,LIANG Jiacheng,CHEN Fengjiao,et al. Design of LCL Grid Connected Inverter based on Single Closed Loop Control and Multiple PR Controllers[J].,2020,(5):16.
[4]王晓光,赵 萌,文益雪,等. 定子闭口槽结构对永磁电机齿槽转矩影响分析[J].湖北工业大学学报,2020,(4):25.
　WANG Xiaoguang,ZHAO Meng,WEN Yixue,et al. Study on Cogging Torque and Vibration Noise of Permanent Magnet Motor with Segmental Stator and Closed-Slot[J].,2020,(5):25.
[5]宇 卫,凃玲英,陈 健. 风电场集中接入对集电线电流保护的影响[J].湖北工业大学学报,2020,(4):29.
　YU Wei,TU Lingying,CHEN Jian. Effect of the Collective Line Current Protection when Wind Farms are Centralized Accessed to the Power System[J].,2020,(5):29.
[6]廖政斌,王泽飞,祝 珊. 二惯量系统谐振在线抑制及相位补偿[J].湖北工业大学学报,2020,(4):34.
　LIAO Zhengbin,WANG Zefei,ZHU Shan. Online Resonance Suppression and Phase Compensation for Double Inertia System[J].,2020,(5):34.
[7]王 欣,游 颖,姜天翔,等. 面向3D打印过程的产品工艺设计和优化[J].湖北工业大学学报,2020,(4):39.
　WANG Xin,YOU Ying,JIANG Tianxiang,et al. Product Process Design and Optimization for 3D Printing Processes[J].,2020,(5):39.
[8]冉晶晶,文 红,罗雅梅,等. 全自动样品前处理平台及其控制系统[J].湖北工业大学学报,2020,(4):43.
　RAN Jingjing,WEN Hong,LUO Yamei,et al. Research on Automatic Sample Preprocessing Platform and its Control System[J].,2020,(5):43.
[9]杨 磊,马志艳,石 敏,等. 基于模糊PID的小型冷库过热度控制方法[J].湖北工业大学学报,2020,(4):43.
　YANG Lei,MA Zhiyan,SHI Min,et al. Research on Superheat Control Method of Small Cold Storage based on Fuzzy PID[J].,2020,(5):43.
[10]黄 晶,周细枝,周业望. 动态注塑成型模具的设计与实验研究[J].湖北工业大学学报,2020,(4):52.
　HUANG Jing,ZHOU Xizhi,ZHOU Yewang. Design and Experimental Study of Dynamic Injection Molding[J].,2020,(5):52.

备注/Memo

备注/Memo:
［收稿日期］ 2021-12-04
［基金项目］ 国家自然科学基金（61702168，62072134）；广西可信软件重点实验室研究课题（Kx202014）
［第一作者］ 张 浩（1997-），男，湖北孝感人，湖北工业大学硕士研究生，研究方向为位置隐私
［通信作者］ 沈 华（1978-），女，江苏兴化人，工学博士，湖北工业大学副教授，研究方向为信息安全，隐私保护
更新日期/Last Update: 2022-10-25