Skip to content

Improve robustness of Delaunay Triangulation algorithm #310

Description

@dr-jts

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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions