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
\(\,\)c \(\,\)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 \(\,\)g \(\,\) to start mass
random
sampling within the polygon and press it again to stop. Press \(\,\)l \(\,\) to see the cut
locus
generated by the red circles. Hit \(\,\)r \(\,\) to
reset.
Overview
The algorithm for finding the cut locus after the polygon is created goes roughly as follows:
- Triangulate the polygon
- Sample points randomly from each triangle
- For each point, precompute distance from each edge of the polygon
- If the two shortest distances are within some \(\varepsilon\) (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.