Country Interior: Two Solutions to the Nonconvex Polygon Interior Problem
Country Interior: Two Solutions to the Nonconvex Polygon Interior Problem
The problem to be solved here is a polygon-interior problem, which is to determine whether or not a point is inside a polygon. We assume the polygon is not self intersecting, though it may be nonconvex.
There are many algorithms that deal with the same problem under the assumption that the polygon is convex. For a general polygon that is not self intersecting, we describe an algorithm (see the Details section).
One obvious way is to triangulate the polygon's interior and boundary, and see whether the point lies inside one of the triangles. However, country borders are often extremely complicated, with many edges. The triangulation process can thus be computationally expensive and may not be appropriate for a mobile-phone application.
Here we test our method using the country border data. Select a country to draw it and its neighbors (if any). Drag the locator; if you are inside one of the countries, that will be indicated.
The polygon-interior problem can alternatively be solved using the so-called "odd-even rule" (see the Details section). Users can switch between the odd-even rule and our method using the toggle buttons. The result will be the same.