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

Point Inclusion Test for Simple Polygons By the Nearest Relevant Edge

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

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 P iP i+1 from the given point Q If the orientation of triangle P iP i+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