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:

1. given all the explicit nodes and edges, find all of the implicit nodes and edges
2. 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)
3. 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.

Peter Coles

is a software engineer living in NYC who is building Superset 💪 and also created GoFullPage 📸
more »