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

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]

What later computations are long edges undesirable for? Maybe you could focus that computation (per John's response)?

Answer 1

[John D'Errico]

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]

Thanks for your input John.

As you may realise by now I'm not very knowledgable of this field!

I think a lack of clarity on my part has mislead you as to my exact problem. The long edges aren't simply the result of having an outer point a long way from its neighbours, but rather becuase it seems that triangulation algorithm does not always compute the shortest edge connections available.

I have looked into using the "ashape" and/or "distmesh" libraries, which are clearly excellent tools, but concluded they were probably a bit too powerful (and computationally expensive) for my purposes.

I have found that defining the outer points slightly differently, essentially shifting them around on a known perimeter so that they align better with the inner points, has done the trick and avoided generation of the long edges.

[John D'Errico]

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]

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.

Answer 2

[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.

[AJP]

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.