In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. Computational geometry is a branch of Computer science devoted to the study of algorithms which can be stated in terms of Geometry. In Geometry a polygon (ˈpɒlɨɡɒn ˈpɒliɡɒn is traditionally a plane figure that is bounded by a closed path or circuit It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, geographical information systems (GIS), motion planning, and CAD. The point location problem is a fundamental topic of Computational geometry. Computer graphics are Graphics created by Computers and more generally the Representation and Manipulation of Pictorial Data Motion planning (aka the "navigation problem" the "piano mover's problem" is a term used in Robotics for the process of detailing a task into atomic
An early description of the problem in computer graphics shows two common approaches (ray casting and angle summation) in use as early as 1974. [1]
An attempt of computer graphics veterans to trace the history of the problem and some tricks for its solution can be found in an issue of the Ray Tracing News. [2]
Contents |
Ray casting algorithm
One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray starting from the point intersects the edges of the polygon. In Geometry, a simple polygon is a polygon whose sides do not intersect If the point in question is not on the boundary of the polygon, the number of intersections is an even number if the point is outside, and it is odd if inside. In Mathematics, the parity of an object states whether it is even or odd In Mathematics, the parity of an object states whether it is even or odd This algorithm is sometimes also known as the crossing number algorithm or the even-odd rule algorithm. The even-odd-rule is an Algorithm implemented in vector-based graphic software like the PostScript language which determines how a graphical shape with more than The algorithm is based on a simple observation that if a point moves along a ray from infinity to the probe point and if it crosses the boundary of a polygon, possibly several times, then it alternately goes from the outside to inside, then from the inside to the outside, etc. As a result, after every two "border crossings" the moving point goes outside. This observation may be mathematically proved basing on the Jordan curve theorem. In Topology, the Jordan curve theorem states that every non-self-intersecting loop in the plane divides the plane into an "inside" and an "outside"
If implemented on a computer with finite precision arithmetics, the results may be incorrect if the point lies very close to that boundary, because of rounding errors. This is not normally a concern, as speed is much more important than complete accuracy in most applications of computer graphics. However, for a formally correct computer program, one would have to introduce a numerical tolerance ε and test in line whether P lies within ε of L, in which case the algorithm should stop and report "P lies very close to the boundary. Computer programs (also software programs, or just programs) are instructions for a Computer. Numerical analysis is the study of Algorithms for the problems of continuous mathematics (as distinguished from Discrete mathematics) Engineering tolerance is the permissible limit of variation in a physical Dimension, a measured value or Physical property of a "
Most implementations of the ray casting algorithm consecutively check intersections of a, say, horizontal ray with all sides of the polygon in turn. In this case the following problem must be addressed. If the ray passes exactly through a vertex of a polygon, then it will intersect 2 segments at their endpoints. In Geometry, a vertex (plural "vertices" is a special kind of point. While it is OK for the case of, say, the topmost vertex in the example, the case of, say, the rightmost vertex (in the example) requires that we count one intersection for the algorithm to work correctly. A similar problem arises with horizontal segments that happen to fall on the ray. The issue is solved as follows. If the intersection point is a vertex of a tested polygon side, then the intersection counts only if the second vertex of the side lies below the ray.
Once again, the case of the ray passing through a vertex may pose numerical problems in finite precision arithmetics: for two sides adjacent to the same vertex the straightforward computation of the intersection with a ray may not give the vertex in both cases. If the polygon is specified by its vertices, then this problem is eliminated by checking the y-coordinates of the ray and the ends of the tested polygon side before actual computation the the intersection. In other cases, when polygon sides are computed from other types of data, other tricks must be applied for the numerical robustness of the algorithm.
Winding number algorithm
Another algorithm is to compute the given point's winding number with respect to the polygon. The term winding number may also refer to the Rotation number of an Iterated map. If the winding number is non-zero, the point lies inside the polygon. One way to compute the winding number is to sum up the angles subtended by each side of the polygon. However, this involves costly inverse trigonometric functions, which generally makes this algorithm slower than the ray casting algorithm. Luckily, these inverse trigonometric functions do not need to be computed. Since the result, the sum of all angles, can add up to 0 or 2*PI (or multiples of 2*PI) only, it is sufficient to track through which quadrants the polygon winds, as it turns around the test point, which makes the winding number algorithm comparable in speed to counting the boundary crossings.
For simple polygons, both algorithms will always give the same results for all points. However, for complex polygons, the algorithms may give different results for points in the regions where the polygon intersects itself, where the polygon does not have a clearly defined inside and outside. The term complex polygon can mean two different things In Computer graphics, as a polygon which is neither convex nor concave. In this case, the former algorithm is called the even-odd rule. The even-odd-rule is an Algorithm implemented in vector-based graphic software like the PostScript language which determines how a graphical shape with more than
Point in polygon queries
The point in polygon problem may be considered in the general repeated geometric query setting: given a single polygon and a sequence of query points, quickly find the answers for each query point. Clearly, any of the general approaches for planar point location may be used. The point location problem is a fundamental topic of Computational geometry. Simpler solutions are available for some special polygons.
Special cases
Simpler algorithms are possible for monotone polygons, star-shaped polygons and convex polygons. In Geometry, a Polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L A star-shaped polygon (not to be confused with Star polygon) is a Polygonal region in the plane which is a Star domain, i
References
- ^ Ivan Sutherland et al,"A Characterization of Ten Hidden-Surface Algorithms" 1974, ACM Computing Surveys vol. Ivan Edward Sutherland (born 1938 in Hastings, Nebraska) is an American Computer scientist and Internet pioneer 6 no. 1.
- ^ "Point in Polygon, One More Time...", Ray Tracing News, vol. 3 no. 4, October 1, 1990.
External links
- Point in polygon strategies, by Eric Haines
- C code to determine if a point is in a polygon
- C code for an algorithm using integers and no divides
- Crossing number and winding number algorithms with illustrations and example code
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic