I was avoiding posting here because there's plenty of information on triangulation out there, but I'm beginning to find it more of a curse than a blessing due to how specified my case is and how many triangulation algorithms there are.

I have 2D potentially-concave polygons that are defined as an ordered list of vertices in clockwise order. These vertices define the hull or outline of the shape - no vertices are inside the polygon. I was looking at ear-clipping, but the order of complexity seems like it could be improved with a better algorithm.

Anyone have any good resources or personal knowledge specific to my case?

If you can get an ear-clipping algorithm to work, try it. If that's not fast enough for your purpose, try something fancier. For instance, CGAL has functions for partitioning a polygon into convex polygons, and then triangulating those is trivial: http://doc.cgal.org/latest/Partition_2/index.html

I've implemented ear clipping. It can be done quite efficiently. My favorite resource was from David Eberly on his website. He makes annoying use of C++ templates, but the algorithm and PDF + drawings he made are really nice. https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Thanks for the input. I was thinking partitioning into convex would be faster, so maybe I'll give that a shot.

My assumptions come from this paper: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Particularly, in the first section:

Quote

The simplest algorithm, called ear clipping, is the algorithm described in this document. The order is O(n 2 ). Algorithms with better asymptotic order exist, but are more difficult to implement. Horizontal decomposition into trapezoids followed by identification of monotone polygons that are themselves triangulated is an O(n log n) algorithm [1, 3]. An improvement using an incremental randomized algorithm produces an O(n log∗ n) where log∗ n is the iterated logarithm function [5]. This function is effectively a constant for very large n that you would see in practice, so for all practical purposes the randomized method is linear time. An O(n) algorithm exists in theory [2], but is quite complicated. It appears that no implementation is publicly available

To provide a bit of context, I need this for a simple Unity plugin. Originally I was making it to aid with development of one of my game projects, but after seeing there weren't any good, simple and cheap 2D polygon tools in the asset store, I figured I'd try to optimize it and put it up for sale for a low price. For that reason, I'd like usage of the tool to be as seamless as possible. Ideally the polygons would re-triangulate their meshes every update if a vertex was moved, but if it causes any lag at all I'd rather avoid it. Additionally, I'm personally going for a 2D Sonic-esque physics simulation using polygons/edges rather than heightmaps (old school optimization for the 16-bit games), so some ramps and curves would involve a lot of vertices. Considering that, O(n^2) complexity seems a bit risky for constant triangulation updates. I was curious if anyone had any leads on the O(n) theoretical algorithm, but it sounds like a Unicorn so I'll leave it at that.

I'll go ahead with convex-partitioning, but if anyone has anything new to add please feel free to do so.