patternMinor
Algorithm for animating/morphing convex polygon diagrams
Viewed 0 times
convexmorphingdiagramsanimatingalgorithmforpolygon
Problem
I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type.
The target diagram is usually generated from the source, where all kind of operations may happen (new polygon popping up, polygon gets deleted etc.)
So for example I may want to go from
To
with the following constraints:
I tried looking around for papers and/or previous work on that, but failed spectacularly in finding anything, so...
Does anyone here have any idea/references?
(Heck, I'm not even sure this is the right stack exchange board to ask for it)
The target diagram is usually generated from the source, where all kind of operations may happen (new polygon popping up, polygon gets deleted etc.)
So for example I may want to go from
To
with the following constraints:
- Morphing between the two diagrams should be smooth (e.g: new polygons should not pop up but kind of grow)
- In all intermediate diagrams the polygons should be simple and convex
I tried looking around for papers and/or previous work on that, but failed spectacularly in finding anything, so...
Does anyone here have any idea/references?
(Heck, I'm not even sure this is the right stack exchange board to ask for it)
Solution
If your initial set of polygons is a power-diagram, you can insert a new polygon by inserting a new center and growing its power circle smoothly. You don't have direct control of the polygons but rather of the underlying power circles. Power diagrams as Voronoi diagrams are always made of convex polygons.
https://diglib.eg.org/bitstream/handle/10.2312/evs20201057/109-113.pdf
Another way is to subdivide one of the polygons slicing it with a straight line, similar to a spatial partition tree, to ensure the resulting polygon is still convex. http://proceedings.mlr.press/v84/fan18b/fan18b.pdf
https://diglib.eg.org/bitstream/handle/10.2312/evs20201057/109-113.pdf
Another way is to subdivide one of the polygons slicing it with a straight line, similar to a spatial partition tree, to ensure the resulting polygon is still convex. http://proceedings.mlr.press/v84/fan18b/fan18b.pdf
Context
StackExchange Computer Science Q#117580, answer score: 2
Revisions (0)
No revisions yet.