Many very small edges

[fatlimey]

Love your library, use it heavily. Been finding however that the algorithm generates many tiny edges. The visualization attached places transparent circles on each unique vertex in the mesh and where there are tiny edges the overlapping circles darken by addition. Red circles are the seed points. I would guess that maybe 20% of polygons in a large mesh contain tiny degerate edges. It seems to me these edges could be collapsed without violating the Voronoi rules.

[JCash]

Nice, glad to hear it's of use to someone!

I do wonder though, if the points are actually the same values? It's ofc impossible to know for sure by looking at the image, if the floating point values are close enough.

If they are the same, I wonder if the algorithm actually decided that it should be two points, but the floating point precisionmucks it up and they become close or the same. Are you using doubles or floats?

As for the solution, I agree, especially for my usecases, I wouldn't want degenerate edges in the mix.

Since you already have test data, perhaps you could send the test data (in a .txt file) in the form? Makes it a little bit easier/faster when one has the same data

rectmin_x rectmin_y rectmin_x rectmin_y
point_x, point_y
point_x, point_y
point_x, point_y
point_x, point_y

[fatlimey]

You are correct, there are two issues (setting aside the problem that jvc_diagram_get_next_edge() seems to visit each edge twice):

1. When visiting adjacent sites, vertices that are shared often have different floating point coordinates, sometimes differing by as much as 1e-5 even though they are the "same" vertex.

2. When visiting edges using using jvc_diagram_get_edges() / jvc_diagram_get_next_edge() the code skips over edges that are zero length using the jvc_point_eq() test that tests for equality using FLT_EPSILON. This epsilon is the smallest value that can be added to 1.0 to get a new value, a value which only applies to values in the floating point decade [1.0, 2.0). If you are generating a Voronoi mesh outside of the unit square, say in the range [-100,100], then this test will always succeed regardless of the difference between the values. A better test would take into account the relative size of the floating point values (cite: https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/)

I will get you a set of example Voronoi points to play with - I have a weird point set and bounding box because I am trying to produce tiling meshes and have to repeat wrapped points to each edge and remove the sites that touch the bounding box. give me a moment to hack up some representative voronoi points in the [0,100] range that demonstrate the problem.

[JCash]

differing by as much as 1e-5 even though they are the "same" vertex.

The question is though: Are they logically the same? E.g. imagine if we had infinite precision, would they still be different points? If so, then it's not actually a bug per se, more like an inconvenience for the end user that they are impractically close. I suspect you agree since you quoted it as the "same".

Question is, how to filter out those vertices, in the library or on the user end. In cases like this, I tend to opt for a solution that doesn't add extra complexity into the base library, and instead let the user cleanup the data. However, I wonder if it's a case where the library should help out.

If you are generating a Voronoi mesh outside of the unit square, say in the range [-100,100]...

Correct, the user needs to cater for their use case, and perhaps choose double precision if necessary, and/or transform the set of points to around origin. As an extra help, there's the JCV_REAL_TYPE_EPSILON which the user can configure to fit their set of corrdinates. Possibly, it might be relevant to add a function override instead, so that user can compare numbers that have different exponents.

I agree that if the edge iterator skips edges depending on jvc_point_eq(), then the rest of the api needs to have the same mindset.

setting aside the problem that jvc_diagram_get_next_edge() seems to visit each edge twice

Hmm, I haven't noticed this before. Do you have a small repro case for this? And, please attach that data to a new ticket, please!

[fatlimey]

Are the vertices logically the same? Well, if the sites are sharing an edge then the vertices of each end of the edge should be equal. But I understand that doing that greatly complicates the building of the voronoi diagram, you need to know edge and site adjacency information to update pairs of polygons every time an edge is changed. Leaving that to some reconstruction code is OK by me, I can match the points and edges to whatever precision I am looking for. Some example matching code would be helpful, for example I used std::hash and std::unordered_set to medium-quickly match edges (a spatial data structure would have better O(1) performance once constructed)

Here is a set of points in the format you requested that generates the following diagram (for me) inside a box [-2.5,-2.5] to [17.5,17.5]. voronoi-points-generate-small-edges.txt

My graphical analysis of the edges generated shows some edges with tiny lengths. Not a stellar example but there a few examples in there.

[JCash]

if the sites are sharing an edge then the vertices of each end of the edge should be equal

I do think that the shared vertices of the edges are the same, since they should come from the shared jcv_edge struct, which each half edge points to. The half edge does hold a pos[2] as well, but it's for performance reasons.

But having shared vertices isn't the problem, right? The problem is that some edges are extremely short?

My current idea is that it should "just work" to skip those short edges? E.g. just like in jcv_diagram_get_next_edge(), I'll add an iterator for the sites, and edges and let that iterator do the skipping. ANd if the user wants the raw data, they can iterate manually themselves. (Also, I plan to add a use replace'able function(s) for detecting equality to solve for the user's epsilon)

[NongBenz]

I seem to be having a related issue. I'm iterating through the sites and their respective site edges. But after the first site which works fine, the following cells have duplicated edges (note 2 lines represent a single pair of edge points):

LogBlueprintUserMessages: [BP_Hex_C_1] New Cell===========
LogBlueprintUserMessages: [BP_Hex_C_1] X=4.379 Y=-37.472
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-9.417 Y=-34.563
LogBlueprintUserMessages: [BP_Hex_C_1] X=-9.417 Y=-34.563
LogBlueprintUserMessages: [BP_Hex_C_1] X=0.000 Y=-40.000
LogBlueprintUserMessages: [BP_Hex_C_1] X=0.000 Y=-40.000
LogBlueprintUserMessages: [BP_Hex_C_1] X=4.379 Y=-37.472
LogBlueprintUserMessages: [BP_Hex_C_1] New Cell=========== (duplicated stuff starts here)
LogBlueprintUserMessages: [BP_Hex_C_1] X=13.817 Y=-32.023
LogBlueprintUserMessages: [BP_Hex_C_1] X=1.716 Y=-25.791
LogBlueprintUserMessages: [BP_Hex_C_1] X=1.716 Y=-25.791
LogBlueprintUserMessages: [BP_Hex_C_1] X=1.716 Y=-25.791
LogBlueprintUserMessages: [BP_Hex_C_1] X=1.716 Y=-25.791
LogBlueprintUserMessages: [BP_Hex_C_1] X=-3.473 Y=-25.306
LogBlueprintUserMessages: [BP_Hex_C_1] X=-3.473 Y=-25.306
LogBlueprintUserMessages: [BP_Hex_C_1] X=-3.473 Y=-25.306
LogBlueprintUserMessages: [BP_Hex_C_1] X=-3.473 Y=-25.306
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=4.379 Y=-37.472
LogBlueprintUserMessages: [BP_Hex_C_1] X=4.379 Y=-37.472
LogBlueprintUserMessages: [BP_Hex_C_1] X=13.817 Y=-32.023
LogBlueprintUserMessages: [BP_Hex_C_1] New Cell===========
LogBlueprintUserMessages: [BP_Hex_C_1] X=-3.473 Y=-25.306
LogBlueprintUserMessages: [BP_Hex_C_1] X=-5.555 Y=-19.150
LogBlueprintUserMessages: [BP_Hex_C_1] X=-5.555 Y=-19.150
LogBlueprintUserMessages: [BP_Hex_C_1] X=-13.829 Y=-17.098
LogBlueprintUserMessages: [BP_Hex_C_1] X=-13.829 Y=-17.098
LogBlueprintUserMessages: [BP_Hex_C_1] X=-16.875 Y=-30.257
LogBlueprintUserMessages: [BP_Hex_C_1] X=-16.875 Y=-30.257
LogBlueprintUserMessages: [BP_Hex_C_1] X=-9.417 Y=-34.563
LogBlueprintUserMessages: [BP_Hex_C_1] X=-9.417 Y=-34.563
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-8.439 Y=-33.764
LogBlueprintUserMessages: [BP_Hex_C_1] X=-3.473 Y=-25.306
...

This is the code I'm running, it's pretty safe so I don't think it's an initialization issue. My FVectors do use doubles but I cast all sites to floats before sending to the voronoi library.

// Process the diagram and populate OutCells...
// Iterate over the Voronoi sites to create cells
const jcv_site* SitesArray = jcv_diagram_get_sites(&Diagram);
for (int32 Index = 0; Index < Diagram.numsites; ++Index)
{
    const jcv_site* Site = &SitesArray[Index];
    FVoronoiCell CellWrapper = {};

    // Set the site location
    CellWrapper.Site = FVector2D(Site->p.x, Site->p.y);
    // Iterate over the edges of the cell
    const jcv_graphedge* SiteEdge = Site->edges;
    while (SiteEdge)
    {
        CellWrapper.Edges.Add(
            FVector2DPair(
                FVector2D(SiteEdge->pos[0].x, SiteEdge->pos[0].y), 
                FVector2D(SiteEdge->pos[1].x, SiteEdge->pos[1].y)));
        SiteEdge = SiteEdge->next;
    }
    // Add the cell to the output array
    OutCells.Add(CellWrapper);
}

[NongBenz]

For anyone else stuck on my issue, using a larger JCV_REAL_TYPE_EPSILON which is used for pruning duplicate edges fixed it for me. #define JCV_REAL_TYPE_EPSILON 1e-05