I would like to generate a composite diagram of two Voronoi diagrams. I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered.

Basically, I have two sets of convex polygons (Voronoi diagrams) generated by two sets of overlapping coordinates. I want to overlay the Voronoi diagrams on top of each other and calculate the the areas of the intersected polygons as well as the membership of each intersected polygon -- each intersected polygon is a member of 2 polygons, one polygon from each Voronoi diagram.

I start with two sets of Voronoi cells calculated over the same region of interest. I want to output a list of intersected polygons with their associated Voronoi members as well as the areas of the intersected polygons.


  • $\begingroup$ A Voronoi diagram is a specific type of planar subdivision. What you want sounds a lot like map overlay of planar subdivisions, that is find the new areas that result from drawing the two diagrams on top of eachother. However, I'm not sure if that is what you want. Can you clarify? $\endgroup$ – Discrete lizard Jun 20 '19 at 17:15
  • $\begingroup$ That is precisely what I want: an overlay of two planar subdivisions. The information I want from that are the areas of the new map, say there are N areas, and then an Nx2 list of the member polygons from the original two subdivisions with respect to the new areas. $\endgroup$ – Pedro Relich Jun 20 '19 at 20:17
  • 1
    $\begingroup$ Found a good link for a map overlay approach: slideplayer.com/slide/4520337 . I will follow up with an answer when I've written something that works. $\endgroup$ – Pedro Relich Jul 15 '19 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.