How it works: Classifying Placemarks by Region

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.

About Timothy Whitehead

Timothy has been using Google Earth since 2004 when it was still called Keyhole before it was renamed Google Earth in 2005 and has been a huge fan ever since. He is a programmer working for Red Wing Aerobatx and lives in Cape Town, South Africa.






PLEASE NOTE: Google Earth Blog is no longer writing regular posts. As a result, we are not accepting new comments or questions about Google Earth. If you have a question, use the official Google Earth and Maps Forums or the Google Earth Community Forums.

Comments

  1. I think I understand this but I was confused because you’re using the word “vertex” wrong. A vertex is a point — a “corner” of a polygon. I think where you say vertex you mean edge: one of the line segments making up a polygon’s boundary (between two vertices). See https://www.mathsisfun.com/geometry/vertices-faces-edges.html.

    What happens if the line to the pole exactly intersects a vertex? Does your algorithm count it as a single crossing?

    • Timothy Whitehead says:

      Thanks for the correction, I have updated the post. My algorithm will probably fail if the line exactly intersects a vertex. In addition, due to rounding errors, there is a small chance that it can slip between two consecutive edges and not be detected as crossing either, or be detected as crossing both. JavaScript has about 15 digits of precision but Google Earth only has about 8 digits. Nevertheless, unless you deliberately position a placemark and vertex in such a way that they will line up, it is very unlikely to happen. If dealing with very regular data then it could definitely occur and the solution would be to not draw the line to the North Pole but to a point offset from the North Pole, and possibly double check by drawing multiple lines to different locations.



PLEASE NOTE: Google Earth Blog is no longer writing regular posts. As a result, we are not accepting new comments or questions about Google Earth. If you have a question, use the official Google Earth and Maps Forums or the Google Earth Community Forums.