search

otfried / ipe

The Ipe extensible drawing editor
http://ipe.otfried.org
159 stars 15 forks source link

Infinite edges in Voronoi diagrams behaving strangely #447

Closed Nacknime closed 1 year ago

Nacknime commented 1 year ago

bug.pdf When creating a Voronoi diagram of all the points in the attached picture, some edges are extended into infinity, and cause visual bugs as shown in the following picture:

image

I think this might be related to closed issue #301 , but I am using Ipe 7.2.26 (on Fedora Wayland), in which this should be fixed already.

otfried commented 1 year ago

The Voronoi code using qhull uses floating point arithmetic, it has issues with very degenerate situations like this one.

I have added some slack so this example will work correctly in 7.2.27. In general, however, you may be better off with the CGAL ipelet which is meant to handle arbitrary inputs.