Delaunay triangulation improvements

[jpolchlo]

Previously, a custom implementation of the Delaunay triangulation algorithm was integrated into GeoTrellis, but this algorithm could fail in some simple cases. For instance, triangulating the set of points

val pts = for ( v <- 0.0 to 1.0 by 0.01 ) yield Point(v, v)

is likely to fail. This is through no fault of the algorithm, but rather, it is because the operators that test cocircularity/collinearity (herein called predicates) lacked the robustness to determine that the above point set is collinear. This lack of robustness can cause the triangulator to fail.

In response, the custom triangulator was scrapped in favor of the version contained in JTS. A problem that arises is that in cases where the custom implementation succeeds, it is faster than JTS, a gap which widens as the inputs increase in size. If one wishes for faster triangulations (or faster Voronoi diagrams or faster EuclideanDistanceTiles), this reliance on JTS is a problem.

This issue addresses the desire for fast but still correct Delaunay triangulations. What is required is for the predicates used in the triangulator to be replaced with fast, robust predicates. One example is Shewchuk's robust predicates, detailed here. At one time, these predicates were implemented in JTS, but abandoned in favor of a different approach (see this archived thread for more information).

Note that the most mature code for the custom triangulator can be found here. Note that before continuing development, a new unit test should be included to calculate the triangulation of pts given above.

[lossyrob]

We've integrated Shewchuk's and made our Delaunay implementation robust on the milestone/pointcloud branch; closing