基于边方向角长度表示的多边形方向、凹凸性及点包含算法
Orientation, Convexity-Concavity and Inclusion Query Algorithms for Polygons Using the Edge-Azimuth-Length Concept
-
摘要: 提出矢量边方向角的长度表示概念,用于解决多边形方向识别、顶点凹凸性识别和点包含判断三个问题.给出了基于矢量边方向角长度概念描述多边形边方向角的单调连续函数,当方向角从0°增加到360°时,函数值从0增加到8,该函数可以准确地表达多边形中边矢量的方向角,也可以准确地表达待检测点与多边形顶点连线所形成矢量的方向角.建立了基于矢量边方向角长度概念的多边形相邻边左右侧走向关系判定规则.该规则可用于判定相邻边方向关系,实现多边形方向识别和顶点凹凸性识别;计算待检测点与多边形顶点连线之间所夹有向边方向角长度和,实现点包含判断.给出了三个问题的实现算法,该算法与目前最优算法复杂度相同,但计算量较最优算法少1次乘除类运算,同时保证了高可靠性、稳定性和执行效率.实现了三个问题解决方法在几何概念上的统一,而在其他同类算法中几何概念是相互独立的.Abstract: A metric square with each side of 2 units long is constructed inside the given polygon, and the azimuth of a radial vector, taking y-axis as north direction, is represented in terms of edge-azimuth-length (EAL), i. e. the overall length of the square edges included between their crossing points with y-axis and the given radial vector, resulting in a monotonically continuous function value ranging from 0 to 8, as the azimuth increasing from 0° to 360°. Orientation of a polygon and convexity-concavity of a vertex can be detected by verifying whether the EAL values of consecutive edges are increasing monotonically or not, while point inclusion query can be clarified by taking the given point as origin and summing-up the incremental EAL value of each edge: ±8 means included and 0 means not.
下载: