I want to construct the minimal convex hull of some n points such that the hull is a regular polygon of degree n. Math friends, pointers? :)
Conversation
Ah, yes! The last of these in particular seems close…
Basically trying to find minimal circumscribing n-gon
1
for an approximation, you could use Megiddo's algorithm for smallest circle and then circumscribe+shrink an n-gon about that
2
Yeah, that's a good strategy! I do know the minimal diameter of the n-gon (it's the diameter of the convex hull), so that helps.
1
Yeah, but diameter of n-gon ≤ diameter of circumcircle (consider equilateral triangle) :(
1
Right, I guess I mean: I know how far to try shrinking! Still seems probably intractable to do at 60 Hz? :/
1
oh geez, if you're animating then you have a whole new set of constraints — consistency between frames?
1
1
I, um, haven't thought about that yet. :)
I just want to make a fun multitouch toy!!! :D
1
well it might make your job easier! find an OK bounding n-gon for first frame and then just perturb it to fit new points?
1
1
Replying to
Maybe! Not totally clear how to try perturbing given an event stream, but I can probably come up with guesses.