Bug report #5239

TIN interpolation causes crash

Added by Giovanni Manghi over 7 years ago. Updated over 5 years ago.

Status:Closed
Priority:High
Assignee:Marco Hugentobler
Category:C++ Plugins
Affected QGIS version:master Regression?:No
Operating System: Easy fix?:No
Pull Request or Patch supplied:Yes Resolution:
Crashes QGIS or corrupts data:Yes Copied to github as #:14974

Description

Tested on master and 1.7.4 on both linux and windows.

The attached layer "3763" causes qgis to crash if interpolating (with the "Z" column) with the "interpolation" plugin and the TIN method. Works fine with IDW.

Strangely enough, the very same layer saved in another CRS (attached here) does not cause the tool to crash qgis.

In both cases the project CRS was set as the same as the layer being processed.

MoBatimIST_shp.zip (104 KB) Giovanni Manghi, 2012-03-26 03:48 PM

3763_shp.zip (156 KB) Giovanni Manghi, 2012-03-26 03:48 PM

DualEdgeTriangulation.h.diff Magnifier (1.54 KB) Thomas Arnold, 2012-03-30 01:49 PM

DualEdgeTriangulation.cc.diff Magnifier (346 Bytes) Thomas Arnold, 2012-03-30 01:49 PM

test2.xyz (2.73 MB) Tristan Allouis, 2012-05-25 01:37 AM

0001-5239_v1.patch Magnifier (6.54 KB) Thomas Arnold, 2012-06-01 12:15 AM


Related issues

Related to QGIS Application - Bug report #6654: QgsTINInterpolator.interpolatePoints() called from Python... Closed 2012-11-07
Related to QGIS Application - Bug report #9505: qgis crash on TIN interpolation of curve line Closed 2014-02-06
Duplicates QGIS Application - Bug report #2482: Interpolation plugin causes seg fault Closed 2011-07-25
Duplicated by QGIS Application - Bug report #9539: Interpolation Plugin crash when executed Closed 2014-02-11

History

#1 Updated by Thomas Arnold over 7 years ago

Hi,

could anybody check this solution?
I think it was a numerical problem. The value of the leftOfTresh was too small. So the case "p is in a line with p0 and p1" could not detect.

Thomas

#2 Updated by Giovanni Manghi over 7 years ago

  • Pull Request or Patch supplied changed from No to Yes

#3 Updated by Giovanni Manghi over 7 years ago

  • Target version changed from 35 to Version 1.8.0

#4 Updated by Giovanni Manghi over 7 years ago

probably duplicate of #2482

#5 Updated by Tristan Allouis over 7 years ago

Same problem: Segmentation fault using the "interpolation" plugin and the TIN method on a xyz dataset (Z interpolation).
I checked the patch but it bit not fix the problem.

According to my tests, qgis crashes when the points to interpolate are too close (too dense dataset).
I enclose a dataset that causing qgis to crash. Use the SCR ID 10090.

Please can you test this dataset and report if it crashes or not ?

Thanks!

#6 Updated by Salvatore Larosa over 7 years ago

Reverting the patch does not work! (tested w/test2.xyz)

below the backtrace, if it can you help:

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff4220c79 in MathUtils::triArea(Point3D*, Point3D*, Point3D*) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
(gdb) bt
#0  0x00007ffff4220c79 in MathUtils::triArea(Point3D*, Point3D*, Point3D*) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#1  0x00007ffff421f74a in MathUtils::inCircle(Point3D*, Point3D*, Point3D*, Point3D*) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#2  0x00007ffff420a1ef in DualEdgeTriangulation::checkSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#3  0x00007ffff420a768 in DualEdgeTriangulation::doSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#4  0x00007ffff420a204 in DualEdgeTriangulation::checkSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#5  0x00007ffff420a768 in DualEdgeTriangulation::doSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#6  0x00007ffff420a204 in DualEdgeTriangulation::checkSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#7  0x00007ffff420a768 in DualEdgeTriangulation::doSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#8  0x00007ffff420a204 in DualEdgeTriangulation::checkSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#9  0x00007ffff420a768 in DualEdgeTriangulation::doSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#10 0x00007ffff420a204 in DualEdgeTriangulation::checkSwap(unsigned int) ()
   from /usr/local/lib/libqgis_analysis.so.1.8.0
#11 0x00007ffff420a768 in DualEdgeTriangulation::doSwap(unsigned int) ()
........................

loop till to the end, alterning doSwap and checkSwap!

#7 Updated by Giovanni Manghi over 7 years ago

  • Status changed from Open to Closed

merging this with #5239

#8 Updated by Giovanni Manghi over 7 years ago

Giovanni Manghi wrote:

merging this with #5239

see also #2482

#9 Updated by Giovanni Manghi over 7 years ago

  • Status changed from Closed to Reopened

#10 Updated by Thomas Arnold over 7 years ago

Hi,

the mean problem is the recursiv call checkSwap<->doSwap. I don't know the precise reason why the recursion sometimes never ends. But how about the simple strategy to limit the recrusiv deep? I know that is not ideal. But this prevent that qgis crashes.

Thomas

By the way I used the "git format-patch" command to create this patch. I hope it is ok.

#11 Updated by Tristan Allouis over 7 years ago

Hello,
Thank you for the patch Thomas, it works well !

#12 Updated by Marco Hugentobler over 7 years ago

I agree the numerical stability of the triangulation code is not rock-solid (and if there are volunteers for maintaining the triangulation code, that would be great).

As Thomas points out, limiting the recursive depth of the swaping is not optimal (in extreme cases, one point insertion could swap all the existing edges in a triangulation). Therefore, I'm not applying that patch to the git repo.

#13 Updated by Paolo Cavallini about 7 years ago

  • Target version changed from Version 1.8.0 to Version 2.0.0

#14 Updated by Giovanni Manghi about 7 years ago

  • Status changed from Reopened to Closed
  • Resolution set to fixed

Tested again on master and it works fine, no more crashes.

#15 Updated by Salvatore Larosa about 7 years ago

  • Status changed from Closed to Reopened
  • Resolution deleted (fixed)

Still persists ! (at least under Linux)

#16 Updated by Giovanni Manghi almost 7 years ago

  • Status changed from Reopened to Feedback

Salvatore Larosa wrote:

Still persists ! (at least under Linux)

tested now on linux (ubuntu) and qgis master and seems to work ok. Salvatore, still a crash for you?

#17 Updated by Salvatore Larosa almost 7 years ago

Giovanni Manghi wrote:

tested now on linux (ubuntu) and qgis master and seems to work ok. Salvatore, still a crash for you?

Hi Giovanni,
yes, it still happens here with a similar backtrace (as above):

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff3fb29a0 in MathUtils::triArea (pa=0x60f94a0, pb=0x6455cc0, pc=0x63f7a00)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/MathUtils.cc:503
503        double deter = ( pa->getX() * pb->getY() + pb->getX() * pc->getY() + pc->getX() * pa->getY() - pa->getX() * pc->getY() - pb->getX() * pa->getY() - pc->getX() * pb->getY() );
(gdb) bt
#0  0x00007ffff3fb29a0 in MathUtils::triArea (pa=0x60f94a0, pb=0x6455cc0, pc=0x63f7a00)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/MathUtils.cc:503
#1  0x00007ffff3fb07ff in MathUtils::inCircle (testp=0x63f7a00, p1=0x6454620, p2=0x60f94a0, p3=
    0x6455cc0) at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/MathUtils.cc:266
#2  0x00007ffff3f95aab in DualEdgeTriangulation::checkSwap (this=0x645fa00, edge=359)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:692
#3  0x00007ffff3f96024 in DualEdgeTriangulation::doSwap (this=0x645fa00, edge=909)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:735
#4  0x00007ffff3f95ac0 in DualEdgeTriangulation::checkSwap (this=0x645fa00, edge=909)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:694
#5  0x00007ffff3f96024 in DualEdgeTriangulation::doSwap (this=0x645fa00, edge=483)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:735
#6  0x00007ffff3f95ac0 in DualEdgeTriangulation::checkSwap (this=0x645fa00, edge=483)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:694
#7  0x00007ffff3f96024 in DualEdgeTriangulation::doSwap (this=0x645fa00, edge=689)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:735
#8  0x00007ffff3f95ac0 in DualEdgeTriangulation::checkSwap (this=0x645fa00, edge=689)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:694
#9  0x00007ffff3f96024 in DualEdgeTriangulation::doSwap (this=0x645fa00, edge=359)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:735
#10 0x00007ffff3f95ac0 in DualEdgeTriangulation::checkSwap (this=0x645fa00, edge=359)
    at /home/sam/pacchetti_gis/Quantum-GIS/src/analysis/interpolation/DualEdgeTriangulation.cc:694
#11 0x00007ffff3f96024 in DualEdgeTriangulation::doSwap (this=0x645fa00, edge=909)

Tested with the attached dataset (3763.shp)

#18 Updated by Giovanni Manghi over 6 years ago

  • Priority changed from High to Severe/Regression

#19 Updated by Marco Hugentobler over 6 years ago

  • Priority changed from Severe/Regression to High

This wasn't working in 1.8 too, so shouldn't be a blocker.
Btw., it obviously is something related to numerical stability of the TIN generation. Therefore it is more likely in degree coordinate system than in meters.

#20 Updated by Giovanni Manghi almost 6 years ago

  • Target version changed from Version 2.0.0 to Future Release - High Priority
  • Status changed from Feedback to Open

Marco Hugentobler wrote:

This wasn't working in 1.8 too, so shouldn't be a blocker.
Btw., it obviously is something related to numerical stability of the TIN generation. Therefore it is more likely in degree coordinate system than in meters.

still crashes qgis, now I see just

Segmentation fault (core dumped)

#21 Updated by Martin Dobias almost 6 years ago

The numerical stability issues are apparent especially in cases when points are forming rectangles, ending up swapping edges infinitely (well, until QGIS runs out of stack and crashes).

For short term solution I would propose using Thomas Arnold's patch to limit the recursion depth. The numerical errors are IMHO not easy to resolve, especially because there are two ad-hoc thresholds involved (one for point-in-circle test, other one for which-side-of-line test). Marco's point about possible sub-optimal triangulation are valid, but I think mostly theoretical (if the recursion level is great enough, e.g. 1000). After all, we do not need a perfect Delaunay triangulation for the interpolation - much more important is not to crash!

For longer term solution we should use a proven implementation where we do not need to deal with such issues. An obvious choice can be GEOS (support Delaunay triangulation since 3.4 release) or qhull.

#22 Updated by Giovanni Manghi almost 6 years ago

Martin Dobias wrote:

After all, we do not need a perfect Delaunay triangulation for the interpolation - much more important is not to crash!

agree!

#23 Updated by Marco Hugentobler over 5 years ago

  • Status changed from Open to Closed

Since I didn't have time to look at the triangulation code, I just upplied the patch now.

An obvious choice can be GEOS (support Delaunay triangulation since 3.4 release) or qhull

Do they support constrained triangulations? qhull says it does not and for geos, I didn't find it mentioned in the documentation.
Also, it would be cool to have a library which supports very large datasets (current implementation unfortunately loads everything into virtual memory).

Also available in: Atom PDF