TransWikia.com

Using GRASS v.delaunay with QGIS results with gaps in triangulation

Geographic Information Systems Asked by Lars81 on July 26, 2021

When I use the GRASS v.delaunay algortithm in QGIS 3.18 on my dataset the output has gaps in it. But when I use the QGIS delaunay algorithm there are no problems and all is triangulated.

v.delaunay output

qgis delaunay output

The input that I use is a pointlayer with xyz geometry and the algorithms are called on from the processing toolbox. The settings for v.delaunay are shown below.

v.delaunay settings

And these are the warnings.

v.delaunay warnings

Does anybody know how to solve this?

2 Answers

The problems with the gaps within the triangulation with v.delaunay is solved with the solution as provided by @Babel. But along the borders there were points in this dataset that were left out of the triangulation and lines (brown) ended up not as expected (blue).output_vs_expected

The following steps helped me to get the output I want.

  1. remove duplicate geometries and add a field with the z value. Formula = z ($geometry)
  2. create new field in step 1 with @Babels's formula

if ( length ( make_line( $geometry, array_first ( overlay_nearest( @layer, $geometry ) ) ) ) > 0.001, 'true', if ( array_first ( overlay_nearest ( @layer, $id ) )< $id, 'true', 'false' ) )

  1. select by expression with expression "fieldname" = 'True'

  2. v.delaunay with step 3 as input and use selected features only

This gives me a triangulation that filled the gaps on the inside, but with unexpected sides. output step 4

To fix these:

  1. minimum bounding geometry with step 1 as input. Type geometry = convex hull

  2. buffer step 5, in this case I used a 1 meter buffer

  3. extract vertices of step 6

  4. join by nearest step 7 as first input and step 1 as second

  5. set z-value step 8, get z value from the field made in step 1

  6. merge vector layers from step 1 and step 9

  7. repeat step 2,3 and 4

  8. merge vectorlayers step 4 and 11

  9. remove duplicate geometries of step 12

  10. extract by location input is step 13 extract objects within step 5. This gives the output I expected.

output step 14

Correct answer by Lars81 on July 26, 2021

What the problem was: duplicate points

After inspecting your data, I could identify the problem: you have a lot of duplicate points as well as a few points that are "almost" duplicates (extremely close to each other). From originally 954 features in the point layer you provided, only 229 (ca. 24%) are really unique points (thus not duplicates or quasi-duplicates).

You can see this: set your layer rendering style to Point Cluster (see screenshots 2 and 3 below), than you see how many points are in the same place or extremely close together.

This causes the problem with v.delaunay (and, by the way, similarily with v.voronoi as well). Polygons would get extremely small. It seems that the native QGIS algorithm for Delaunay Triangulation (and Voronoi polygons as well) tolerates this, whereas the GRASS tool does not.

How to solve the problem: remove duplicates and very close points

  1. Remove duplicate points: Menu Processing / Tollbox / Delete duplicate geometries. This reduces your point layer from originally 954 features down to 243 features.

  2. Remove the points that are "almost" duplicates (extremely close). I created a new attribute field with field calculator to measure the distance from each point to it's next neighbor. It keeps points that have a certain minimum distance from the next neighbor. For points extremely close to it's next neighbor, it keeps only the one with the lower $id value. This is the expression that returns true for points to keep and false for all points to ignore - minimum distance to keep points set to 0.001 (this marks another 14 features to be ignored):

if (
    length (
        make_line(
            $geometry, 
            array_first (
                overlay_nearest( 
                    @layer, 
                    $geometry
                )
            )
        )
    ) > 0.001,
    'true',
    if (
        array_first (
            overlay_nearest (
                @layer,
                $id
            )
        )< $id,
        'true',
        'false'
    )
)
  1. Use select by expression to select those features with attribute-value of the field created in step 2 = 'true'. Calculation will be done for only 229 features out of 954 as you originally have.

  2. Now run v.delaunay and check the box next to Selected features only

Screenshot 1: v.delaunay with default settings and checked box Selected features only (red frame) results in the orange output. Overlayed, semi-transparent polygons created with the same tool, based on the original points you provided for comarison: the "holes" are now filled, the same way as with native QGIS Delaunay algorithm:

enter image description here

Screenshot 2: Your original point layer, containing 954 features, many of them duplicates as you can see when rendering with Point Cluster:

enter image description here

Screenshot 3: after removing duplicates (step 1), you're left with 243 features, some of them de-facto duplicates as the next screenshot shows. They appear exactly where your problems are:

enter image description here

Screenshot 4: There are still areas left where you have extremely small, obtuse angled triangles. Reason is that you have points that are almost, but not exactly on a line - see on the next image (rotated, to be better visible). In QGIS native output, the area is calculated as 0, in v.delaunay output, it gives a value > 0. So it least in my understanding, v.delaunay is more correct: enter image description here

Answered by Babel on July 26, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP