How to get the points around a voronoi cell?

5
votes

I am trying to get the points which form a polygon to fill it with some color. I have a set of points and then I calculate the Voronoi Diagram for it. The result is this:

Voronoi Diagram

Green points are the points I define and blue points are the calculated vertices for the Voronoi Diagram. I want to fill the polygon which is generated by an specific green point so I need to know which points are around it to form the polygon and fill it.

I have read about Gift Wrapping Algorithm and Convex Hull but it doesn't seems to be what I need. Is there any algorithms to suit this need ? I am programming in C++ but any help in Java or C# would be helpful.

2
c++algorithmpolygonvoronoi
Matlab voronoi(x,y) function gives you full info you need. – David
I am doing it in C++, so Matlab is not an alternative, I need an algorithm to write in my program – Andres
C++ calls matlab (via COM) is no problem, the point is whether you want to dive into the black box. – David
There is a platform independent C++ standalone library? Because then I will distribute my program and I can't install Matlab everywhere. I don't know too much about Matlab so I am asking. – Andres
if you want to deploy it to other PC, this is no longer a choice. Though feasible, but very cumbersome and it will consume you a lot of time. Leave it. – David

2 Answers

1
votes

The Gift Wrapping algorithm (which is a convex hull algorithm) is for finding the smallest convex polygon that contains a set of points in the plane. That's not what you want here.

Fortune's algorithm is a good solution for finding the actual boundaries of your Voronoi diagram. It's not a trivial algorithm, but a full pseudocode is provided on the linked Wikipedia page. At the bottom of the Wikipedia page, there are links to implementations of Fortune's algorithm in a few different languages.

0
votes

Your implementation of Fortune's algorithm appears to compute the natural embedding, which can be used to extract edge lists for the faces. Here is the critical data structure.

struct Halfedge 
{
    struct  Halfedge    *ELleft, *ELright;
    struct  Edge    *ELedge;
    int     ELrefcnt;
    char    ELpm;
    struct  Site    *vertex;
    float   ystar;
    struct  Halfedge *PQnext;
};

ELleft and ELright appear to be a doubly-linked list that contains the edges incident to a particular vertex or face, sorted by angle. If it's a face, you're golden; otherwise, you can iterate around a face by updating the half-edge e to the reverse of the next half-edge in (counter)clockwise order about its destination vertex (i.e., the reverse of ELleft).