Empty cells

[Mazzelfassel]

In some cases the algorithm calculates empty cells with 0 half-edges. Based on this pointIntersection(double,double) produce wrong results and the relax() function throws some seg-faults. I think maybe its related to setting some target points outside the bounding box

[mdally]

hm, I haven't seen this before. Could you send me the points and bounding box you run it with to get this result?

[Mazzelfassel]

Am 20.04.2017 um 08:45 schrieb Mark Dally:

hm, I haven't seen this before. Could you send me the points and bounding box you run it with to get this result?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/mdally/Voronoi/issues/2#issuecomment-295599923, or mute the thread https://github.com/notifications/unsubscribe-auth/AE7gWTpUd3QLSmP7IIV2mdZVRivNAPjCks5rxv8UgaJpZM4NCW2t.

Points:

{x=1123.7924804690001 y=1208.7784423830001 } {x=1925.1013183590001 y=2659.8022460940001 } {x=1026.0461425780002 y=5587.0288085940001 } {x=3327.6679687500000 y=1125.1007080080001 } {x=2505.9399414060003 y=3207.0190429690001 } {x=3731.6088867190001 y=4844.4243164059999 } {x=6092.5878906250000 y=462.84979248000002 } {x=4866.3159179690001 y=2476.9313964840003 } {x=4305.5952148440001 y=4336.7690429690001 }

BB:

{xL=2048.0000000000000 xR=4096.0000000000000 yB=4096.0000000000000
yT=2048.0000000000000 }

With the given points and bonding box the cells with the index 0, 2 and 8 have 0 half edges (with a total of 8 cells)

[mdally]

The issue here is that sites are outside the provided bounding box.

My implementation requires all sites to be inside the box (not on the borders either). Providing sites outside the box results in undefined behavior.

[patnolan33]

@mdally I am seeing this behavior as well with sites inside the bounding box. Here is a snippet of code that I am using to test the behavior of this library:

    std::shared_ptr<VoronoiDiagramGenerator> generator = std::make_shared<VoronoiDiagramGenerator>();

    // Test sites:
    std::vector<Point2> sites;
    sites.push_back(Point2(2.5,2.5));
    sites.push_back(Point2(5,5));
    sites.push_back(Point2(7.5,7.5));

    // Bounding box:
    BoundingBox bbox(0,10,0,10);

    // Compute diagram:
    Diagram* diagram = generator->compute(sites, bbox);

    std::cout << "Number of cells: " << diagram->cells.size() << std::endl;
    std::cout << "Number of edges: " << diagram->edges.size() << std::endl;
    std::cout << "Number of vertices: " << diagram->vertices.size() << std::endl;
    std::cout << "Point (1,2) in cell 1: " << diagram->cells.at(0)->pointIntersection(1,2) << std::endl;

    // Loop over all cells and print the corresponding site location and number of half edges.
    for(auto cell : diagram->cells) {
        std::cout << "Cell Site:  (" << cell->site.p.x << ", " << cell->site.p.y << ")" << std::endl;

        std::cout << "Cell half edges: " << cell->halfEdges.size() << std::endl;
        // Loop over all half edges and print starting and end points:
        for(auto edge : cell->halfEdges) {
            std::cout << "Start Point:  (" << edge->startPoint()->x << ", " << edge->startPoint()->y << ")" << std::endl;
            std::cout << "End Point:  (" << edge->endPoint()->x << ", " << edge->endPoint()->y << ")" << std::endl;
        }
    }

The output of the above code is:

Number of cells: 3
Number of edges: 0
Number of vertices: 4
Point (1,2) in cell 1: 1
Cell Site:  (2.5, 2.5)
Cell half edges: 0
Cell Site:  (5, 5)
Cell half edges: 0
Cell Site:  (7.5, 7.5)
Cell half edges: 0

This seems to output the correct number of cells and it even checks if a point is in a polygon correctly. However, I never get any edges (or half edges in a cell). Since I don't get any half edges, I also don't get the starting and ending point coordinates to print. Am I missing something?

(p.s. great work on this, it has been super helpful. Thank you!)