Site vertices

[kewp]

If I want to create a mesh from the sites can I use edges and assume they are connected, i.e. iterate through edges and add each starting point to a list of vertices ?

[JCash]

Yes. That's one of the main features I wanted from this project, I found it hard to do with other solutions.

See the main.c which is used to generate the example image by iterating the edges, and drawing each edge+site triangle one by one.

[kewp]

Do they come out in order, e.g. clock wise and connected?

[JCash]

Yes, always connected and CCW. It also inserts new edges in case it was clipped against the border of the bounding box. (I should make that clearer in the README).

[kewp]

Awesome. Thanks so much

[kewp]

I'm struggling to get a mesh without lines that cross. Am I doing something wrong ?

I have a struct of Mesh, Element and Vertice.

  sites = jcv_diagram_get_sites(&diagram);

  Mesh mesh;
  mesh.nelms = diagram.numsites;
  mesh.elms = (Elm*) malloc(sizeof(Elm)*diagram.numsites);

  for (i=0; i<diagram.numsites; i++) {

    // get number of edges
    int numedges = 0;
    graph_edge = sites[i].edges;
    while (graph_edge) { numedges++; graph_edge = graph_edge->next; }

    mesh.elms[i].nverts = numedges;
    mesh.elms[i].verts = (Vert*) malloc(sizeof(Vert)*(numedges));

    graph_edge = sites[i].edges;

    int j; for (j=0; j<numedges; j++)
    {
        mesh.elms[i].verts[j].x = (double) graph_edge->pos[0].x;
        mesh.elms[i].verts[j].y = (double) graph_edge->pos[0].y;

        graph_edge = graph_edge->next;
    }
}

[JCash]

I think that looks about right. What do you mean "lines that cross"? The output data, or your usage of the data? Given an example with one or two points, and printing out the vertices for each polygon, does it look right then?

[david94133]

That code looks fine to me. I've generated many, many large voronoi diagrams with this library (> 100,000 sites) and have never seen crossed edges.

The coordinates of the vertices have some rounding errors, causing the vertices for adjacent edges to not match exactly. That could cause edges to cross, if by cross you mean a very small amount right at the end of the edge. In my own code I changed JCV_REAL_TYPE to be double, which fixed this inaccuracy.

[kewp]

It was my fault. I didn't put in a separate line in the data file to separate line segments for GNUPlot !

https://i.imgur.com/N77JYe0.png

[kewp]

Not sure how to upload an image ...

[kewp]

image

All working perfectly :)

[JCash]

Ah, good!

[kewp]

Does my image look right ?

[JCash]

Well, it's a little bit difficult to see without the sites plotted, but I think it looks ok.

You can also use one of the online generators (which sometimes accept input data) to verify (e.g this

[kewp]

OK. Will try that. Thanks again !