有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。

Directed-loop Method and Grid Method:New Algorithms for Inclusion Test of Planar Polygons

This paper proposes two inclusion test algorithms of planar polygons:directed-loop method and grid method by treating the polygon as a directed-loop,using its orientation and making region partition.Directed-loop method utilizes the orientation of the polygon so that it doesn't have to process all sides of the polygon in some cases.Its time com plexity is O(n),with an average efficiency less thanΘ(n)algorithms such as labeling method and ray method,but it works on convex polygons only.Grid method is an improved algorithm of the directed-loop method:it utilizes the orientation of the polygon and region partition at the same time.A n-vertex polygon is bounded by a rectangular extent (also called bounding box),then the extent is partitioned into(n-1)×(n-1)grids as the grid method.If the point to be tested is in a certain grid,then people can decide whether it is interior to the polygon or not based on all sides passing through the grid solely.Grid method works on both convex and concave polygons even polygons with holes,its time complexity is O(lg n)in the worst case,space complexity isΘ(n 2 ).