We recently created a JavaScript tool for classifying placemarks by region. This post is about how it works.
The basic idea is actually quite simple. To determine whether or not a point is inside or outside a polygon, simply draw a line from the point in question to a point you know is outside the polygon and then count how many times it crosses the polygon. If the number is odd, the point is inside the polygon, if the number is even the point is outside. In our case, we assumed that the polygon being tested does not go around the North Pole, so we draw a line from the point to the North Pole and then count how many edges of the polygons it intersects.
Below is an example of a place in Japan being tested:
The green line is drawn from the point being tested to the North Pole. The red lines are edges that we identified as being crossed by the green line. The white diamonds are the intersections. There are fifteen intersections, therefore the point is inside the polygon.
To see it in Google Earth download this KML file
.
To actually identify which vertices the line crosses, it is necessary to find the intersection between the great circle on which the edge lies and the great circle on which the line we are testing lies and then check whether the intersection lies between the two ends of the edge and also whether or not it lies between the two ends of the line being tested. All this is complicated by the fact that any two great circles actually have two intersections on opposite sides of the globe (the antipode). The original algorithm we had for finding intersections that we used for the circle drawing tool sometimes found the intersection we wanted and sometimes the antipode. We found that when it found the antipode it was not as accurate as when it finds the intersection we are interested in, so we had to improve the algorithm to try and ensure it finds only the intersection we want.
To improve performance we first check whether or not a point is in the same region of the globe as the polygon being tested and don’t actually bother with the above algorithm if they are in different parts of the globe.
The reason we were working on the code in the first place is that when we were working on this post about recent progress in 3D imagery we noticed a significant discrepancy between the total areas for the timeline vs total areas in the ‘sorted by country’ section. To easily identify mistakes we wanted to match up polygons from the two sections. To do this we needed to know whether any two polygons overlap. The way we achieve that is to test every point in every polygon and see if it is internal to another polygon. If it is, the two polygons overlap.
.
