* DelaunayAndVoronoi ***

Description:

This is an implementation of Delaunay triangulation and Voronoi diagram on the sphere. The purpose of this re-implementation is for considering the efficient update when all the data points can move without construct from the scratch. It originates from the need of space tessellation in my numerical scheme (TTS) for solving linear advection problem.

All the codes are written in Fortran 95/2003. High degree of modularization is realized. The internal data structure is completely hidden from users.

Directory structure:

The program is made up by several modules in "Core" and "Util". In "UnitTest", there are some tests can be run. The scripts in "PlotTool" can be used to show the output graphically.

Dependencies:

The NetCDF library is needed for outputing results, and NCL is incorporated in visualization.

Usage:

DelaunayAndVoronoi is highly modularized. The use of it is very easy. In some Fortran program:

  ...
  use SampleManager
  use DelaunayAndVoronoi
  ...
  call SampleManager_Init(<number of samples>)
  call SampleManager_Set(<sample lon>, <sample lat>)
  call DelaunayAndVoronoi_LinkSample
  call ConstructDelaunayTriangulation
  call ExtractVoronoiDiagram
  call DelaunayAndVoronoi_Output(<file name>)

The program has been compiled using "ifort" and "gfortran", you can change the compiler in "Makefile.basic" for FC macro.

To visualize the results, use the scripts in "PlotTool":

  cd <directory where results are>
  <relative path to "PlotTool">/PlotDTVD.sh

And following some questions, it will generate PDF file(s) of the Delaunay triangulation and Voronoi diagram projected on the sphere.

Current Development:

Finished:

• Only sphere manifold is considered (for atmospheric modelling).
• Delaunay triangulation and its dual Voronoi diagram are finished.

To be finished:

• Optimize the resulting Voronoi diagram to avoid short edges.
• Incoporate some efficient update methods to avoid intensive reconstruction.

  ---