search

TaipanRex / pyvisgraph

Given a list of simple obstacle polygons, build the visibility graph and find the shortest path between two points
MIT License
217 stars 45 forks source link

Visibility graph bug #51

Open yaara-shoval opened 4 years ago

yaara-shoval commented 4 years ago

I tried to build a visibility graph with the following input: [[vg.Point(x=119.55624999999999, y=16.48333333333367), vg.Point(x=203.7872976182326, y=81.64246915103985), vg.Point(x=203.78733213720346, y=112.326984303335), vg.Point(x=189.70101758191677, y=112.326984303335), vg.Point(x=184.99113388465582, y=75.10000000000025), vg.Point(x=184.99113388465582, y=103.01666666666668), vg.Point(x=133.69454408285583, y=103.01666666666668), vg.Point(x=133.69454408285583, y=75.10000000000025), vg.Point(x=131.22787741618916, y=75.10000000000025), vg.Point(x=131.22787741618916, y=103.0166666666666), vg.Point(x=119.55624999999999, y=103.01666666666759)]].

This was the result: image

I solved this by rounding the points before giving them as input. I suggest fixing this bug.

TaipanRex commented 3 years ago

This isnt really a bug, its a consequence of small differences in floating points. See this, "floating point representation errors".