3
$\begingroup$

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.

enter image description here

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Jakob Jun 15 '16 at 11:25
  • $\begingroup$ 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. $\endgroup$ – osuarez Jun 16 '16 at 18:48
  • 2
    $\begingroup$ If you found the answer to your question you can post the answer and then accept it. $\endgroup$ – Chuck Jul 13 '16 at 14:31
  • $\begingroup$ Can you post the expected output you want to achieve? $\endgroup$ – Ben♦ Jul 14 '16 at 10:39
1
$\begingroup$

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."

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! I will take a look whether it is possible to compute the Voronoi diagram for polygon obstacles with those projects. $\endgroup$ – osuarez May 14 '16 at 15:44
  • $\begingroup$ 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 $\endgroup$ – galtor Jul 13 '16 at 20:20
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Welcome to Robotics, ManuelRodriguez. On StackExchange we are are looking for comprehensive answers that provide some explanation and context. One-line answers cannot do this, so please edit your answer to add context, ideally with citations. Answers that don't include explanations may be removed. Additionally, we prefer answers to be self contained if possible. Links tend to rot so answers which rely on a link can be rendered useless if the linked content disappears. If you add more context it is more likely that people will find your answer useful. $\endgroup$ – Chuck Jul 21 '16 at 18:07
  • $\begingroup$ Specifically, what is RRT? Could you explain it and its relation to the generalized Voronoi diagram? $\endgroup$ – Chuck Jul 21 '16 at 18:08

Your Answer

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

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