This is one of those questions with a somewhat narrow perspective.    Still, however, the underlying problem of approximating a surface with a Delaunay triangulation or a Dirichlet tessellation (tessellating a region of space with Voronoi regions of points is named after Dirichlet) is important and well-worth considering.

A good starting point in looking for an answer to your question is to consider

H.S. Muddana, Integrated biomechanical model of cells embedded in extracellular matrix, M.S. thesis, Texas A&M University, 2006:

http://research.cs.tamu.edu/bnl/papers/muddana.thesis06.pdf

See, for example, the introduction to Delaunay triangulation and its generalization, starting on page 26 (bottom of the page).    See the discussion about mesh refinement, starting on page 48.

This is one of those questions with a somewhat narrow perspective.    Still, however, the underlying problem of approximating a surface with a Delaunay triangulation or a Dirichlet tessellation (tessellating a region of space with Voronoi regions of points is named after Dirichlet) is important and well-worth considering.

A good starting point in looking for an answer to your question is to consider

H.S. Muddana, Integrated biomechanical model of cells embedded in extracellular matrix, M.S. thesis, Texas A&M University, 2006:

http://research.cs.tamu.edu/bnl/papers/muddana.thesis06.pdf

See, for example, the introduction to Delaunay triangulation and its generalization, starting on page 26 (bottom of the page).    See the discussion about mesh refinement, starting on page 48.

Thank you for your comment Prof.

I will appreciate further comments and advice please.

I am not exactly sure what you want to do, but it seems that the first step would be to find the list of neighbouring face elements for each vertex. This is an easy task: you just have to ask each element whether it contains the vertex or not. This also gives you the number of neighbouring elements and therefore the order of the polygon.

Additionally you need a list of all neighbouring vertices for any vertex. Also this is simple: just go through the list of neighbouring elements of a vertex and ask for the other two vertices; those are direct neighbours of your initial vertex.

From this information you can work out everything in a relatively straightforward way.

I am not sure if the Voronoi diagram on a Delaunay triangulation (i.e. a 2D surface) in 3D is properly defined. Unless you have a flat surface the dual of any triangulation will be different from the initial surface. Furthermore, polygons are considered to be planar (otherwise there is no proper description yet what surface a polygon describes). If your Delaunay triangulation is not planar there is no guarantee that you can extract polygons for the Voronoi diagram. As far as I understand the Voronoi diagram is only properly defined for Delaunay triangulations in 2D and Delaunay tetrahedrizations in 3D. For 2D structures in 3D you can take the ideas from the Voronoi diagram and introduce your own tessellation which will probably be specific to you problem.

Thank you for your comment.

@ Dr Timm, you are highly appreciated. My current code can determine the number of neighbouring elements and therefore the order of the polygon. But my challenge is my inability to code algorithm to determine the voronoi polygon area, centroid and components of normal on the polygon surface. My code gave an obviously wrong answer because the voronoi polygon area and centroid I obtained are either ZERO, NEGATIVE NUMBERS or NaN.

@Dr Simon. Thank you for your comment. From my observation, it is possible to obtain surface tessellation of a 2D surface embedded in a 3D space (i.e. a closed 2-manifold). Please see link below for a answer provided by Dr Darren Engwirda on Stack Exchange (I also extracted the image here for reference).

Thank you once again.

http://stackoverflow.com/questions/27150786/how-can-i-obtain-voronoi-diagram-on-a-red-blood-cell-using-xyz-coordinate-of-poi