Skip to content
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

Improve robustness of Delaunay Triangulation algorithm #310

Open
dr-jts opened this issue Sep 4, 2018 · 3 comments
Open

Improve robustness of Delaunay Triangulation algorithm #310

dr-jts opened this issue Sep 4, 2018 · 3 comments

Comments

@dr-jts
Copy link
Contributor

dr-jts commented Sep 4, 2018

Issue #298 highlights the robustness limitations of the IncrementalDelaunayTriangulator. While there is a heuristic to avoid this issues (using a distance tolerance) it does impose a potentially unwanted constraint. Some work has been done towards improving the robustness of the Delaunay algorithm (in particular, implementation of a robust inCircle predicate using DD precision).

Here's a roadmap to making the robust DT capability available in production:

  1. Add option to IncrementalDelaunayTriangulator to allow using a robust inCircle predicate (i.e. inCircleDDFast)
  2. Add unit tests covering the Overlapping Delaunay triangles #298 failure case (for DT and inCircle predicate). This will require implementing a DT validator
  3. [optional science project] determine if possible to detect triangulation failures when they occur and fail fast, so that user can choose to fall back to using robust inCircle
  4. Do performance testing to see performance impact of using inCircleDDFast. If not too bad then make it the default (and keep option to use FP inCircle if performance is needed).
@Komzpa
Copy link

Komzpa commented Sep 4, 2018

2: extra triangles are quite easily caught by breaking sum(area(delaunay_triangles(geom))) = area(convexhull(geom))

@dr-jts
Copy link
Contributor Author

dr-jts commented Sep 4, 2018

A test based on total area should detect most errors, certainly. However, it might not flag very small extra triangles though. And it doesn't pinpoint where the error is.

A brute force test is to check every pair of triangles using the overlaps predicate.

@dr-jts
Copy link
Contributor Author

dr-jts commented Sep 18, 2018

See #311 for a sketch of an adaptive inCircle function

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants