How can I obtain Voronoi diagram on a Red Blood Cell using XYZ coordinate of points and face connectivity data from Delaunay triangulation?

Question

UPDATE (1/12/14): Dear all, I have been trying all I can to code the algorithm by Dr Darren below in MATLAB but I am yet to succeed with it. I humbly request that a good Samaritan should kindly help me with the code and share the m-file. Thanks once again.

---

I intend to obtain Voronoi diagram on RBC using MATLAB/FORTRAN. I need the following specific information.

1. Voronoi vertex using the normal vector for each Delaunay triangle;
2. Order of each Voronoi polygon;
3. Voronoi vertex lists that define the Voronoi polygons;
4. Component of normals on the Voronoi polygons;
5. Areas of the Voronoi polygons;
6. Centroids of the Voronoi polygons;
7. Finally, plot Voronoi polygons using PATCH;

Please find link to corresponding text files RBC_1 which contain XYZ node coordinates on the RBC and RBC_2 which contain face connectivity data from Delaunay triangulation (RBC_1 and RBC_2 are in Zip file).

https://www.dropbox.com/s/slan053xbr2e864/RBC.zip?dl=0

I have tried to follow the work of John Burkardt for unit sphere: http://people.sc.fsu.edu/~jburkardt/m_src/sphere_voronoi/sphere_voronoi.html but its not working.

Thank you in advance.

N.B Any comment and advice will be highly appreciated.

Answer 1

Looking at your files, you have a set of points P in R^3 and a (2-manifold) surface triangulation T of your geometry:

This can easily be turned into a surface voronoi complex V by noting that the voronoi complex is dual to the underlying triangulation T. This means the following:

• for each primary edge Ei in T there is a dual edge Vi in the voronoi complex.
• for each primary node Pi in P there is a dual cell Vc in the voronoi complex.

Each dual edge in the voronoi complex spans between the centre of the circumballs of the triangles that are adjacent to the associated primary edge in the triangulation.

This duality implies the following algorithm for the construction of the voronoi complex:

calculate circumcentres CC for all triangles in T

for (all edges Ei in T)
    find triangles [Ti,Tj] in T adjacent to edge Ei
    push voronoi edge Vi between centres [CC(Ti),CC(Tj)]
    associate edge Vi with voronoi cells associated with edge endpoints [Pi,Pj] in Ei
endfor

Putting this into practice gives the following voronoi complex for your mesh:

As others have pointed out, your question is very extensive, and I won't try to answer everything here.

---

I have made a set of dual mesh construction routines available here. Nonetheless, based on the slew of emails that you've bombarded me with over the weekend, let me make a few remarks: (i) you should invest some effort to understand a bit of computational geometry -- don't just blindly use the code provided, and (ii) if you do use the code provided, ensure that you make an effort to reference it appropriately.