Implement ability to create contours from Delaunay Triangulation

[gwlucastrig]

I am developing a capability to create contours from Delaunay Triangulations. The end goal would be to create both isoline features and nested polygon features based that could be used to represent analysis products from Tinfour applications.

I welcome suggestions for features, API elements, or general approach.

The algorithm I am using is similar to the "meandering triangles algorithm". The contours would be developed directly from the triangulation (rather than using an intermediate step of creating a grid). The requirements for the implementation are complicated somewhat in that I wish to handle the special case where contours pass exactly through vertices.

One use of the contouring feature would be to make it an output option the Simple Volumetric Model (SVM). I've attached a picture of my work so far (created from data for The Lake of the Arbuckles in Oklahoma). The picture was created from a sample of about 100 thousand soundings. The contouring logic required about 0.23 seconds to complete.

[gwlucastrig]

I could use help on this project in two regards.

First, I would like SVM to be able to output graphical representations of the data it analyzes. To that end, I would like to provide a convenient way to specify color. Is anyone familiar with open standards for palettes? Could you recommend a format for TInfour to support? I'd like something small and manageable. For example, the SLD specification used in GeoServer would be too elaborate for a niche implementation such as the Simple Volumetric Model.

Second, I would like SVM to be able to write Shapefile output. Would anyone be interested in writing one? Again, Tinfour is a small project and I want to minimize external dependencies. Also, because Tinfour is not a dedicated GIS project, only a very basic Shapefile writer implementation would be required. For example, the implementation wouldn't have to include the ability to write a ".prj" file (it would simply copy the existing .prj from the input Shapefiles). Also, I'd like to see an implementation consistent with the ShapefileReader class in the Tinfour SVM module.

Finally, this would be my first time accepting major code contributions from other developers for Tinfour. So I'm sure there will be a few "bumps in the road" in making that happen. So, if you do take this on, I thank you in advance for your patience.

[gwlucastrig]

Conventional contouring applications often take a two-step process in which they build a raster (grid) from the Delaunay Triangulation and then construct the contours over the grid. One of the attractions of that process is that it is much easier to manipulate a grid of data points than a triangulated mesh. In particular, contour building implementations often require some kind of data-smoothing to reduce the complexity of the contours. In a grid, this smoothing is easily accomplished using a convolution filter (a low-pass filter) which blends the values in each raster cell with those of its neighbors.

So, the question comes up whether the Tinfour approach of building contours directly from the triangulation would be able to support smoothing. Tonight I implemented a smoothing filter that took advantage of the various features of the Tinfour API. The implementation took me just over an hour (though I need to clean up the code and add Javadoc). To see the effect, please compare the results below with those of the image in the original post (above). Run time was approximate 0.75 seconds.

[gwlucastrig]

I have posted the work-in-progress version of the contouring logic to the Tinfour project code page. The contouring implementation is in the core module, package org.tinfour.contour.

Currently, I have completed the generation of contour line features and am working on the creation of polygon features.

The code is currently in an untested state. If you come up with test implementations or results, I'd be grateful to hear about them.

[gwlucastrig]

I have completed the initial implementation of the polygon-building logic in support of contour-regions. Latest version of code is now posted.

The code is still largely untested. I am currently writing unit tests for the contour builder.

[gwlucastrig]

An example image of the Lake of the Arbuckles with the color-filled contour regions is shown below.

[gwlucastrig]

I have added an example application to the demo module to show how to use the contour-related API elements. The class org.tinfour.demo.examples.ExampleContour creates a TIN from a regular grid of sample points and generates contours and contour regions. It also includes example code showing how to plot the contour results. The input grid is given in text form:

static final String[] input = { "4 4 4 4 4 4 3 3 3", "4 4 4 4 4 4 3 3 3", "4 4 4 0 4 4 4 4 4", "4 4 0 0 4 4 4 4 4", "4 4 4 4 4 4 4 4 4", "2 2 2 2 2 2 2 2 2", "2 2 2 2 2 2 2 2 2", "2 2 2 2 2 2 2 2 2", "2 2 2 2 2 2 2 2 2", "0 0 0 0 0 0 0 0 0", "2 2 0 0 0 2 0 0 0", "2 2 0 0 0 0 0 0 0"};

Contours are specified for the values 1.0 and 3.0. The results are shown in the image shown below:

[gwlucastrig]

The contouring logic is now integrated into the Simple Volumetric Model (SVM) model to support an optional output of an graphic showing the lake or reservoir contours and color-filled regions. These features were included in the standard distribution starting with Tinfour version 2.1.2 which was released today (19 Aug 2019).

Future work will include the ability to output the data in the form of Shapefiles. The Tinfour contour and region-building logic already implements the ability to handle nested (or embedded) areas in a manner consistent with the way that they are used is Shapefiles. So the remaining challenge is to create an API for writing Shapefiles (without introducing new dependencies to other projects). I am still looking for help with this issue if somebody finds it interesting.

[gwlucastrig]

The contouring was improved substantially as part of Issue 66. Work on the Shapefile storage API is still pending.

[gwlucastrig]

Tinfour is not a Geographic Information System (GIS), but it does implement a few GIS-related utilities for obtaining test data. In some cases, it implements utilities for writing output data that can be used by GIS systems. I am working on the ability to write contour data to shapefiles. I'm making some progress and should post new code in a week or so.

In the mean time, I've attached a picture from some early results.

[gwlucastrig]

The ability to create contours and, optionally, write them to shapefiles is now complete.

Addressing this issue has been a long and challenging process. Thank you for your patience and support.