Bug report #14513

Bad Interpolation TIN (displacement and hole) when too many points inside pixel...

Added by Olivier ATHIMON almost 9 years ago. Updated almost 6 years ago.

Status:Closed
Priority:Normal
Assignee:-
Category:Analysis library
Affected QGIS version:2.99(master) Regression?:No
Operating System: Easy fix?:No
Pull Request or Patch supplied:No Resolution:end of life
Crashes QGIS or corrupts data:No Copied to github as #:22486

Description

Hello,

I have got my problem with QGIS 2.12.x, 2.14.x, and QGIS 2.15.0 Master (installation OSGeo4W64) under Windows 64 bits...

The interpolation TIN with QGIS only (Menu Raster > Interpolation > Interpolation, and select a shapefile with points for the Interpolation TIN) give displacements and holes...

I suppose that the problem appear when we have too many points (the input) in a pixel (the output)... I don't know if this is the right reason...

To compare: the same shapefile with QGIS and : Processing > SAGA > Grid-Gridding > Triangulation give a nice interpolation TIN...

The problem of the interpolation TIN is maybe with the library GDAL (2.0.2) and/or QGIS...

To help to understand my problem, i join 3 pics (3 jpeg) and my data (in a archive .zip)

Thanks for all.
Olivier ATHIMON

Diapositive1.JPG - My parameters and results with my shapefile (74.2 KB) Olivier ATHIMON, 2016-03-16 10:47 AM

Diapositive2.JPG - The same shapefile (input) and results with QGIS/RASTER/Interpolation TIN, and SAGA/Grid-Gridding/Triangulation (115 KB) Olivier ATHIMON, 2016-03-16 10:47 AM

Diapositive3.JPG - Differents zooms on my data... (73.8 KB) Olivier ATHIMON, 2016-03-16 10:47 AM

2009_06_bathy_L93_NGFN.zip - The data used : a shapefile with many points... (747 KB) Olivier ATHIMON, 2016-03-16 10:47 AM

interpolation.jpg (48.1 KB) Maximilian Krambach, 2016-03-17 02:14 PM

Parameters.jpg (150 KB) Olivier ATHIMON, 2018-02-15 10:43 AM

Result_Bad_interpolation.jpg (460 KB) Olivier ATHIMON, 2018-02-15 10:43 AM

History

#1 Updated by Maximilian Krambach almost 9 years ago

When trying with evenly distributed OSM data, I (debian testing, qgis 2.14) get a triangle of data (see interpolation.jpg). It is not a case of "too many points per pixel", as it only searches in the center of the pixel.

The creation of triangles for the TIN (as seen in "export triangles for the triangulation") seems correct.

I think the source is hidden somewhere in "DualEdgeTriangulation::getTriangle"

https://github.com/qgis/QGIS/blob/00633811c9ed40cfc4bdbf2ed66cda5b8c081c27/src/analysis/interpolation/DualEdgeTriangulation.cc#L1082

which returns false in cases of "too many triangles around".

My way there is something like that:;
interpolation/QgsTINInterpolator.cpp: 47: interpolatePoint -->
interpolation/LinTriangleInterpolator.cc : 101: CalcPoint-->
interpolation/dualedgetriangulation.cc: 1082: getTriangle -->
(maybe: interpolation/dualedgetriangulation.cc: 477: baseEdgeOfTriangle)

I don't fully understand the last two functions.

#2 Updated by Maximilian Krambach almost 9 years ago

I tested it in debug mode. For many points, function DualEdgeTriangulation::baseEdgeOfTriangle (477) is entering an endless loop, which is stopped after 300000 runs with an error code, which is then passed down to other functions; those fail because the triangle searched is "-100"

BaseEdgeofTriangle iterates through "mHalfEdge" to find 3 points "on the left side" (494). The counter does not reach 3, because "else" (538) is triggered, which resets the counter to 1.

As it seems, the error lies between line 538 and 546, maybe in which edge is selected next for the leftOf-Test.

#3 Updated by Maximilian Krambach over 8 years ago

In DualEdgeTriangulation:pointVectorCount there is only one definition of mEdgeInside = 3, if mPointVector.count() == 2 (182).
The other options (mPointVector.count() 1,3, >3) miss the appropiate mEdgeInside values, which seem to be different, something between 0 and 5.
This value tells baseEdgeofTriangle (477) on which given edge to start searching. Setting it (479) to 3 results in misses, setting it to 2 results in different misses. 1 or 0 result in QGIS crashing because of index error.
So I guess the value has to be updated according to pointVectorCount for all cases.

#4 Updated by Giovanni Manghi over 8 years ago

  • Priority changed from High to Normal
  • Target version deleted (Future Release - High Priority)

@ Maximilian Krambach can you propose a patch?

#5 Updated by Olivier ATHIMON about 8 years ago

  • Assignee set to Even Rouault

The problem of TIN Interpolation always exists in QGIS LTR 2.14.7, QGIS 2.16.3 and QGIS 2.17...

Any solution Maximilian Krambach?...

Maybe, a solution with the interpolation with library gdal??? I request Mister Even Rouault?...

#6 Updated by Giovanni Manghi almost 8 years ago

  • Category changed from 116 to Analysis library

#7 Updated by Giovanni Manghi almost 8 years ago

  • Target version set to Version 3.0

#8 Updated by Giovanni Manghi over 7 years ago

  • Regression? set to No
  • Easy fix? set to No

#9 Updated by Even Rouault about 7 years ago

  • Assignee deleted (Even Rouault)
  • Description updated (diff)

#10 Updated by Olivier ATHIMON almost 7 years ago

I have tried the same interpolation TIN with QGIS 3 (exactly QGIS 2.99, QGIS b6ad920404)...

and i get the same problem, a bad interpolation...

I join the result (Result_Bad_interpolation.jpg) and my parameters (Parameters.jpg) for the tool :
Processing > QGIS > Interpolation > Interpolation TIN

I used the same input data : 2009_06_bathy_L93_NGFN.zip (joined in my first message)...

#11 Updated by Giovanni Manghi almost 7 years ago

  • Affected QGIS version changed from master to 2.99(master)

#12 Updated by Giovanni Manghi almost 6 years ago

  • Status changed from Open to Closed
  • Resolution set to end of life

Also available in: Atom PDF