AnalyticalGraphicsInc/cesium — pull request #947 by DavidHudlow (2013-07-16 18:55:26+00:00)
Title: Improve Polygon Triangulation Algorithm

This replaces the O(n^2) ear clipping algorithm with an O(nlogn) random cut algorithm. We have need of improved performance for large polygons with many vertices (such as those that would represent a country or state), so we optimized this algorithm.

The recursive algorithm concept is quite straightforward:

Take a polygon, pick two random vertices, if we can make a clean cut between them, divide the polygon using that cut and repeat for each polygon unless it has only three vertices. If the cut isn't clean, simply pick new random vertices until we find one that is.

This algorithm could be improved (though probably not much for most polygons) with a superior pseudo-random generator or deterministic selection pattern that never checks the same set of vertices twice. As it stands, it radically improves performance in the test cases I ran, triangulating 10k vertices in ~200-300ms compared to about 10 seconds before.