25 October 2012

# Triangle Finder

A few weeks ago there was an NPR Sunday Puzzle for counting all of the triangles in a particular shape. I thought it’d be fun to code up a solution using JavaScript and HTML5 canvas, so I did. Unfortunately, I caught the flu and finished it a couple days late.

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.