Bug report #5239
TIN interpolation causes crash
| 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)
3763_shp.zip (156 KB)
DualEdgeTriangulation.h.diff 
(1.54 KB)
DualEdgeTriangulation.cc.diff
(346 Bytes)
test2.xyz (2.73 MB)
0001-5239_v1.patch
(6.54 KB)
Related issues
History
#1
Updated by Thomas Arnold over 12 years ago
- File DualEdgeTriangulation.cc.diff added
- File DualEdgeTriangulation.h.diff added
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 12 years ago
- Pull Request or Patch supplied changed from No to Yes
#3
Updated by Giovanni Manghi over 12 years ago
- Target version changed from 35 to Version 1.8.0
#4
Updated by Giovanni Manghi over 12 years ago
probably duplicate of #2482
#5
Updated by Tristan Allouis over 12 years ago
- File test2.xyz added
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 12 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 12 years ago
- Status changed from Open to Closed
merging this with #5239
#8
Updated by Giovanni Manghi over 12 years ago
#9
Updated by Giovanni Manghi over 12 years ago
- Status changed from Closed to Reopened
#10
Updated by Thomas Arnold over 12 years ago
- File 0001-5239_v1.patch added
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 12 years ago
Hello,
Thank you for the patch Thomas, it works well !
#12
Updated by Marco Hugentobler over 12 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 over 12 years ago
- Target version changed from Version 1.8.0 to Version 2.0.0
#14
Updated by Giovanni Manghi about 12 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 12 years ago
- Status changed from Closed to Reopened
- Resolution deleted (
fixed)
Still persists ! (at least under Linux)
#16
Updated by Giovanni Manghi almost 12 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 12 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 11 years ago
- Priority changed from High to Severe/Regression
#19
Updated by Marco Hugentobler over 11 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 11 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 11 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 11 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 almost 11 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).