aewallin / openvoronoi

2D voronoi diagram for point and line-segment sites using incremental topology-oriented algorithm. C++ with python bindings. Licensed under LGPL2.1.
http://www.anderswallin.net/cam/
GNU Lesser General Public License v2.1
199 stars 68 forks source link

void ovd::VoronoiDiagram::add_edges(ovd::HEFace, ovd::HEFace, ovd::HEFace, std::pair<void*, void*>): Assertion `(new_count % 2) == 0' failed. Aborted (core dumped) #48

Open zengtaiping opened 4 years ago

zengtaiping commented 4 years ago

When I am trying to use the cpp_examples medial_axis, I found the error:

void ovd::VoronoiDiagram::add_edges(ovd::HEFace, ovd::HEFace, ovd::HEFace, std::pair<void, void>): Assertion `(new_count % 2) == 0' failed.

With the code:

    ovd::Point p0(3.25,1.15);
    ovd::Point p1(1.1,1.15);
    ovd::Point p2(-0.275,1.15);
    ovd::Point p3(-1.25,0.475);
    ovd::Point p4(-0.95,-1.1);
    ovd::Point p5(1.1,-1.15);

    int id0 = vd->insert_point_site(p0);
    int id1 = vd->insert_point_site(p1);
    int id2 = vd->insert_point_site(p2);
    int id3 = vd->insert_point_site(p3);
    int id4 = vd->insert_point_site(p4);
    int id5 = vd->insert_point_site(p5);

    vd->insert_line_site(id0, id1);
    vd->insert_line_site(id1, id2);
    vd->insert_line_site(id2, id3);
    vd->insert_line_site(id3, id4);
    vd->insert_line_site(id4, id5);
    vd->insert_line_site(id5, id0);
    vd->check();

However, when I remove Point p1 and remake, it works without errors. With the code:

    ovd::Point p0(3.25,1.15);
    // ovd::Point p1(1.1,1.15);
    ovd::Point p2(-0.275,1.15);
    ovd::Point p3(-1.25,0.475);
    ovd::Point p4(-0.95,-1.1);
    ovd::Point p5(1.1,-1.15);

    int id0 = vd->insert_point_site(p0);
    // int id1 = vd->insert_point_site(p1);
    int id2 = vd->insert_point_site(p2);
    int id3 = vd->insert_point_site(p3);
    int id4 = vd->insert_point_site(p4);
    int id5 = vd->insert_point_site(p5);

    vd->insert_line_site(id0, id2);
    // vd->insert_line_site(id1, id2);
    vd->insert_line_site(id2, id3);
    vd->insert_line_site(id3, id4);
    vd->insert_line_site(id4, id5);
    vd->insert_line_site(id5, id0);
    vd->check();

I think the different points caused the problems. But I did not find why it happens. Thanks.

aewallin commented 4 years ago

can you draw your points and line-sites in a 2D drawing and attach it here? (for example crossing lines are not allowed input to openvoronoi)

zengtaiping commented 4 years ago

@aewallin Thanks for your quick response. There are no crossing lines in this simple example. I plot the points and connected lines without the last point to the start point, for easy viewing. The six points figure with error: six_points_error

The five points figure without error: five_points_without_error

zengtaiping commented 4 years ago

Any suggestions to solve this problem? @aewallin

aewallin commented 4 years ago

in your first example above, I am guessing the error comes from inserting the second line-site, vd->insert_line_site(id1, id2), which is co-linear with the first site?

one would have to study the code in depth to look at what is causing the problem. line-sites that are either at 90-degrees to each other, or like in your case at 0-degrees/co-linear to each other are special cases.

yuyue2013 commented 3 years ago

So line-sites can not at 90-degrees to each other?

aewallin commented 3 years ago

There are two ways to solve this:

In practice I haven't had much time to work on openvoronoi in the past years, so I don't know if/when this might move forward. If there's another maintainer that is eager to take over then please go ahead!

dbdxnuliba commented 3 years ago

hello @zengtaiping , did you find the solution