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

3 views (last 30 days)
AJP on 2 Jun 2011
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?
Sean de Wolski on 2 Jun 2011
What later computations are long edges undesirable for? Maybe you could focus that computation (per John's response)?

John D'Errico on 2 Jun 2011
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.
AJP on 12 Jun 2011
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.

Wolfgang Schwanghart on 2 Jun 2011
Hi AJP,
without knowing what exactly yoou want to do, I like to link to a tool that was extremely helful to me.
Perhaps it does what you need.
Cheers, W.
AJP on 2 Jun 2011
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.