I was looking into polygon triangulation algorithms at work this week. It didn't take long to find reference to the optimal version, developed by a guy named Bernard Chazelle, which can triangulate a simple polygon in linear time. The reference also came with a warning that it was not a simple algorithm. They weren't kidding. I found a copy of the original paper (pdf) on Chazelle's home page. Understanding the algorithm itself isn't impossible. Figuring out how to actually implement the algorithm on the other hand had me well and truly stumped. If anyone knows of any publicly available implementation of this algorithm (I haven't been able to find any) I'd be interested to learn of them.

So linear time was unworkable in the time I have available to devote to the task but fortunately there are alternatives. My next choice was an n log n algorithm that claimed to usually run in roughly linear time. Even better this one had source code. Unfortunately the link to the source code was dead. I eventually found a mirror, only to find what I'd been dreading. Sample implementation source code which is 50% incomprehensible. int i1, i2, i3, i4, i5, i6, i7. Yes, I know exactly what those are going to be used for! Also, I was under the impression that K&R style function definitions of the form:

void function(a, b)	int a;	int b;{}

had been deprecated in the very first C standard, back in 1989. Yet here was code written in 1994, five years later, still using it. Sometimes. Even better though has to be this gem of a comment:

  int usave, uside;		/* I forgot what this means */

And after a weekend off, tomorrow morning I get to go back to work and try and finish porting that mess to C++ so that I can extend the algorithm for my own purposes. Joy.

I also thought I'd update you on my progress with the language shootout:

benchmark-name     | C++ speed as % of fastest other | status -------------------+---------------------------------+-------nsieve             | 113                             | 1 program rejectedregex-dna          | 204                             | 1 program pendingnsieve-bits        | 97*                             | 1 program accepted*recursive          | 98                              | 1 program acceptedmandelbrot         | 97                              | 1 program acceptednbody              | 102                             | 1 program acceptedfasta              | 103                             | Not attemptedcheap-concurrency  | 1852                            | 1 program accepted, 1 program rejectedspectral-norm      | 102                             | 1 program acceptedk-nucleotide       | 222                             | 1 program rejectedchameneoes         | 770                             | Not attemptedpi-digits          | 102                             | Not attemptedpartial-sums       | 178                             | Not attemptedreverse-complement | 169                             | Not attemptedbinary-trees       | 405                             | Not attemptedfannkuch           | 170                             | Not attemptedsum-file           | 224                             | Not attemptedstartup            | 294                             | Not attempted

*one of the optimisations used may now be considered illegal, which will affect several programs in the benchmark, including mine

Remember, the target is to get all of them down to 101 or below. Long way to go yet, but the benchmarks I've submitted programs for are doing a lot better than the ones I haven't.

?nigma