Crash with a simple polygon #11
Comments
wonder-sk
added a commit
to wonder-sk/QGIS
that referenced
this issue
Jan 9, 2020
It looks like it was introduced when trying to make compiler happy: jhasse/poly2tri@e0ba327 Also added a test to make sure this crasher does not come back See jhasse/poly2tri#11 for upstream issue
|
We should add a test case for that polygon. |
brandon-kohn
added a commit
to brandon-kohn/poly2tri
that referenced
this issue
Sep 29, 2022
commit 2c7ef27c0f666101f339f42400396f30edadd676 Author: Brandon Kohn <[email protected]> Date: Tue Sep 20 11:59:30 2022 -0400 Fixed compile issues. commit 740ea0dfd10d160fef2e4610671039a1fd15f00f Merge: f189424 81612cb Author: Brandon Kohn <[email protected]> Date: Tue Sep 20 11:52:44 2022 -0400 Merge remote-tracking branch 'upstream/master' into update/merge_from_upstream commit 81612cb Merge: d6ecda3 563239d Author: Jan Niklas Hasse <[email protected]> Date: Fri May 20 15:46:44 2022 +0200 Merge pull request jhasse#43 from AndriyAndreyev/stability_fixes Stability fixes commit d6ecda3 Merge: 54af704 505f63d Author: Jan Niklas Hasse <[email protected]> Date: Mon May 9 10:08:46 2022 +0200 Merge pull request jhasse#47 from pierre-dejoue/pragma-once Replace header guards by pragma once commit 505f63d Author: Pierre Dejoue <[email protected]> Date: Sun May 8 19:26:22 2022 +0200 Pragma once and for all commit 54af704 Merge: dbc52ac abdf448 Author: Jan Niklas Hasse <[email protected]> Date: Fri May 6 07:56:47 2022 +0200 Merge pull request jhasse#46 from pierre-dejoue/testbed-autozoom QoL: Add auto-zoom feature to the testbed app commit 563239d Author: AndriyAndreyev <[email protected]> Date: Fri May 6 00:49:31 2022 +0300 Add unittest to check stack overflow crash Signed-off-by: AndriyAndreyev <[email protected]> commit afee326 Merge: 15dfbc2 dbc52ac Author: AndriyAndreyev <[email protected]> Date: Fri May 6 00:50:55 2022 +0300 Merge remote-tracking branch 'upstream/master' commit abdf448 Author: Pierre Dejoue <[email protected]> Date: Sun Apr 24 17:36:35 2022 +0200 Testbed autozoom feature commit 36e5514 Author: Pierre Dejoue <[email protected]> Date: Sun Apr 24 16:36:26 2022 +0200 Testbed usage note commit 39a5f47 Author: Pierre Dejoue <[email protected]> Date: Sun Apr 24 17:10:22 2022 +0200 Testbed: global config variable to set the window size commit bdd6e3b Author: Pierre Dejoue <[email protected]> Date: Thu Apr 21 01:04:32 2022 +0200 Add to the testbed report the result of the Delaunay test commit dbc52ac Merge: a8247ae 49a12eb Author: Jan Niklas Hasse <[email protected]> Date: Thu May 5 18:25:29 2022 +0200 Merge pull request jhasse#42 from pierre-dejoue/dllexport Rework on dllexport/dllimport definitions commit 15dfbc2 Merge: 1bf8fad a8247ae Author: AndriyAndreyev <[email protected]> Date: Thu May 5 01:11:12 2022 +0300 Merge remote-tracking branch 'upstream/master' commit a8247ae Merge: 3380f5c de70670 Author: Jan Niklas Hasse <[email protected]> Date: Tue May 3 08:57:24 2022 +0200 Merge pull request jhasse#44 from pierre-dejoue/test-case-issue-10 Test polygons from issue jhasse#10 commit de70670 Author: Pierre Dejoue <[email protected]> Date: Sun Nov 1 22:10:03 2020 +0100 Test polygons from issue jhasse#10 commit 1bf8fad Author: AndriyAndreyev <[email protected]> Date: Tue Apr 26 21:46:45 2022 +0300 Add test case to check stack overflow crash Without additional check is angle negative or not in the LargeHole_DontFill function this test case leads to stack overflow. Signed-off-by: AndriyAndreyev <[email protected]> commit 64636de Author: AndriyAndreyev <[email protected]> Date: Tue Apr 26 21:46:11 2022 +0300 Сonsider that LargeHole_DontFill is true if angle is negative Otherwise, a wrong triangle can be generated Signed-off-by: AndriyAndreyev <[email protected]> commit 49a12eb Author: Pierre Dejoue <[email protected]> Date: Wed Apr 20 22:12:21 2022 +0200 Set the API export symbols based on CMake BUILD_SHARED_LIBS By default poly2tri is built as a static library. commit 7f5846b Author: Pierre Dejoue <[email protected]> Date: Sun Apr 17 14:12:01 2022 +0200 Retakes on dllexport/dllimport commit ad184c3 Author: Clifford Yapp <[email protected]> Date: Tue Aug 3 17:19:16 2021 -0400 Add dllexport/dllimport definitions. commit 3380f5c Author: Jan Niklas Hasse <[email protected]> Date: Fri Mar 25 08:49:45 2022 +0100 Apply even more clang-tidy fixes commit dcdb744 Author: Jan Niklas Hasse <[email protected]> Date: Fri Mar 25 07:56:30 2022 +0100 Apply several clang-tidy fixes commit 529470f Merge: 8b5fa15 30279f7 Author: Jan Niklas Hasse <[email protected]> Date: Wed Mar 23 21:34:31 2022 +0100 Merge pull request jhasse#40 from roystgnr/no_collinearity_tolerance Disable collinearity tolerance commit 30279f7 Author: Roy Stogner <[email protected]> Date: Wed Mar 16 08:35:34 2022 -0500 Use std::fpclassify for double==0 tests commit 19ec7c7 Author: Roy Stogner <[email protected]> Date: Tue Mar 15 20:37:14 2022 -0500 ConcaveBoundaryTest unit test This is from the case I originally got to trigger the problem. We could probably boil it down to something smaller (by temporarily reverting the Orient2d change to make sure the failure still occurs) but this doesn't seem too bloated for a unit test as-is. commit cc1e657 Author: Roy Stogner <[email protected]> Date: Tue Mar 15 20:36:53 2022 -0500 NarrowQuadTest triangulation succeeds now commit 57b3039 Author: Roy Stogner <[email protected]> Date: Tue Mar 15 19:16:40 2022 -0500 Disable tolerance in Orient2d collinearity test This fixes failures for me when trying to triangulate concave-by-less-than-epsilon boundary polylines. commit 8b5fa15 Merge: 136fa7a 4581f1f Author: Jan Niklas Hasse <[email protected]> Date: Thu Dec 2 15:46:35 2021 +0100 Merge pull request jhasse#34 from roystgnr/instructions_update File naming, build/run instruction updates commit 4581f1f Author: Roy Stogner <[email protected]> Date: Wed Dec 1 17:38:53 2021 -0600 Consistent executable path in README.md These commands run (from the source directory; would commands as run from the build directory be clearer?) for me as-is (after the testbed executable has been built) now. commit 4fd0287 Author: Roy Stogner <[email protected]> Date: Wed Dec 1 17:38:23 2021 -0600 Fix, clarify build instructions If we're in a build subdirectory, we need `..` to tell cmake where to find the source directory. commit cbc025a Author: Roy Stogner <[email protected]> Date: Wed Dec 1 17:37:18 2021 -0600 Note unit test dependencies I already had most of Boost installed, but not enough. commit ebf0c4d Author: Roy Stogner <[email protected]> Date: Wed Dec 1 17:36:31 2021 -0600 Rename testbed/testbed to testbed/p2t That's what README.md has been referencing as the executable name, and it's more meaningful. commit 136fa7a Author: Jan Niklas Hasse <[email protected]> Date: Sat Aug 21 17:28:47 2021 +0200 Move Point ctor into .cc file to hide shadowing from users See jhasse#15 and jhasse#31. commit 7f0487a Merge: 4a323bf 905a765 Author: Jan Niklas Hasse <[email protected]> Date: Tue May 18 10:24:21 2021 +0200 Merge pull request jhasse#29 from piotrkania-here/sanity_checks Additional sanity checks for triangulate operation commit 905a765 Author: Piotr Kania <[email protected]> Date: Thu Apr 29 11:51:05 2021 +0200 Additional sanity checks for triangulate operation commit 4a323bf Merge: 444ee57 af36bac Author: Jan Niklas Hasse <[email protected]> Date: Mon Apr 26 17:02:23 2021 +0200 Merge pull request jhasse#28 from piotrkania-here/check_ptr Check pointer before dereferencing it commit af36bac Author: Piotr Kania <[email protected]> Date: Mon Apr 26 10:25:12 2021 +0200 Check pointer before dereferencing it commit 444ee57 Merge: d949f3c b4534b3 Author: Jan Niklas Hasse <[email protected]> Date: Sat Apr 24 11:11:52 2021 +0200 Merge pull request jhasse#27 from piotrkania-here/fixed_point_operator Fixed inequality operator for Point struct commit b4534b3 Author: Piotr Kania <[email protected]> Date: Fri Apr 23 14:32:39 2021 +0200 Fixed inequality operator for Point struct commit d949f3c Author: Jan Niklas Hasse <[email protected]> Date: Sat Jan 16 18:43:00 2021 +0100 Add namespace comment commit 8b8e6cb Author: Jan Niklas Hasse <[email protected]> Date: Thu Dec 17 23:12:58 2020 +0100 Ignore .cache/ commit 4515f65 Merge: 83680d9 8388a74 Author: Jan Niklas Hasse <[email protected]> Date: Fri Nov 20 11:38:31 2020 +0100 Merge pull request jhasse#23 from pierre-dejoue/master Improvement to the testbed application commit 8388a74 Author: Pierre Dejoue <[email protected]> Date: Wed Nov 11 22:04:39 2020 +0100 Improve testbed data file format Data file format now has optional sections for holes polylines and Steiner points identified with tokens "HOLE" and "STEINER". Rework the data file dude.dat accordingly. Add data file steiner.dat for an example with Steiner points. commit cf5f95d Author: Pierre Dejoue <[email protected]> Date: Wed Nov 11 19:57:54 2020 +0100 Fix compilation warnings in testbed commit 83680d9 Author: Jan Niklas Hasse <[email protected]> Date: Fri Nov 6 22:37:50 2020 +0000 Remove Waf build system, fix jhasse#14 commit e9938d9 Merge: c4404a7 718d687 Author: Jan Niklas Hasse <[email protected]> Date: Mon Oct 26 20:18:51 2020 +0000 Merge pull request jhasse#22 from pierre-dejoue/master Add documentation and code patches for maintenability commit 718d687 Author: Pierre Dejoue <[email protected]> Date: Mon Oct 26 09:15:52 2020 +0100 Add references section to README The flipscan picture by Thomas Ahlen was found on those pages: https://blackflux.wordpress.com/2014/03/01/meshing-in-voxel-engines-part-2/ https://groups.google.com/g/poly2tri/c/LNfxMtVyhqs commit 1054475 Author: Pierre Dejoue <[email protected]> Date: Sun Oct 25 17:32:28 2020 +0100 Triangle::NeighborAcross to return a pointer Same as Triangle::NeighborCW and Triangle::NeighborCCW commit 35b2fa9 Author: Pierre Dejoue <[email protected]> Date: Sun Oct 25 14:56:23 2020 +0100 Patch inversion of head and tail in the advancing front initialization No functional impact, the code is equivalent. We just assign head_ to af_head_ and tail_ to af_tail_ as one would expect. commit 5aa0c22 Author: Pierre Dejoue <[email protected]> Date: Sun Oct 25 15:58:16 2020 +0100 Add headers in project files generated by cmake commit c480777 Author: Pierre Dejoue <[email protected]> Date: Sat Oct 24 19:56:43 2020 +0200 Update README for cmake commit c4404a7 Author: Jan Niklas Hasse <[email protected]> Date: Sun Oct 25 20:50:14 2020 +0100 Avoid redefinition of BOOST_TEST_DYN_LINK commit 6febaed Author: Jan Niklas Hasse <[email protected]> Date: Mon Oct 19 18:27:52 2020 +0200 Add debug configurations for VSCode commit a3a6456 Author: Jan Niklas Hasse <[email protected]> Date: Mon Oct 19 18:27:21 2020 +0200 Add namespace comment for clang-tidy commit f6ca87a Author: Jan Niklas Hasse <[email protected]> Date: Mon Oct 19 18:24:46 2020 +0200 Add .clang-format commit f91fcd9 Merge: a269fb4 0554608 Author: Jan Niklas Hasse <[email protected]> Date: Thu Aug 27 20:09:59 2020 +0200 Merge pull request jhasse#20 from pierre-dejoue/master Add CMake files for the unit tests and the testbed app commit 0554608 Author: Pierre Dejoue <[email protected]> Date: Thu Aug 27 19:12:15 2020 +0200 Add CMake files for the testbed commit 7125fdb Author: Pierre Dejoue <[email protected]> Date: Tue Jul 14 18:16:18 2020 +0200 Add CMake files for the unit tests - Building unit tests is optional, disabled by default to prevent the library clients from pulling the dependency on boost - Add the unit tests to the Github Actions. - Use boost::filesystem to manipulate paths for better portability commit a269fb4 Merge: 6c184d1 2c6bec6 Author: Jan Niklas Hasse <[email protected]> Date: Thu Aug 6 23:54:23 2020 +0200 Merge pull request jhasse#19 from pierre-dejoue/master Add one exception case in Triangle::NeighborAcross commit 2c6bec6 Author: Pierre Dejoue <[email protected]> Date: Thu May 21 16:14:10 2020 +0200 Throw in Triangle::NeighborAcross in case of null pointer Add an example quad for which the exception is throwni in the tests commit 06b0f14 Author: Pierre Dejoue <[email protected]> Date: Thu May 21 15:47:13 2020 +0200 Actually throw exceptions commit 7f8c4c5 Author: Pierre Dejoue <[email protected]> Date: Sun Jul 12 11:57:01 2020 +0200 Rename local index for readability commit 3e583f5 Author: Pierre Dejoue <[email protected]> Date: Thu Aug 6 19:36:19 2020 +0200 Fix linux build action commit 6c184d1 Author: Jan Niklas Hasse <[email protected]> Date: Sun Jun 14 20:14:58 2020 +0200 Use nullptr instead of NULL or 0 commit f5f9d33 Author: Jan Niklas Hasse <[email protected]> Date: Thu Jun 4 22:40:09 2020 +0200 Add simple Doxyfile commit f16f016 Author: Jan Niklas Hasse <[email protected]> Date: Tue May 5 13:31:21 2020 +0200 Remove Azure Pipelines config commit 722ddf7 Author: Jan Niklas Hasse <[email protected]> Date: Tue May 5 13:29:33 2020 +0200 Add GitHub Actions configuration (jhasse#16) commit e66d045 Author: Martin Dobias <[email protected]> Date: Mon Jan 20 10:19:20 2020 +0100 Fix jhasse#11 - regression causing crash when abs(p1.y - p2.y) < 1e10 (jhasse#12) This reverts commit e0ba327. While the orignal commit silences a compiler warning, it introduces incorrect behavior in Edge constructor that causes crash later during triangulation. See jhasse#11 for an example of a simple polygon that would cause crash commit e6e63dd Author: Jan Niklas Hasse <[email protected]> Date: Sat Nov 30 14:03:43 2019 +0100 Update waf to 2.0.19 commit 5a171da Author: Jan Niklas Hasse <[email protected]> Date: Tue Jun 11 12:05:12 2019 +0200 Add missing include for GCC 9.1 commit 3a2db01 Author: Jan Niklas Hasse <[email protected]> Date: Tue Mar 12 13:38:06 2019 +0100 Create path for TestbedFilesTest relative to build folder commit 0898bb2 Author: Jan Niklas Hasse <[email protected]> Date: Thu Feb 21 14:42:20 2019 +0100 Add function IsDelaunay to check if results are valid commit 96b08ee Author: Jan Niklas Hasse <[email protected]> Date: Thu Feb 21 14:34:37 2019 +0100 Add new function Triangle::CircumcicleContains commit e945488 Author: Jan Niklas Hasse <[email protected]> Date: Fri Jan 25 00:20:39 2019 +0100 Set up CI with Azure Pipelines (jhasse#7) commit 48f545c Author: Jan Niklas Hasse <[email protected]> Date: Wed Sep 26 11:09:14 2018 +0200 Meson: Add poly2tri_dep variable commit a41b316 Author: Jan Niklas Hasse <[email protected]> Date: Tue Sep 11 13:02:47 2018 +0200 Add tasks.json for VS Code commit 4973f2e Author: Jan Niklas Hasse <[email protected]> Date: Tue Sep 11 13:00:49 2018 +0200 Change BSD-3 license formatting a little bit so that GitHub detects it commit 9c8b474 Author: Jan Niklas Hasse <[email protected]> Date: Tue Sep 11 12:53:31 2018 +0200 Update project URL and copyright year commit e0ba327 Author: Jan Niklas Hasse <[email protected]> Date: Tue Aug 21 13:07:06 2018 +0200 Do not compare doubles with == commit 0105437 Author: Jan Niklas Hasse <[email protected]> Date: Mon Aug 13 14:46:34 2018 +0200 Add simple CMakeLists.txt commit a9d2cf8 Author: Jan Niklas Hasse <[email protected]> Date: Mon May 28 19:55:02 2018 +0200 Add very simple unit test commit 1271d6b Author: Jan Niklas Hasse <[email protected]> Date: Mon May 28 13:56:27 2018 +0200 Overload operator<< for Point commit 66ff955 Author: Jan Niklas Hasse <[email protected]> Date: Fri Apr 13 19:29:10 2018 +0200 Remove unused parameter from CreateAdvancingFront, fix jhasse#3 commit 1ed5e08 Author: Jan Niklas Hasse <[email protected]> Date: Fri Apr 13 19:16:30 2018 +0200 Include shapes.h and cmath instead of math.h commit 001b5cd Author: Jan Niklas Hasse <[email protected]> Date: Fri Apr 13 19:15:44 2018 +0200 Settings for VS Code commit 053fce6 Author: Jan Niklas Hasse <[email protected]> Date: Tue Mar 13 16:04:11 2018 +0100 Add Meson build file commit f0a1641 Author: Jan Niklas Hasse <[email protected]> Date: Wed Feb 28 17:34:54 2018 +0100 Throw an exception instead of assert(false) for repeat points commit 76b3b53 Author: Jan Niklas Hasse <[email protected]> Date: Wed Apr 13 17:56:42 2016 +0200 Update waf to 1.8.20
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
e0ba327 caused a regression - this simple polygon will now crash during triangulation:
0 0
-5 -3e-10
-10 -2e-10
-10 -4
0 -4
From what I understand,
Edgemaintains invariant that p1.y < p2.y and in case p1.y == p2.y then p1.x < p2.x. However if the 1e10 tolerance is used for comparison of Y coordinates, this invariant is broken for the second edge and the subsequent code crashes later during triangulation.I would therefore suggest rolling back that commit...
The text was updated successfully, but these errors were encountered: