2017 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 9

Problem

Consider a triangulation (mesh) of a polygonal domain like the one in the figure below. (a) Given the vertices of a triangle, devise a strategy for determining if a given point is inside that triangle. (b) Will your strategy work for polygons with more than three sides? (c) After implementing your strategy in an optimally efficient computer code you find that the search for a problem with triangles, on average, takes seconds. You refine the triangulation by subdividing each of the triangles into smaller triangles by placing a new vertex at the center of gravity of each triangle. On average, how long will it take to find a point in the new mesh?

Solution

Various solutions are possible. For example, a simple algorithm is to walk around the polygon along one side at the time. If the point is always to the left (or always to the right) of the line in the plane that coincides with the current side, then the point is inside (for triangles this is done by dot-products). Another option is to use the Jordan Curve Theorem: “Any continuous simple closed curve in the plane, separates the plane into two disjoint regions, the inside and the outside”. This theorem implies that if one casts a ray from the point at hand in any direction and count the number of intersections of the ray and the boundary of the polygon. If the number of crossings is odd then the point is inside, see Figure ??. The complexity will typically be linear so the new search will, on average, take half a minute as the number of triangles have grown by a factor of three. This problem is of significant practical importance in computer graphics. Additional information can be found at:

• Point in Polygon

If one only consider triangles there are three techniques that are particularly popular: barycentric coordinate system, parametric equations system, check sides with dot product. These are described (along with explicit formulas and computer codes) in this blog post:

• Point in Triangle Test