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 Source Diagram To Target Diagram

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)


1 Answer 1


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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.