判断点与多边形拓扑关系的改进算法

为了解决射线法不能有效地判断点在复杂多边形内或外的问题,根据射线与多边形边界相交的特性,分析射线所经过的多边形的不同类型顶点,提出了对顶点数加1、加2和加3的运算方法。通过判断交点个数的奇偶性,改进了射线法,并给出了计算模型和算法的详细步骤,简单有效的将现有的射线法扩展到更复杂的多边形中,能准确的判断点与多边形的位置关系。4种不同算法对比分析结果表明,该算法能解决其它3种算法存在的问题,并且在简单多边形和复杂多边形中都是有效的。

改进有向回路法判断点与多边形关系

在地理信息系统(GIS)中,判断点与多边形的关系是一个非常基础的问题。本文对计算效率较高的有向回路法做出改进,将改进后的算法思想作为本文的主体。

隐私保护的点与任意多边形位置关系判定

点与多边形位置关系判定的保密计算是一种非常有用的安全多方计算几何应用,目前已有的方案仅支持凸多边形的关系判定.本文提出一种有效隐私保护的点与任意多边形位置关系判定方案.该方案使用模拟射线的判定法将点与任意多边形位置关系的判定问题转化为任意一条过点的射线与多边形相交点数的奇偶性判定问题.设计中首先提出一种精简高效的叉积协议,该协议利用符号位编码将明文空间划分为两个不相交的子空间,分别用于点的正负坐标到明文空间的映射空间从而实现了支持负数的叉积运算,然后基于该叉积协议并利用同态加密方案设计一种隐私保护下的点与多边形位置关系的判定协议,以计算射线与多边形的相交点数,最后利用模拟范例证明该协议的安全性.现有点与多边形位置关系判定方案通常只适用于凸多边形的情况,本文方案不仅能支持对凸多边形的判定且能支持对凹多边形的判定.模拟实验显示本文提出的叉积协议的运行效率相对于已有的叉积协议提高了67.5%.由于避免使用了复杂的密码原语,本文提出的判断方案获得了线性的计算复杂度和通信开销.

一种改进的点与多边形关系的叉乘判别法

本文针对叉乘判别法只适用于凸多边形的缺陷提出了改进,将其推广至凹多边形和自相交多边形,改进方法利用叉乘值的正负变化,选择对点的积分路径,从而判断是否有闭合的路径包围被测点。并通过检测多边形是否环绕被测点,判断点与多边形的关系,属于非零环绕数法。经过实验,改进方法被证明有较快的速度和较强的适应性。

油田数字化管理过程中快速判定井位归属问题的算法

现代化油田管理中,油田的各项参数已经全部数字化;其中井位成为数据库中各项参数的链接枢纽。对于每年新增的大量数据,数据库中井位与范围区块(如开发区块、含油面积范围、沉积相范围、断块等)的归属关系快速判定,以及快速查询出某一范围区块中的井位名称,不仅可以大大提高地质工作人员的工作效率,而且还可以提高油藏描述的精度。解决该问题的相应的数学模型为判定点与多边形的位置关系。在分析所有算法优缺点的基础上,利用了改进的Q型算法,通过待判点的预判定、特殊性待判点的判定;以及一般性点的判定来快速判定井位的归属问题。根据此算法进行编程,在吉林油田的数字化管理的过程中得到了广泛的应用。