i've looked into this, it's pretty hilarious -- the best triangulation algorithm is O(n), but in _every_ citing is described as "unimplementable" or "too complex to realistically implement".. reading this in a research paper is pretty hilarious/depressing.
Awesome :D
Here's a
graphics gem on fast polygon triangulation, with source code. They report it's an n*log(n) algorithm that gets close to linear time in practice, and could triangulate 100 vertices in 6.7 ms ... in '94 or '95 on an "HP Series 735" ... so perhaps it will be good enough for your purposes? It's graphics gem code, so I believe the license is this (from
http://tog.acm.org/GraphicsGems/):
"EULA: The Graphics Gems code is copyright-protected. In other words, you cannot claim the text of the code as your own and resell it. Using the code is permitted in any program, product, or library, non-commercial or commercial. Giving credit is not required, though is a nice gesture. The code comes as-is, and if there are any flaws or problems with any Gems code, nobody involved with Gems - authors, editors, publishers, or webmasters - are to be held responsible. Basically, don't be a jerk, and remember that anything free comes with no guarantee."
The "fast" grid-based algorithm I was thinking of (which creates steiner points) is basically to draw the edges as lines on a grid, but instead of drawing pixels, add the lines ID (eg "this is line number 7") to a list at that grid position. Then run across the grid in scan lines; if you've crossed an odd number of line IDs, you're inside the object and you should make a steiner point. If you're in the process of crossing over, you should additionally either push the grid vertex to the edge line or connect to an additional vertex created on that line.
... but that's kind of half-formed in my head, and I think the graphics gem code is better if it works.
Anyway, hope that helps!
Developer
