search

gwlucastrig / Tinfour

Delaunay and Constrained Delaunay Triangulations in Java, providing high-performance utilities for modeling surfaces with support for Lidar LAS files, Digital Elevation Models (DEM), finite element analysis, path planning, natural neighbor interpolation, and other applications of Triangulated Irregular Networks (TIN)
Apache License 2.0
153 stars 34 forks source link

Need enhancement to handle defective polygon constraints #56

Open gwlucastrig opened 3 years ago

gwlucastrig commented 3 years ago

The LogoCDT demonstration application uses Java fonts to provide polygons for rendering constrained Delaunay triangulations. The original implementation was developed using Java 8 and used the font "Arial Black", Bold, 72 pt. However, when running tests in preparation for the 2.1.5 release, we discovered that the CDT was failing. The problem was due to the way more recent versions of Java handled that font specification.

The picture below illustrates the problem. In Java 11, the lowercase letter "a" is formed so that the upper part of the letter touches the lower loop. This geometry violates the requirement that polygon constraints must not intersect themselves. Thus the constraint formed from the letter a is not valid.

This issue requests an enhancement to the current Tinfour API's capabilities for detecting problematic geometries. In the present implementation, some bad geometries can slip through the test procedures.

In the mean time, the LogoCDT module will be modified to use the font "Arial Black", Plain, 72 pt.

ConstrainedPolygonDefect

mlthlschr commented 3 years ago

Maybe an idea could be to add a geometry validation with JTS. This validation logic would not be part of the core package but of a different one, e.g.utils. One could use the package, in case the validity can not be guaranteed, or omit the package entirely if the validity of the geometries can be guaranteed.

With that, you could keep the core package clean of external dependencies, but would offer some convenience functions for others who do not mind having some additional dependencies.

gwlucastrig commented 3 years ago

That's a good idea. And I'm pleased to see that you addressed the dependency issues. Also, I think JTS is a perfect choice for the task.

micycle1 commented 3 years ago

Sounds like IsSimpleOp?

A Geometry is simple if and only if the only self-intersections are at boundary points.

Another idea: rather than using such a technique to reject inputs (validation logic), perhaps degenerate polygon constraints could be fixed with JTS' new GeometryFixer (see here) and then processed. Alternatively, I believe .buffer(0) is a simple solution to fix problems like the one in this issue.

gwlucastrig commented 3 years ago

Thanks. I just read Martin Davis' discussion from the link you provided for Fixing Invalid Geometry with HTS It's great to see that they provide that function, since I've needed something like it more times than I can count.

While I wouldn't want to give Tinfour an additional external dependency on JTS, most of the applications I've written that use Tinfour also happen to use JTS. So it would be a good fit.

nicolas-f commented 2 years ago

Hi, Maybe its the same issue. I've prepared a specific unit test for this here:

https://github.com/nicolas-f/Tinfour/blob/issue_constraint/core/src/test/java/org/tinfour/utils/TriangleRegressionConstraintTest.java

gwlucastrig commented 2 years ago

Thanks. I will look at this and incorporate it into the test suite this weekend.