Jordan point-in-polygon test
The Jordan point-in-polygon test checks whether a particular point in the plane is inside, outside, or on the boundary of a polygon.
According to Jordan's theorem of curves , to put it simply, the edges of a polygon divide the data space into an inside and an outside. For many applications it is necessary to find out whether a point is inside or outside a polygon.
Beam method
With the beam method, a beam is sent in any direction from the point to be tested. The number of times the ray intersects the edges of the polygon is counted. Four cases can be distinguished:
- no intersection
- an even number of intersections
- an odd number of intersections
- infinite intersections
If the number is zero, the point lies outside the polygon. If the number is odd, the point is inside the polygon, if it is even, it is outside. In the case of an infinite number of intersections, the ray ran directly on an edge. The test must then be repeated at a different angle. However, through a more refined consideration of the relative position of the test point and the edge ends in the collinear case, such a repetition with a different angle can be dispensed with. So the following pseudocode counts along the horizontally to the right directed ray with special attention to corners lying on the ray:
Funktion: PunktInPolygon
Parameter: Ecken P[1], ...,P[n] eines ebenen Polygons P, Testpunkt Q
Rückgabe: +1, wenn Q innerhalb P liegt;
−1, wenn Q außerhalb P liegt;
0, wenn Q auf P liegt
Setze P[0] = P[n] und t = −1
Für i = 0, ..., n−1
Setze t = t * KreuzProdTest(Q,P[i],P[i+1])
Wenn t = 0
Abbruch der Schleife
Ergebnis: t
Funktion: KreuzProdTest
Parameter: Punkte A = (x_A,y_A), B = (x_B,y_B), C = (x_C,y_C)
Rückgabe: −1, nicht im Polygon;
0, Punkt auf Kante liegt;
sonst +1
Wenn y_B > y_C
Vertausche B und C
Wenn y_A ≤ y_B oder y_A > y_C
Ergebnis: +1
Setze Delta = (x_B−x_A) * (y_C−y_A) − (y_B−y_A) * (x_C−x_A)
Wenn Delta > 0
Ergebnis: 1
sonst wenn Delta < 0
Ergebnis: -1
sonst
Ergebnis: 0
Note: According to the description of the return value of the KreuzProdTest function , the value is returned if Delta> 0 . If the sign of Delta is returned instead , the PointInPolygon function also returns the correct result. In this case, the intersections of the edges with a ray going from the left are counted.
application areas
This method is mainly used in geographic information systems.
literature
- Günter Hake, Dietmar Grünreich, Liqiu Meng : Kartographie deGruyter, 2001, ISBN 3-11-016404-3 , p. 306ff.
- Norbert Bartelme: Geoinformatics: models, structures, functions. 2005, ISBN 3-540-20254-4 , p. 103.