Cut Locus

Note: the code below is a bit buggy and a work in progress!

Click on the canvas below to draw a point. Press

on your keyboard to close the the polygon when finished and click again to spawn a circle. A red circle is maximal and a blue (low alpha) is not. Press

to start mass random sampling within the polygon and press it again to stop. Press

to see the cut locus generated by the red circles. Hit

to reset.

Overview

The algorithm for finding the cut locus after the polygon is created goes roughly as follows:

Triangulate the polygon

see triangulation

Sample points randomly from each triangle

see this stack overflow post on it

For each point, precompute distance from each edge of the polygon

see this paper

If the two shortest distances are within some $ε$ (say, 3 pixels), then that point is in the cut locus

It's important to make sure that the two shortest distances aren't secretly the same point! Consider a vertex in some concavity of the polygon; we need to make sure that that vertex is not double counted since it exists in two edges.

Issues

There are many issues with my implementation and this method in general.

The random sampling is not weighted by area of each triangle, so samplings are denser in triangles with smaller area.
Despite this, the sampling sometimes struggles with small areas of a polygon for some reason.
A random sampling isn't going to get a super accurate or consistent picture of the actual cut locus.
Some bugs happen when a circle spawns too close to a vertex of the polygon.