Mesh Simplification Part I - It's All About Squatters

I've been working on map simplification for a few days now - it seems like I periodically have to revisit this problem. After working on simplification yet again, I realized that the problem statement is even simpler than I realized.

Given an arrangement (that is, a set of line segments and possibly free points such that line segments don't cross or end in each other's interiors) we can iteratively simplify the map by replacing adjacent pairs of line segments with a "short-cut" (e.g. replace line segments pq and qr with pr) given the following conditions:

1. The degree of vertex q is 2 (e.g. only pq and qr emerge from q).
2. Line segment pr is not already in the arrangement.
3. If p, q, and r are not collinear are no points in the interior of triangle pqr (nor directly between p and r). By definition there can't be any points on pq and qr.

Test 3 - the test for "squatters" (that is, points in the interior or on the border of triangle PQR) is the key. If any points exist inside PQR then:

• There is some kind of island geometry (or free vertex) and it will be on the wrong side of pqr after simplification, or
• The geometry "connects" to the world outside pr and pr will intersect at least one segment.

Both cases require us to not simplify.

Given this, we can build an iterative algorithm for simplifying a mesh:

• Put every vertex that passes these tests into a queue, based on the error introduced by removing it.
• Remove the first vertex.
• Requeue neighboring vertices based on changed error metrics.

Note that a vertex that may have been "stuck" before may now be removable, if one of the "squatters" from test 3 was previously removed.

The Zone Is Not What We Want

Previously I had coded similar logic via a zone visiting calculation - that is, finding every face, line and point that the edge pr would intersect. This had a few problems:

1. Arrangement zone calculations are really expensive. Given a simple polygon with X sides, we may have to do as many as X zone calculations (if any vertex is eligible for removal) and the zone calculation iterates the polygon boundary. Thus we have an O(N^2) calculation, which is really painful for large polygons made of a large number of small sides. (Sadly, that is precisely what my data tends to be.)
2. The zone calculation is wrong; even if we don't crash into anything while computing the zone, if the zone has holes that would be on inside of triangle PQR then we still should not be simplifying. So we would have to iterate over holes as well as calculate the zone.

Up next: fast arrangement simplification.