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

RFC: Proposal to Implement Limited Voronoi Diagram Class #38

Closed gwlucastrig closed 6 years ago

gwlucastrig commented 6 years ago

I have a need for a Voronoi Diagram capability and am planning to implement a new class to construct Voronoi Diagram structures from an instance of a Tinfour IncrementalTin. The IncrementalTin classes implement Delaunay Triangulations and can be used to produce Voronoi diagrams in a relatively direct manner. The proposed class would accept a populated IncrementalTin as input and would use it to build a Voronoi diagram.

I am seeking comments from potential users who have features they would like to see supported or have suggestions regarding the implementation.

The preliminary name for the new class is "LimitedVoronoi". The implementation will be limited in two senses.

First off, it will be limited to a finite domain. I do not intend to attempt to make the implementation cover an infinite plane as a true Voronoi would. The calling routine will have the option of either using the bounds of the IncrementalTin or of supplying its own. The domain of the resulting structure will always be a rectangular area.

Second, the LimitedVoronoi class will be limited in the range of functions it offers. Some of the more difficult operations will be left for future development. Most notably, it will not support an "add vertex" or "remove vertex" operation. These may be added in the future, but will not be part of the initial release.

Please feel free to post to this issue if you have relevant comments.

Thanks.

gwlucastrig commented 6 years ago

I have posted an experimental version of classes that build and support Voronoi Diagrams. The rendering tool is not quite ready, but I hope to post it within the next week or so.

Additional functionality will be added as I receive recommendations from prospective users.

The new classes are in the package tinfour.voronoi

gwlucastrig commented 6 years ago

In connection with the work on Voronoi Diagrams, I have posted a new class which implements a graph-coloring algorithm. The class is located in the utils package and is named VertexColorizerKempe6.java. It is based on Kempe's 6-color algorithm.

I am still adding new functionality to the LimitedVoronoi class and will be posting more updates over the next few weeks. I also plan on posting a rendering utility.

The picture below shows the results of a Voronoi Diagram with colors assigned by the new VertexColorizerKempe6 class.

voronoidiagramsixcolors

gwlucastrig commented 6 years ago

I added a new class for rendering Voronoi Diagrams. It's called LimitedVoronoiDrawingUtility.

I have tested the LimitedVoronoi class with several hundred thousand test runs and it seems to be working properly.

I paln to close this issue in the near future.

gwlucastrig commented 6 years ago

I am now integrating an improved clipping algorithm into the construction of the Voronoi Diagram structure. This feature will allow a calling application to specify an explicit set of bounds for limiting the domain of the Voronoi structure. It is the final feature planned for this implementation effort. Once it is complete I will close out this issue.

Future work will be conducted as users identify new features or new ways of using the Tinfour Voronoi classes.

gwlucastrig commented 6 years ago

Preliminary implementation is complete. Future work will follow if bugs are detected.

I have also added an integrity check class for testing purposes. The function of this class is analogous to that of the incremental TIN implementations.

This tracker issue is now closed.