List of unique vertices

[kewp]

One more issue :/

Because I want to create a mesh, I need a list of unique vertices. These are stored as x,y points. Any idea how to do this ?

My naive algorithm would go as follows:

• Loop through all sites and their edges and add them all together (i.e. 5 sites each with, say, 5 edges gives a maximum of 25 vertices)
• Now we have a maximum. Allocate an integer for each (to be used as boolean). Set all to 1.
• Loop through again, this time with an inner loop starting from the outer loop +1
• In the inner loop, check if the outer loop position as the same as inner. If so, set the value of the integer to 0 (not unique).

Now we have a list of unique vertices ...

Not very elegant. Any better ideas ?

Also - can I just use an equals check on the positions (x1==x2) even though they are floats ?

[kewp]

This is what I'm thinking. It's messy !

jcv_graphedge* edge, edge2;

// count total edges
int edges = 0;
for (i=0; i<mesh.diagram.numsites; i++)
{
    edge = sites[i].edges;
    while (edge) {
        edges++;
        edge = edge->next;
    }
}

// mark which can be considered unique
int* unique = (Int*) malloc(sizeof(int)*edges);
memset(unique, 1, sizeof(int)*edges); // initially all of them

// loop through every edge
int ei=0; // index into unique list
for (i=0; i<mesh.diagram.numsites; i++)
{
    edge = sites[i].edges;
    while (edge) {

        // loop through all the next sites
        int j; for (j=i+1; j<mesh.diagram.numsites; j++)
        {
            edge2 = sites[j].edges;
            while (edge2) {

                // zero out unique list if future edge has same vertice
                if (edge->pos[0].x==edge2->pos[0].x && edge->pos[0].y==edge2->pos[0].y)
                    unique[ei] = 0;

                edge2 = edge2->next;
            }
        }
        edge = edge->next;
        ec++;
    }
}

`

[kewp]

After basic testing this seems to be working

jcv_graphedge *edge, *edge2;

// count total edges
int edges = 0;
for (i=0; i<mesh.diagram.numsites; i++)
{
    edge = sites[i].edges;
    while (edge) {
        edges++;
        edge = edge->next;
    }
}

printf("Found %d edges\n",edges);

// mark which can be considered unique
int* unique = (int*) malloc(sizeof(int)*edges);
for (i=0; i<edges; i++)
    unique[i] = 1;

// loop through every edge
int ei=0; // index into unique list
for (i=0; i<mesh.diagram.numsites; i++)
{
    edge = sites[i].edges;
    while (edge) {

        printf("Edge %.2f %.2f\n",edge->pos[0].x,edge->pos[0].y);

        // loop through all the next sites
        int j; for (j=i+1; j<mesh.diagram.numsites; j++)
        {
            edge2 = sites[j].edges;
            while (edge2) {

                // zero out unique list if future edge has same vertice
                if (fabs(edge->pos[0].x-edge2->pos[0].x)<0.0001 && fabs(edge->pos[0].y-edge2->pos[0].y)<0.0001)
                    unique[ei] = 0;

                edge2 = edge2->next;
            }
        }
        edge = edge->next;
        ei++;
    }
}

int c=0;
for (ei=0; ei<edges; ei++)
{
    if (unique[ei]) c++; // ha
    printf(" %d",unique[ei]);
}
printf("\n");
printf("Found %d unique\n",c);

`

[david94133]

I've found that the rounding errors can be quite large for the default configuration, where points are stored as floats. In some cases the error is larger than some edge lengths, which messes up the diagram. I switched to using doubles for JCV_REAL_TYPE and that fixed it.

This is for very large diagrams (over 100,000 cells). It may not be relevant for you.

[kewp]

Thanks for the heads up

On Thu., 21 Jun. 2018, 4:53 pm david94133, notifications@github.com wrote:

I've found that the rounding errors can be quite large for the default configuration, where points are stored as floats. In some cases the error is larger than some edge lengths, which messes up the diagram. I switched to using doubles for JCV_REAL_TYPE and that fixed it.

This is for very large diagrams (over 100,000 cells). It may not be relevant for you.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/JCash/voronoi/issues/21#issuecomment-399132283, or mute the thread https://github.com/notifications/unsubscribe-auth/AAYMan2P4XNk05y049r-T2G3RJNpK_Tuks5t-7NrgaJpZM4UyKcF .

[JCash]

I'll keep this in mind in the future, to see if I can add this in a good way in perhaps some example code. Closing for now though :)