locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.95k stars 440 forks source link

Improve robustness of Delaunay Triangulation algorithm #310

Open dr-jts opened 6 years ago

dr-jts commented 6 years ago

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 #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 commented 6 years ago

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

dr-jts commented 6 years ago

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 overlapspredicate.

dr-jts commented 6 years ago

See #311 for a sketch of an adaptive inCircle function