高级检索

映射相关边概念的多边形内外点判别算法

Point Inclusion Test for Simple Polygons By the Nearest Relevant Edge

  • 摘要: 提出映射相关边、密切边的概念,将点在多边形内外的判别转化为点与密切边关系的判别.通过X方向的一次映射快速求取判别点的相关边,对相关边的二次映射可得到判别点的密切边.证明了根据密切边的矢量方向就可以判别点在多边形内外.在运算效率上对射线法进行改进,当多边形的边数较多时,更能体现文中算法优越性.

     

    Abstract: The relevant edge nearest to the given point is determined by first projecting the point and polygon edges onto X-axis and finding the edges within whose ranges the point projection is located. Then the point and relevant edges found in the first step are projected onto Y-axis to pick out the nearest edge PiPi+1 from the given point Q.If the orientation of triangle PiPi+1 Q is the same as polygon, Q is inside the polygon.Otherwise,it is outside the polygon.Compared to Jordan curve theorem algorithm,this approach is more efficient and reliable,especially in the case of large number of polygon edges.

     

/

返回文章
返回