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

Failure on n-gons with even n #27

Open dmitryplatonov opened 9 years ago

dmitryplatonov commented 9 years ago

I feel it's due to parallel edges in such n-gons, but not completely sure. Made simple test generator: http://pastebin.com/ULwQdgSw git rev-parse --short HEAD 6c9c25f Output before failure with n=100 add line 49 : 370 377 add line 50 : 377 384 add line 51 : 384 390 WARNING empty solution set!! WARNING in_region_filter() results in empty solution set!! WARNING t_filter() results in empty solution set!! solution edge: (-1.39563e-05, -0.000444096)1 - (5.52635e-17, -8.75288e-18)1 solution edge: 3206[1]{1} -[2]- 3208[1]{0} s1= LineSite: (-0.898224, 0.0565115) - (-0.9, 1.10218e-16)(k=-1) s2= LineSite: (0.898224, -0.0565115) - (0.9, 0)(k=-1) s3= LineSite: (-0.898224, -0.0565115) - (-0.9, 1.10218e-16) Running solvers again: LLLPARASolver. s1 : -0.999507 0.0314108 -0.899556 -1 s2 : 0.999507 -0.0314108 -0.899556 -1 s3 : 0.999507 0.0314108 0.899556 1 bisector: -0.999507 0.0314108 5.55112e-17 Solution: t=0.899556 (-0.9, -28.6385) k3=1 LLLPARASolver. s1 : -0.999507 0.0314108 -0.899556 -1 s2 : 0.999507 -0.0314108 -0.899556 -1 s3 : 0.999507 0.0314108 0.899556 1 bisector: -0.999507 0.0314108 5.55112e-17 Solution: t=0.899556 (-2.77693e-17, -2.6509e-15) k3=-1 No solutions found by solvers! VertexPositioner::desperate_solution() edge: (-1.39563e-05, -0.000444096) - (5.52635e-17, -8.75288e-18) dist(): 0.899556 - 0.899556 WARNING: Returning desperate solution: (0.0305228, 0.971251) t=0.899556 k3=-1 e_err=0.97173 s1_err= 0.404023 s2_err= 0.404023 s3_err= 0.445509 solution_on_edge() ERROR err= 0.97173 solution edge: 3206[1]{1} -[2]- 3208[1]{0} edge: 3206(t=0.899556) - 3208(t=0.899556) edge: (-1.39563e-05, -0.000444096) - (5.52635e-17, -8.75288e-18) solution: (0.0305228, 0.971251) t=0.899556 python: /home/shadowjack/projects/openvoronoi/src/vertex_positioner.cpp:98: ovd::solvers::Solution ovd::VertexPositioner::position(ovd::HEEdge, ovd::Site*): Assertion `solution_on_edge(sl)' failed. Aborted

aewallin commented 9 years ago

Thanks! I will add this as a test for use with ctest when I have time. The issue of numeric robustness and exceptions probably requires some more thought and two or three layers of more 'desperate'/brute-force algorithms to fall back on in hard cases.

aewallin commented 9 years ago

I have added this now in python_examples/issues I will look at the solver - hopefully soon!