Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

TIN interpolation causes crash #14974

Closed
qgib opened this issue Mar 26, 2012 · 23 comments
Closed

TIN interpolation causes crash #14974

qgib opened this issue Mar 26, 2012 · 23 comments

Comments

@qgib
Copy link
Contributor

@qgib qgib commented Mar 26, 2012

Author Name: Giovanni Manghi (@gioman)
Original Redmine Issue: 5239
Affected QGIS version: master
Redmine category:c++_plugins
Assignee: Marco Hugentobler


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.



Related issue(s): #12542 (duplicates), #15831 (relates), #18096 (relates), #18127 (duplicates)
Redmine related issue(s): 2482, 6654, 9505, 9539


@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Mar 30, 2012

Author Name: Thomas Arnold (Thomas Arnold)


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


  • 4357 was configured as DualEdgeTriangulation.cc.diff
  • 4356 was configured as DualEdgeTriangulation.h.diff

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Mar 30, 2012

Author Name: Giovanni Manghi (@gioman)


  • pull_request_patch_supplied was changed from 0 to 1
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Apr 15, 2012

Author Name: Giovanni Manghi (@gioman)


  • fixed_version_id was changed from 35 to Version 1.8.0
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Apr 16, 2012

Author Name: Giovanni Manghi (@gioman)


probably duplicate of #12542

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented May 24, 2012

Author Name: Tristan Allouis (Tristan Allouis)


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!


  • 4486 was configured as test2.xyz

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented May 25, 2012

Author Name: Salvatore Larosa (@slarosa)


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!

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented May 30, 2012

Author Name: Giovanni Manghi (@gioman)


merging this with #14974


  • status_id was changed from Open to Closed
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented May 30, 2012

Author Name: Giovanni Manghi (@gioman)


Giovanni Manghi wrote:

merging this with #14974

see also #12542

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented May 30, 2012

Author Name: Giovanni Manghi (@gioman)


  • status_id was changed from Closed to Reopened
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented May 31, 2012

Author Name: Thomas Arnold (Thomas Arnold)


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.


  • 4530 was configured as 0001-5239_v1.patch

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Jun 7, 2012

Author Name: Tristan Allouis (Tristan Allouis)


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

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Jun 7, 2012

Author Name: Marco Hugentobler (@mhugent)


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.

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Sep 4, 2012

Author Name: Paolo Cavallini (@pcav)


  • fixed_version_id was changed from Version 1.8.0 to Version 2.0.0
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Oct 5, 2012

Author Name: Giovanni Manghi (@gioman)


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


  • status_id was changed from Reopened to Closed
  • resolution was changed from to fixed
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Nov 7, 2012

Author Name: Salvatore Larosa (@slarosa)


Still persists ! (at least under Linux)


  • status_id was changed from Closed to Reopened
  • resolution was changed from fixed to
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Dec 26, 2012

Author Name: Giovanni Manghi (@gioman)


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?


  • status_id was changed from Reopened to Feedback
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Dec 26, 2012

Author Name: Salvatore Larosa (@slarosa)


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)

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Jun 2, 2013

Author Name: Giovanni Manghi (@gioman)


  • priority_id was changed from High to Severe/Regression
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Jun 2, 2013

Author Name: Marco Hugentobler (@mhugent)


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.


  • priority_id was changed from Severe/Regression to High
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Jan 26, 2014

Author Name: Giovanni Manghi (@gioman)


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)


  • fixed_version_id was changed from Version 2.0.0 to Future Release - High Priority
  • status_id was changed from Feedback to Open
@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Feb 12, 2014

Author Name: Martin Dobias (@wonder-sk)


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.

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Feb 13, 2014

Author Name: Giovanni Manghi (@gioman)


Martin Dobias wrote:

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

agree!

@qgib

This comment has been minimized.

Copy link
Contributor Author

@qgib qgib commented Feb 16, 2014

Author Name: Marco Hugentobler (@mhugent)


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).


  • status_id was changed from Open to Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.