search

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
198 stars 68 forks source link

fix LLLPARASolver - drop solution that lies on the wrong line side #20

Closed Rogach closed 9 years ago

Rogach commented 9 years ago

Please review this change. I'm not sure this is the best way to do this, but it works.

aewallin commented 9 years ago

I added two scripts with python code for the polygons that you found: python_examples/issues/polygon_2015-02-09.py python_examples/issues/polygon_2015-02-19.py

however this patch doesn't seem to solve the problem for me. I get an assertion error for both polygons: ovd::LineSite::LineSite(const ovd::Point&, const ovd::Point&, double, ovd::Site::HEFace): Assertion `fabs( eq.a_eq.a + eq.b_eq.b -1.0 ) < 1e-5' failed. Aborted (core dumped)

I'll try to take closer look at this over the weekend.

Rogach commented 9 years ago

That's very strange. I re-tested it with everything cleaned up, and no error happened.

Just in case, the exact code I used to test: https://gist.github.com/Rogach/1fbf782d843e92f694d3

Rogach commented 9 years ago

I found possible problem with this patch. It expects that k values are correctly showing offset direction from corresponding adjacent linesites, while it's not always the case. add_vertices takes pos_site in insert_line_site, so all new vertices have k3 set for pos_site. When setting k values for the edges, however, those values "poison" the edges, and in the next step vertex positioner picks up the wrong k values.