I've been working Delaunay triangulation on a set of random points inside a group of mostly linear areas (in fact, buffers around rivers).

The problem is that while the triangulation works correctly inside these areas, it also produce a lot of triangles between the areas. Expectedly.

Now, I need to delete all this extra data manually.

Does anyone think it would be possible to define a threshold, a maximum distance, for the Delaunay algorithm?

That way, it would only produce triangles inside each area.

Any idea how I could do that? I'm using QGIS or GRASS.

  • If R is an option you can use the library Triangle in package RTriangle, and you can specify minimum sizes +/- minimum angles. Happy to show usage if you provide example data. But otherwise, can't you calculate these metrics on each triangle and filter them? – mdsumner Nov 19 '16 at 21:27

GRASS command v.delaunaycan be configured with v.in.ogr min area to define a minimum area for each triangle. But, could be tricky, because the algorithm could generates small polygons out river area.

The easiest way is take buffer polygon (in your case) into account and execute an execute Select by location. You'll select only polygons inside your desire area, also you can set a ruleset for selection. After this, simply selecta Save As.../ Save only selected features.

Here a simple example using a line to define selection:


With a buffer zone, you need one more step. Take buffer polygon and apply an inverse buffer (Fixed distance buffer with negative distance values). Use second buffer to select Delaunay polygons (Black dashed area is second buffer):


  • That's an alternative way to get the same result, all in QGIS. I was looking for threshold and forgot about selecting. – gvanhavre Nov 20 '16 at 13:28

If I understood right what you want to do and if you can use OpenJUMP then perhaps the triangulation with constraints layer is usable.

Create a point layer and a polygon layer with the areas of interest

enter image description here

Use these settings

enter image description here

The result will look like this

enter image description here

  • OpenJUMP works just fine with the constraint. The resulting number of triangles is roughly the same as the manual method I've been using, but obviously faster. – gvanhavre Nov 20 '16 at 12:12

According to the manual, v.delunay has no maximum or minimum distance option. Thus, if you want to get only the triangles within a polygon vector map, you would have to remove the rest using either v.select or v.overlay (the later can be faster for larger datasets.

However, using the v.distance module, you can create lines between points within minimum and maximum distance thresholds. Where the lines form closed sets you can change the lines to boundaries and add a centroid to get a topological correct area. But please note, depending on you input points, the lines are not necessarily connected to triangles and neither to closed boundaries in all cases...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.