判断点在多边形区域内部、外部或边界上的包容性测试方法

摘要

本发明公开了一种判断点在多边形区域内部、外部或边界上的包容性测试方法，属于一种运用方位检测原理推断包容特性的方法，即运用点与有向线段的左右方位关系直接推断点与多边形的内外关系。本发明首先寻找测试点到多边形边界的最近点和最近边，然后根据测试点到最近点的距离和用户设定的边界宽度判断测试点是否在多边形边界上；如果不在边界上，直接利用测试点与有向多边形最近边的左右关系推断出测试点与多边形的内外关系。本发明采用方位法统一检测点对有向凸多边形和凹多边形的包容特性，并且能检测点在多边形边界上这种奇异情形，具有鲁棒性好的特点。

主权项

一种采用方位法计算点在凸和凹多边形内部、外部或边界上的包容性测试方法，其特征在于，统一用点与有向凸和凹多边形最近边的距离与左右方位关系推断点与多边形区域的内外关系；具体包括以下步骤：步骤一，计算测试点到多边形各条边的距离，记录最短距离和该距离所对应的最近边；步骤二，比较最短距离和用户指定的多边形边界宽度的大小关系，当最短距离小于边界宽度时，判断测试点在多边形的边界上，结束测试；步骤三，计算测试点在最近边上的最近点，当最近点不为最近边的端点时，即最近点与最近边两个端点的距离都大于边界宽度，计算测试点与最近边的左右关系，利用推理规则确定点与多边形的内外关系，结束测试；步骤四，选择与最近点距离最小的端点相连接的两条边，分别计算测试点与两条边的左右关系，利用推理规则确定点与多边形的内外关系，结束测试。