libgdx/libgdx — pull request #490 by ttencate (2013-06-30 09:47:08+00:00)
Title: Bugfixes, simplifications and tests for EarClippingTriangulator

I believe this fixes http://code.google.com/p/libgdx/issues/detail?id=207#c11, http://code.google.com/p/libgdx/issues/detail?id=1407 and http://code.google.com/p/libgdx/issues/detail?id=815. Algorithmic changes make infinite loops impossible, and some sort of output will be produced even if the input polygon is degenerate in some way. Also, the implementation is 20% shorter.

I've added a GUI test for the known problematic cases, as well as some other nasty stuff I could come up with, both valid and invalid. Use left and right arrow keys to cycle the polygon vertices.

I have not run any benchmarks, but the order of magnitude should still be the same, if not better: it now only does allocations up front, and does less redundant vertex classification. I did remove the special-casing for convex polygons, but since it was still doing an n^2 thing for those, it shouldn't be a regression.

I've just pushed this code to a production app in the Play Store, and will see how it fares. I think it's already better tested than the old version, but as it's a fairly invasive change, there could be new bugs lurking. I believe merging is safe, but if you'd rather wait until it's been tested in the real world, I can ping this PR if it's proven stable for two weeks, just let me know!