Delaunay Triangulation only for edges below certain length

Hello, having tried to find out if that works for quite some time, I thought I'll try here.

So basically I am performing this triangulation on a network and at the edges of the image, there are points connected by the triangulation that should not be, and I would like to sort them out by giving a constraint on the maximum edge length of the triangles. Is that possible?

Thanks for any help!

[darova]

attach the picture

Answer 1

[John D'Errico]

Is it possible? Of course. Compute the edge lengths. Decide which triangle have a longer edge length than what you want.

What will you do with that information? If the anser is you want the Delaunay triangulation to NOT create those triangles, and have it be smart enough to do that, think again. In context of a Delaunay triangulation, that is not an option you have. In fact, there is relatively little in context of a Delaunay triangulation you can do.

A Delaunay triangulation forms a triangulation of a region, such that the boundary of the region will be the convex hull of the data.

Given that, IF the region you want to see triangulated is not a convex region, then expect problems! You will get those long thin triangles. It will fill the gaps around the perimeter of your region where the data is NOT in fact convex.

Is your real question, can you create a triangulation that does NOT fill those gaps, thus not creating long, thin triangles around the perimeter? To some extent, yes, you do have an alternative - an alpha shape. An alpha shape starts with a Delaunay triangulation, then effectively rolls a ball (or sphere in 3-d) of radius alpha around the perimeter. Where the ball can penetrate a facet of the triangulation far enough to touch an interior node, it erodes those simplexes away. Depending on the options chosen, you can allow the code to erode interior holes or not.

xy = rand(100,2);

S = alphaShape(xy)
S = 
  alphaShape with properties:

             Points: [100×2 double]
              Alpha: 0.0949990743504186
      HoleThreshold: 0
    RegionThreshold: 0
    
plot(S)

The code chose Alpha as 0.094999..., which is pretty small in general. I'd guess an alpha radius of vaguely 1/2 to 2 would be not be unreasonable, since the data is generated from uniform data in the unit square.

S.Alpha = .5
S = 
  alphaShape with properties:

             Points: [100×2 double]
              Alpha: 0.5
      HoleThreshold: 0
    RegionThreshold: 0
    
plot(S)

So where the alpha ball can penetrate a perimeter facet of the triangulation far enough to TOUCH an internal node, the triangle will be eroded, thus deleted from what you get.

If you know in advance the value of alpha you might want to use, then pass it in directly when you create the shape. Thus use it as:

S = alphaShape(xy,0.5);

I generally find an alpha shape to be moderately insensitive to alpha radius as long as you don't go too small. Make the radius a little bit larger, and you will add a few moderately thin triangles. Go too large, and it starts to turn into the convex hull. Note that an alpha radius of inf will generally be equivalent to the Delaunay triangulation itself.

Finally, you do get two parameters to control hole and region thresholds. Without making this a complete tutorial on the idea, just read the docs for alphaShape. Play with it. Learn how to use the tool.

[F Sp]

Thank you a lot for that informative answer. Having tried alphaShape without success now, I guess, I'm just keeping the delaunay. I found a way to extract the long edges, it just doesn't work with the visualisation, but that's not a big issue.

[John D'Errico]

I've not seen your data, so I cannot know why you were unsuccessful. I might hazard many possible guesses.

1. Your data does not live in a domain where x and y are scaled to have the same units. Remember that an alpha shape uses a CIRCULAR ball. So the variables need to have the same units, or you need to scale them so they are consistent in magnitude. An alpha shape will fail otherwise.
2. Your data may be too non-uniform. That is, some parts of the perimeter may have large gaps in them. This is a common problem. The answer is to get better data, sampling the surface of the point cloud as uniformly as possible. Remember that a gap in the data will be perceived as a hole that is NOT part of the domain, since then it will have large triangles spanning the hole. An alpha shape is explicitly designed to erode those very holes.
3. Your data may be non-uniform in the variablesm sampled too sparsely at one end of the domain than another. This is just a variation of #2 above, and bad for the same reason.
4. The point cloud you need to tessellate may have sharp corners, especilly sharp internal corners. A ball of radius alpha will not fit well into such a corner, but if you make alpha too small so it does, then things fail for other obvious reasons.

A Delaunay triangulation has many good properties, and it is easy to build, use, and work with. Once you go past that point however, things get more complicated, and you often need to start to write your own code. Learning how to use and write my own computational geometry tools is a good thing, at least in my opinion. Of course, that was a step I took many years ago, so to me, it seems like a small step when viewed from a distance. :)

[F Sp]

Okay good to know! As it is not my biggest priority to get deeper into that matter, for now I think I'm fine with leaving it the way it is, but thank you neverthelesse for the effort!!