-
Notifications
You must be signed in to change notification settings - Fork 440
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Voronoi diagram fails due to self-intersecting polygons #447
Comments
A test case to reproduce the problem of slightly different triangle circumcentres:
The current JTS
It might be possible to improve this using |
Fixed by #448 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Voronoi diagram building fails on the following input, due to the fact that some of the input sites lie on a grid pattern, which causes some Voronoi polygon vertices to experience numerical precision errors.
This is due to a couple of the generated Voronoi polygons being topologically invalid, and because of that failing during the intersection computation (when clipping the raw Voronoi polygons to a surrounding rectangle).
The reason the polygons are invalid is that they contain two points which are almost identical, one of which happens to lie on another edge of the polygon, thus creating a self-intersection.
The reason the very close points are present is because the input points (Voronoi sites) generating them lie on a regular grid pattern. This produces two Delaunay triangles with almost identical circumcentres. They are not 100% identical because of round-off error. The DT circumcentres form the vertices of the Voronoi polygons, and so polygons are created with almost-but-not-identical points in them.
Original report: https://trac.osgeo.org/geos/ticket/976
The text was updated successfully, but these errors were encountered: