3 ms·
I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to
by eutectic 6y ago
I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to extend it to capture non-convex geometry.
E.g. cutting off 2 ears to create 3 regions vs cutting off whole head to create 2 regions.
- klmadfejno 6y agoThat's an impressive quick effort. My second initial gut reaction says you could add a point to the graph at the local minima of a non-convex curve and use it as a way to generate additional candidate, but not require the solver to eliminate it? Could probably smoosh an extra rule inn there somehow to eliminate pieces on that particular piece, but it wouldn't generalize to all non convex curves.
- eutectic 6y agoAfter some thought I think it works as-is if you just delete all edges between points which can't directly see each-other, as long as the visibility graphs are still connected. The best cuts could then sometimes be edge->edge instead of always vertex->vertex. (e.g. each point at a random position in a little bump, where you want to slice off all the bumps in one go without going off at a random angle. I'm trying to think about the topology of cuts in the plane but its hard to visualize. I guess it must be related to Voronoi and Delaunay.