Is there a way to prevent or circumvent the formation of long edges in a Deluanay Triangulation?

1 次查看（过去 30 天）
AJP
AJP 2011-6-2
I am finding that the delaunay() function causes long edges to be formed near to the boundries of my triangulation.
These are undesirable and are causing trouble for later computations.
Is there any way to prevent them forming or, failing that, detect them and make these edges reference nearer end points?

请先登录，再回答此问题。

回答（2 个）

John D'Errico
John D'Errico 2011-6-2
Since a delaunay triangulation is necessarily convex, exactly how do you intend to triangulate the domain without long edges? TRY IT! Remember, you MUST have a convex result.
You can use an alpha shape, which starts from a delaunay triangulation, and erodes some of the parts.
  3 个评论
显示 1更早的评论
John D'Errico
John D'Errico 2011-6-2
The delaunay triangulation does compute a convex result. The fact is, you cannot do better around the edges with any triangulation. For example...
>> X = rand(10,2)
X =
0.81472 0.15761
0.90579 0.97059
0.12699 0.95717
0.91338 0.48538
0.63236 0.80028
0.09754 0.14189
0.2785 0.42176
0.54688 0.91574
0.95751 0.79221
0.96489 0.95949
>> tri = delaunayn(X)
tri =
2 3 8
8 5 2
10 2 9
2 5 9
6 1 7
7 3 6
7 8 3
5 8 7
4 9 5
4 7 1
5 7 4
>> trimesh(tri,X(:,1),X(:,2))
There are long triangles around the edges. No alternative triangulation exists that does not do the same, yet is still convex and triangulates that set of points! It is the requirement of convexity that causes your problem.
AJP
AJP 2011-6-12
I understand you John, I agree that these sorts of long edges are unavoidable. This is not quite my problem though.
Let me show you what I mean. First try this set of points and triangulation.
x=[17.3138
17.7551
18.2927
18.9796
19.7561
20.2041
21.2195
21.4286
22.6531
22.6829
23.8776
24.1463
25.1020
25.6098
26.3265
27.0732
27.5510
28.5366
28.7755
30.0000
30.0000
30.0000
30.0000
20.2041
21.4286
22.6531
23.8776
23.8776
25.1020
25.1020
26.3265
26.3265
27.5510
27.5510
28.7755
28.7755]
y=[21.4800
21.4800
21.5547
21.4800
21.6537
21.4800
21.7398
21.4800
21.4800
21.8130
21.4800
21.8730
21.4800
21.9197
21.4800
21.9532
21.4800
21.9733
21.4800
21.4800
21.6467
21.8133
21.9800
21.6467
21.6467
21.6467
21.6467
21.8133
21.6467
21.8133
21.6467
21.8133
21.6467
21.8133
21.6467
21.8133]
tri=[28 10 27
10 7 25
27 10 26
2 4 3
11 12 27
15 31 14
12 11 13
18 36 23
13 29 12
36 22 23
3 1 2
4 6 5
26 25 9
9 11 27
8 25 7
9 25 8
5 3 4
27 12 28
6 24 5
6 8 7
24 6 7
28 12 10
24 7 5
27 26 9
10 25 26
14 29 13
19 20 35
14 30 29
12 29 30
30 14 12
16 32 31
16 14 32
34 18 16
17 18 33
32 14 31
18 34 33
16 31 15
36 21 22
36 35 21
19 18 17
34 16 33
21 35 20
36 18 35
14 13 15
16 15 17
16 17 33
18 19 35]
triplot(tri,x,y);hold on;plot(x,y,'ro')
Notice that in some areas the triangulated edges have formed between points that are far from each other, as opposed to what I expected which was edges forming to between more-or-less nearest neighbour points
Now I add in one or two a couple of points around the upper boundary and slightly shift them so they all line up into neat columns. The new values of x,y and tri are:
x=[ 17.3090
17.7551
17.7551
18.9796
18.9796
20.2041
20.2041
21.4286
21.4286
22.6531
22.6531
23.8776
23.8776
25.1020
25.1020
26.3265
26.3265
27.5510
27.5510
28.7755
28.7755
30.0000
30.0000
30.0000
30.0000
20.2041
21.4286
22.6531
23.8776
23.8776
25.1020
25.1020
26.3265
26.3265
27.5510
27.5510
28.7755
28.7755]
y=[ 21.4800
21.4800
21.5151
21.4800
21.6028
21.4800
21.6814
21.4800
21.7511
21.4800
21.8116
21.4800
21.8629
21.4800
21.9050
21.4800
21.9378
21.4800
21.9612
21.4800
21.9753
21.4800
21.6467
21.8133
21.9800
21.6467
21.6467
21.6467
21.6467
21.8133
21.6467
21.8133
21.6467
21.8133
21.6467
21.8133
21.6467
21.8133]
tri=[31 29 14
3 4 5
4 6 5
30 29 32
19 36 38
28 10 12
33 34 31
3 1 2
3 2 4
26 6 8
29 28 12
31 14 33
26 8 27
5 26 7
5 6 26
26 27 7
8 10 27
27 9 7
27 28 9
11 30 13
11 28 29
9 28 11
27 10 28
14 29 12
30 11 29
15 32 34
13 30 32
32 15 13
15 34 17
35 18 20
34 36 17
38 24 21
38 36 35
19 17 36
37 38 35
21 19 38
34 35 36
20 22 23
21 24 25
38 23 24
32 31 34
32 29 31
16 33 14
35 34 33
33 16 35
16 18 35
35 20 37
23 37 20
23 38 37]
triplot(tri,x,y);hold on;plot(x,y,'ro')
Notice now that the triangulation is nicely ordered.
I don't really understand whay this is happening, but at least I got round it.
Anyway, thanks for your help.

请先登录，再进行评论。

Wolfgang Schwanghart
Hi AJP,
without knowing what exactly yoou want to do, I like to link to a tool that was extremely helful to me.
http://www.mathworks.com/matlabcentral/fileexchange/6243-hullfit
Perhaps it does what you need.
Cheers, W.
  1 个评论
AJP
AJP 2011-6-2
Looks very interesting, thank you for posting.
This function may perhaps problematic in my current project though as I need to leave my convhull operations to occur unattended in a time loop with dynamically changing geometry. Therefore the requirement of an empirical "length factor" in this code might be somewhat limiting. I'd have to experiment and see what I can do with it!
But thank you very much for this - it is sure to come in very handy for all sorts of other problems.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Delaunay Triangulation 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by