I decided to see if I could get my original Poly2Tri constrained Delaney triangulation (CDT) code optimized enough to beat the fastest descendant I've come across: "fast-poly2tri." There are a bunch that have popped up over the years in various langs (I'm the original author, circa 2009). There could be a faster variety, but this one caught my attention.
The name speaks for itself: fast, hand-optimized C, with arena pointers and descent sorting. The person who did this ten years ago really knew what they were doing.
Of course I had to see if I could beat it with Nim, and a little help (a lot) from AI:
https://github.com/greenm01/p2t
Not too bad!
I've tried all sorts of other methods to thread/parallelize other algos to go faster, but this single thread (CPU) CDT sweep line algo is one to beat.
More fun with Nim.
Would that help improve performance?
I'm certainly open to help making it better, please.
"I cringe when I have to read "fast, hand-optimized C, with arena pointers and descent sorting", the fast code is the fuck-C code"
But maybe they artisanally hand baked the code with the loving care of a free range organic chicken farmer?
Cleaned up the frontend api.
I also added Shewchuk's Triangle C code to the bench..... p2t smokes it! Not even close.
I can't include his source in the repo for copyright reasons, but it's available online.
I had to take it a step further and added a "contenders" table with results.
P2T absolutely destroys them, including the commercial Fast2D.
Nim is king.