25 October 2012
The basic algorithm is:
- given all the explicit nodes and edges, find all of the implicit nodes and edges
- for every node, explore a path of length 3 that doesn't repeat the same slope between consecutive nodes and doesn’t repeat (except for connecting the last and first)
- dedupe any redundant paths, sort all the results by size, and print them out
In addition to getting the modeling and constraints right, I had to call on some basic algebra for computing lines and intersections, and I also had to deal with the inaccuracies of floating point arithmetic by rounding to the nearest thousandth only when I check for equality. The code is on my github.
I created some extra shapes for testing, click any of the shapes below to find more triangles.