How to get the points around a voronoi cell?

Question

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:

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.

Mental

Matlab voronoi(x,y) function gives you full info you need. – Daradarach

I am doing it in C++, so Matlab is not an alternative, I need an algorithm to write in my program – Mental

C++ calls matlab (via COM) is no problem, the point is whether you want to dive into the black box. – Daradarach

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. – Mental

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. – Daradarach

Yes, but I need to deploy it to other PC :/ – Mental

@Andres: how are you calculating the Voronoi Diagram vertices? If you have access to the source you can modify it to save those vertices for you associated to the points that originated them. – Eulogistic

I am using this library skynet.ie/~sos/mapviewer/voronoi.php So I have acces to the source code but have no idea how it works :/ – Mental

@Mental Try this > Start with the green-point, spread to realize circumference of the polygon like a balloon filling its area with time; when done, extract polygon points from the circumference – Selection

Answer 1

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.

Violetavioletta

check en.wikipedia.org/wiki/Fortune's_algorithm the pseudo code is here, and C code here ect.bell-labs.com/who/sjf/voronoi.tar – Caraway

@Caraway I already have exactly that link in my answer. Did you not see it? – Violetavioletta

Sorry timothy just saw it now, I did not click the link to be sincere.. good job – Caraway

@Caraway Haha no problem - I was just confused why you were commenting with the same exact link. :) – Violetavioletta

The algorithm I am using is fortune algorithm which generates the image I uploaded but it gives me the points of the polygon but I don't know to what site it is associated and that's what I need. I have searched the algorithm because is a little complicated to implement or I can't fully understand it :/ – Mental

@Mental Fortune's algorithm finds all of the information you require while it runs. This should be self-evident: the picture you have has the boundary lines and boundary vertices drawn on it. If the problem is that you're getting back those boundaries without the associated generating points for each boundary segment, then you'll have to inject directly into your implementation some behavior to save that information while the algorithm runs. - That's a nontrivial task - more than you can expect in a Stack Overflow answer. The "boundary rays C_pq" mentioned on the Wikipedia page are a start. – Violetavioletta

Answer 2

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

Prehistoric

Nice I have been examining the source code and I see it. I have seen other Voronoid libraries like blog.ivank.net/fortunes-algorithm-and-implementation.html, the Voronoi Diagram generated is not always right but I have that kind of information. Seems like the struct I want is: struct Halfedge *PQhash – Mental