https://issues.qgis.org/https://issues.qgis.org/favicon.ico2012-03-30T11:49:24ZQGIS Issue TrackingQGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=298722012-03-30T11:49:24ZThomas Arnoldth.arnold@gmx.net
<ul><li><strong>File</strong> <a href="/attachments/download/4357/DualEdgeTriangulation.cc.diff">DualEdgeTriangulation.cc.diff</a><a href="/attachments/4357/DualEdgeTriangulation.cc.diff"><img alt="Magnifier" src="/images/magnifier.png" /></a> added</li><li><strong>File</strong> <a href="/attachments/download/4356/DualEdgeTriangulation.h.diff">DualEdgeTriangulation.h.diff</a><a href="/attachments/4356/DualEdgeTriangulation.h.diff"><img alt="Magnifier" src="/images/magnifier.png" /></a> added</li></ul><p>Hi,</p>
<p>could anybody check this solution?<br />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.</p>
<p>Thomas</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=298752012-03-30T22:37:42ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Pull Request or Patch supplied</strong> changed from <i>No</i> to <i>Yes</i></li></ul> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=302292012-04-15T08:00:28ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Target version</strong> changed from <i>35</i> to <i>Version 1.8.0</i></li></ul> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=307172012-04-16T02:25:56ZGiovanni Manghigiovanni.manghi@gmail.com
<ul></ul><p>probably duplicate of <a class="issue tracker-1 status-5 priority-5 priority- closed" href="https://issues.qgis.org/issues/2482" title="Interpolation plugin causes seg fault (Closed)">#2482</a></p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=321782012-05-24T23:37:58ZTristan Allouis
<ul><li><strong>File</strong> <a href="/attachments/download/4486/test2.xyz">test2.xyz</a> added</li></ul><p>Same problem: Segmentation fault using the "interpolation" plugin and the TIN method on a xyz dataset (Z interpolation).<br />I checked the patch but it bit not fix the problem.</p>
<p>According to my tests, qgis crashes when the points to interpolate are too close (too dense dataset).<br />I enclose a dataset that causing qgis to crash. Use the SCR ID 10090.</p>
<p>Please can you test this dataset and report if it crashes or not ?</p>
<p>Thanks!</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=321822012-05-25T02:15:56ZSalvatore Larosalrssvtml@gmail.com
<ul></ul><p>Reverting the patch does not work! (tested w/test2.xyz)</p>
<p>below the backtrace, if it can you help:</p>
<pre>
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) ()
........................
</pre>
<p>loop till to the end, alterning doSwap and checkSwap!</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=323112012-05-30T03:24:47ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li></ul><p>merging this with <a class="issue tracker-1 status-5 priority-5 priority- closed" href="https://issues.qgis.org/issues/5239" title="TIN interpolation causes crash (Closed)">#5239</a></p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=323132012-05-30T03:25:11ZGiovanni Manghigiovanni.manghi@gmail.com
<ul></ul><p>Giovanni Manghi wrote:</p>
<blockquote>
<p>merging this with <a class="issue tracker-1 status-5 priority-5 priority- closed" href="https://issues.qgis.org/issues/5239" title="TIN interpolation causes crash (Closed)">#5239</a></p>
</blockquote>
<p>see also <a class="issue tracker-1 status-5 priority-5 priority- closed" href="https://issues.qgis.org/issues/2482" title="Interpolation plugin causes seg fault (Closed)">#2482</a></p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=323162012-05-30T03:38:43ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Status</strong> changed from <i>Closed</i> to <i>Reopened</i></li></ul> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=324042012-05-31T22:15:02ZThomas Arnoldth.arnold@gmx.net
<ul><li><strong>File</strong> <a href="/attachments/download/4530/0001-5239_v1.patch">0001-5239_v1.patch</a><a href="/attachments/4530/0001-5239_v1.patch"><img alt="Magnifier" src="/images/magnifier.png" /></a> added</li></ul><p>Hi,</p>
<p>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.</p>
<p>Thomas</p>
<p>By the way I used the "git format-patch" command to create this patch. I hope it is ok.</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=326342012-06-07T04:12:41ZTristan Allouis
<ul></ul><p>Hello,<br />Thank you for the patch Thomas, it works well !</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=326542012-06-07T10:21:15ZMarco Hugentoblermarco.hugentobler@sourcepole.ch
<ul></ul><p>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).</p>
<p>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.</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=343492012-09-04T09:53:43ZPaolo Cavallinicavallini@faunalia.it
<ul><li><strong>Target version</strong> changed from <i>Version 1.8.0</i> to <i>Version 2.0.0</i></li></ul> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=356972012-10-05T12:24:26ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Status</strong> changed from <i>Reopened</i> to <i>Closed</i></li><li><strong>Resolution</strong> set to <i>fixed</i></li></ul><p>Tested again on master and it works fine, no more crashes.</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=369392012-11-07T13:23:38ZSalvatore Larosalrssvtml@gmail.com
<ul><li><strong>Status</strong> changed from <i>Closed</i> to <i>Reopened</i></li><li><strong>Resolution</strong> deleted (<del><i>fixed</i></del>)</li></ul><p>Still persists ! (at least under Linux)</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=379052012-12-26T10:11:10ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Status</strong> changed from <i>Reopened</i> to <i>Feedback</i></li></ul><p>Salvatore Larosa wrote:</p>
<blockquote>
<p>Still persists ! (at least under Linux)</p>
</blockquote>
<p>tested now on linux (ubuntu) and qgis master and seems to work ok. Salvatore, still a crash for you?</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=379132012-12-26T13:07:06ZSalvatore Larosalrssvtml@gmail.com
<ul></ul><p>Giovanni Manghi wrote:</p>
<blockquote>
<p>tested now on linux (ubuntu) and qgis master and seems to work ok. Salvatore, still a crash for you?</p>
</blockquote>
<p>Hi Giovanni,<br />yes, it still happens here with a similar backtrace (as above):</p>
<pre>
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)
</pre>
<p>Tested with the attached dataset (3763.shp)</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=416242013-06-02T07:08:22ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Priority</strong> changed from <i>High</i> to <i>Severe/Regression</i></li></ul> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=416592013-06-02T21:35:12ZMarco Hugentoblermarco.hugentobler@sourcepole.ch
<ul><li><strong>Priority</strong> changed from <i>Severe/Regression</i> to <i>High</i></li></ul><p>This wasn't working in 1.8 too, so shouldn't be a blocker.<br />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.</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=476872014-01-26T09:24:03ZGiovanni Manghigiovanni.manghi@gmail.com
<ul><li><strong>Target version</strong> changed from <i>Version 2.0.0</i> to <i>Future Release - High Priority</i></li><li><strong>Status</strong> changed from <i>Feedback</i> to <i>Open</i></li></ul><p>Marco Hugentobler wrote:</p>
<blockquote>
<p>This wasn't working in 1.8 too, so shouldn't be a blocker.<br />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.</p>
</blockquote>
<p>still crashes qgis, now I see just</p>
<p>Segmentation fault (core dumped)</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=484942014-02-12T02:09:32ZMartin Dobiaswonder.sk@gmail.com
<ul></ul><p>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).</p>
<p>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!</p>
<p>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.</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=485712014-02-13T10:32:22ZGiovanni Manghigiovanni.manghi@gmail.com
<ul></ul><p>Martin Dobias wrote:</p>
<blockquote>
<p>After all, we do not need a perfect Delaunay triangulation for the interpolation - much more important is not to crash!</p>
</blockquote>
<p>agree!</p> QGIS Application - Bug report #5239: TIN interpolation causes crashhttps://issues.qgis.org/issues/5239?journal_id=487292014-02-16T23:11:02ZMarco Hugentoblermarco.hugentobler@sourcepole.ch
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li></ul><p>Since I didn't have time to look at the triangulation code, I just upplied the patch now.</p>
<blockquote>
<p>An obvious choice can be GEOS (support Delaunay triangulation since 3.4 release) or qhull</p>
</blockquote>
<p>Do they support constrained triangulations? qhull says it does not and for geos, I didn't find it mentioned in the documentation.<br />Also, it would be cool to have a library which supports very large datasets (current implementation unfortunately loads everything into virtual memory).</p>