# Please tell about Delaunay triangulation

1 view (last 30 days)
Rashi Mehrotra on 1 Oct 2020
Edited: John D'Errico on 1 Oct 2020
The output appearing as triangular facets instead of rounded surface in Delaunay triangulation .how to find the length of the triangular facet edges ?
##### 0 CommentsShowHide -1 older comments

Sign in to comment.

### Answers (2)

Henry Ukwu on 1 Oct 2020
##### 1 CommentShowHide None
Rashi Mehrotra on 1 Oct 2020
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 ?

Sign in to comment.

John D'Errico on 1 Oct 2020
Edited: John D'Errico on 1 Oct 2020
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.
##### 0 CommentsShowHide -1 older comments

Sign in to comment.

### Categories

Find more on Delaunay Triangulation in Help Center and File Exchange

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!