README

Usage

Click the add buttons to add any number of disks to canvas. Click the clear button to remove all drawings from the canvas. Click the canvas to place a starting puck at any given location, when you click another location that puck ceases to be the starting puck and the newest puck created becomes the starting puck.

Implmentation

This program is implmented entirely in javascript with 3 files:

• Canvas.js: Basic drawing functions
• Delaunay.js: Creates the delaunay triangulation out of the feild of pucks
• Puck.js: Builds an iterable map and runs a modified depth first search to find a path out of the feild of pucks

There's javascript that serves a wrapper in the main page, but it mostly serves as a wrapper for these functions (mostly the Demo.render() method). In general during each render the program:

1. Delaunay.js creates a raw triangulation with global.triangulate
2. Puck.js creates a mappable data structure with global.build, incuding discovering the convex hull
3. Puck.js paths through the data structure, producing a path with global.path
4. This pages calls Canvas.js to render the edges, fills in the triangles, and renders the path to end

Coloring

• The white space is the space outside of the arragement
• Green Edges are passable by the puck
• Red Edges are unpassable by the puck
• Orange Edges are passable edges by the puck and are on the edge of the arragement
• Blue Pucks are pucks to be pathed around
• The Red puck is the starting puck
• Green Triangles are passable
• Red Triangles are not passable
• Purple Triangles are explored
• The Gray line is the path out of the arragment (the puck can legally exist in any triangle interesected by it, most of the time it is the correct path [see bugs])

Why does it work?

Every delaunay edge is the closest path from one point to another, and each circumcicle is equadistant between each of the points. Futhermore each triangle's circumcircle does not contain any other point. What that means is a puck can pass between 2 other points if there's a delaunay edge between them and the puck can fit between them. A puck can pass through a triangle if it can fit in the circumcenter's radius. Due to the fact this is a delaunay triangulation, those points on the edges are the farthest away from adjacent disks. Circumcircle centers are the farthest away from the verticies of the delaunay triangulation.

I'm able to determine the convex hull in O(n) time since I kept track of neighbors. Each edge has between 1 and 2 neighbors in the triangulation. If there exists a triangle that has 1 neighbor and it were not on the convex hull, then there must be an outer edge not on the convex hull. If there is an outer edge that not on the convex hull, it must be in a hole. Since this triangulation does not include holes, then any edge with one neighbor has to be on the convex hull.

How fast is it?

1. The triangulation runs in O(n log n) time since it used the edge flip method and there are only O(n log n) edge flips possible.
2. Build takes O(3n) time since it iterates though all ther triangles and verticies in constant time. The convex hull is extracted in O(3n) time since each edge has a neighbor and the number can be checked in O(3n) time.
3. Pathing does not explore any triangle more than once, therefore it runs in O(n) time. The map is explored with minimum edge distance heuristic (justAnotherGreedyHeuristic) so it's faster than that most of the time.
4. Rendering takes in O(n + m) time since it's limited by the size of the path and the number of triangles. Since the leghth of the path is at maximum a factor of the number of triangles, it total it runs in O(n) time.
5. Space worst case is the limiting factor of O(n^2) since edges and vertecies are related and there can be equal number of both. This is pretty close to an impossiblity although I can not prove it formally. Google Chrome usually gets slow for me at about 250 disks.

Design Decisions

I modified the existing delaunay triangulation methods by adding some methods to the api like midpoint. But more importantly I've fixed an issue that would have delaunay.js run in O(n^2) time in exchange for adding O(2n) space, which is neglible since delaunay.js takes up O(n) space originally. I did this by replacing the arrays with custom-built sets.

I've used sets whenever possible so that duplicate detection can be done in O(1) time. I've stored a radius in each vertex for the possiblility of having variable sized pucks, something that I was not able to achieve. Each I split puck into 2 methods so they could possibly split during certain operations, another optimization I was not able to achieve.

Check out the code for comments and more information

Bugs

1. Double lines may render becaouse of misalignments in canvas.js (sometime noticable on the convex hull)
2. The path line will get to close to the vertex of an obtuse triangle sometimes, and delaunay.js will ignore triangles so obtuse that they're basically canonical
3. It's on the web, so things sometimes don't load at the same time

Credits

Credits to Google for Canvas.js, and Joshua Bell for the modified Delaunay.js

This work is dedicated to the Public Domain.