Please tell about Delaunay triangulation

The output appearing as triangular facets instead of rounded surface in Delaunay triangulation .how to find the length of the triangular facet edges ?

Answer 1

[Henry Ukwu]

DT = delaunay (P)

DT = delaunay (x, y)

DT = delaunay (x, y, z)

[Rashi Mehrotra]

Yes, I know this from mathwork my question is using Delaunay triangulation the output appears as triangular facets instead of rounded surface in , also how to find the length of the triangular facet edges ?

Answer 2

[John D'Errico]

In three dimensions, a triangulation will be composed of tetrahedrae, or we could call them 4-simplexes. So each piece will have 4 vertices. On the free surface or boundary surface of that tessellation, we will have triangular facets, so what you would see if you plotted just the convex hull.

A set of 6 points will suffice as an example.

xyz = rand(6,3)
xyz =
      0.10069      0.26591      0.21099
      0.45641      0.53456      0.46896
      0.86343      0.98294      0.11778
      0.31752      0.27328     0.074489
      0.38894      0.44849      0.23297
      0.10141      0.79623     0.062665

We can triangulate this. We could use the older tool, delaunayn, which just returns the connectivity list that defines the 4-simplexes. I prefer a tool that keeps it all together. For example, there are two such tools:

T = DelaunayTri(xyz)
T = 
  DelaunayTri with properties:
                X: [6×3 double]
    Triangulation: [6×4 double]
      Constraints: []

or the similar:

T = delaunayTriangulation(xyz)
T = 
  delaunayTriangulation with properties:
              Points: [6×3 double]
    ConnectivityList: [6×4 double]
         Constraints: []

So T.Points is the original list of points, and T.ConnectivityList describes the tetrahedral tessellation.

T.ConnectivityList
ans =
     3     6     4     5
     6     1     4     5
     1     2     4     5
     1     6     2     5
     2     3     4     5
     2     6     3     5

Got it? Now, what can we do with such a tessellation? Since T is a class, we can investigate what tools apply.

methods(T)

Methods for class delaunayTriangulation:

barycentricToCartesian  edgeAttachments         incenter                pointLocation           
cartesianToBarycentric  edges                   isConnected             size                    
circumcenter            faceNormal              isInterior              vertexAttachments       
convexHull              featureEdges            nearestNeighbor         vertexNormal            
delaunayTriangulation   freeBoundary            neighbors               voronoiDiagram          

Does edges seem useful? TRY IT!

>> E = edges(T)
E =
     1     2
     1     4
     1     5
     1     6
     2     3
     2     4
     2     5
     2     6
     3     4
     3     5
     3     6
     4     5
     4     6
     5     6
     
size(E)
ans =
    14     2

So there are 6 tetrahedrae, with 14 edges in total. Of course many of those edges are shared between the tetrahedrae.

Anyway, we can compute the lengths of each edge simply enough, since the distance between two points is just the sum of squares of the differences in each dimension, and then you take the sqrt. So this line computes the Euclidean distances.

sqrt(sum((T.Points(E(:,1),:) - T.Points(E(:,2),:)).^2,2))
ans =
      0.51503
      0.25633
      0.34192
      0.55068
      0.70002
      0.49312
       0.2601
      0.59964
      0.89638
      0.72391
      0.78649
      0.24681
      0.56597
      0.48229

Those from the lengths of all 14 edges in the entire object. Some of those edges are in interior facets, and I think perhaps you wanted only the edges on the surface? If you wanted just the length of each edge on the free boundary (that is, the surface or the convex hull), then we would have started with the edges only from the freeBoundary.

facets = freeBoundary(T)
facets =
     1     2     6
     1     4     2
     1     6     4
     2     3     6
     2     4     3
     3     4     6

We can build the list of edges from the facets.

E = unique([facets(:,[1 2]);facets(:,[1 3]);facets(:,[2 3])],'rows')
E =
     1     2
     1     4
     1     6
     2     3
     2     4
     2     6
     3     4
     3     6
     4     2
     4     3
     4     6
     6     4
>> size(E)
ans =
    12     2

So, because the point set was small, there were only two interior edges. 12 edges lie on the surface, and the lengths of those edges are now:

edgelengths = sqrt(sum((T.Points(E(:,1),:) - T.Points(E(:,2),:)).^2,2));

Once you see how those triangulations work, and what they return, computing anything you want is really pretty simple. Look at the methods they provide. The names suggest what they will do.