判定点是否在多边形内部的算法
An Algorithm for Determining Whether a Point Lies Within the Polygon
-
摘要: 提出判定点是否在多边形内部的一种算法,其方法是判定射线与多边形边的交点数目以及必要时移动该点的位置,再判定交点的数目,该算法的时间复杂性为O(n)次四则运算和O(n)次比较,其中n为多边形的顶点数。Abstract: Presents an algorithm for deciding whether a point lies within a polygon. It is bed on the number of intersections of rays radiating from the point and number of edges of the polygon, as well as the necessary number of relocations of the point.The number of intersections is then found again. The algorithm requires O(n) arithmetic operations and O(n) comparisons, n being the number of vertices of the polygon.
下载: