# Generalized Voronoi Diagram

I need to compute the Voronoi diagram for a map with some obstacles but I can't find any pseudo-code or example in MATLAB.

The "voronoi" function in MATLAB works with points, but in this case the obstacles are polygons (convex and non-convex). You can see the map in the attached image.

Because the obstacles are polygons I found that the Voronoi algorithm needed is the GVD (Generalized Voronoi Diagram).

Can anyone help with code or examples on internet explaining how to compute this GVD?

• Maybe you should explain what you want to do with it, and where your problems are. Searching for Voronoi on e.g. github should provide you with enough examples. Jun 15 '16 at 11:25
• I finally found an example with MATLAB code here: smallsats.org/2014/01/26/voronoi-road-map-path-planing. But thanks for the idea of searching in github. Jun 16 '16 at 18:48
• If you found the answer to your question you can post the answer and then accept it. Jul 13 '16 at 14:31
• Can you post the expected output you want to achieve?
– Ben
Jul 14 '16 at 10:39

The project repositories at Florida State should get you what you are looking for: https://people.sc.fsu.edu/~jburkardt/m_src/m_src.html

Look at not only the projects which start with "voronoi_," but also "sphere_voronoi."

• Thanks! I will take a look whether it is possible to compute the Voronoi diagram for polygon obstacles with those projects. May 14 '16 at 15:44
• I got involved in the development of Voronoi diagram for Scilab, and starting by Delaunay and then turning to Voronoi resulted much easier to create Jul 13 '16 at 20:20

I bet some simple OpenCV code could do this. I think you would first get the endpoints of the contours. Then feed those points into the voronoi generator.

In advance, that you need the Voronoi diagram for motion planning, here is an RRT implementation in matlab: http://arms.nu.edu.kz/research/matlab-toolbox-rrt-based-algorithms

I have created a Python implementation which is until now not available on github but follows the idea of LaVelles paper "Rapidly-Exploring Random Trees: A New Tool for Pathplanning" (1998). My implementation not only samples the state-space of a 2d maze, but also uses a underlying physics engine for motion prediction. It was programmed in under 200 Lines of code with the help of the eclipse IDE and is capable to drive a robot to every point in the maze. It's a little bit like the famous A* pathplanning algorithm but it's more general and has a probabilistic background.