Point-in-polygon: Jordan Curve Theorem
Calculating whenever a point is inside a polygon can sometimes be a hard and costly calculation. This article describes a quite cheap solution to calculate whenever a point is inside ANY closed polygon. In an open polygon it's hard to determine what's in and out so naturally it won't work.
The Jordan Curve Theorem states that a point is inside a polygon if the number of crossings from an arbitrary direction is odd. An image explains more than a thousand words so lets take a look at the picture. As you can see point 1 and 3 is inside the polygon but point 2 isn't. Follow the rays from each point and count each time you cross a line-segment. In this article I only deal with 2D polygons but it can easily used in a 3D-environment.
Contents
Find crossings
Casting a ray
One of the first things to do is to cast a ray from the point in an arbitrary direction. I use a ray along the Y axis (pointing upwards as in the picture) for simplicity. Along X-axis is good too, but use one of those or it gets a lot harder. Remember that I use the ray mentioned above throughout this article.
Finding the equation of a line-segment
As a first step, if the ray is along y-axis, check if the point x-coordinate is between the two points connecting the line. If not it don't cross it either. You can also check if the y-coordinate is above both points. The next step is to find the equation of the line. Hopefully you remember this from grade school. The equation of a straight line is $ y=kx+m\, $ (Swedish notation). The slope is $ k=\frac{\Delta\ y}{\Delta\ x} $ and offset is $ m=y-kx\, $. Do the math we have the equation. Now, insert the x-coordinate of the point into the equation. If the result is larger than the y-coordinate the ray does not cross the line-segment.
Repeat this for each line-segment.
C/C++ implementation
| Code: A test case |
