Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

Compulsive Obsolescense

Sign in to follow this  


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 rejected
regex-dna | 204 | 1 program pending
nsieve-bits | 97* | 1 program accepted*
recursive | 98 | 1 program accepted
mandelbrot | 97 | 1 program accepted
nbody | 102 | 1 program accepted
fasta | 103 | Not attempted
cheap-concurrency | 1852 | 1 program accepted, 1 program rejected
spectral-norm | 102 | 1 program accepted
k-nucleotide | 222 | 1 program rejected
chameneoes | 770 | Not attempted
pi-digits | 102 | Not attempted
partial-sums | 178 | Not attempted
reverse-complement | 169 | Not attempted
binary-trees | 405 | Not attempted
fannkuch | 170 | Not attempted
sum-file | 224 | Not attempted
startup | 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.

Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!