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.

Sign up for GitHub

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

Jump to bottom

Infinite Loop in Conform Mode #165

Closed
renvenuti opened this issue Nov 29, 2023 · 4 comments
Closed

Infinite Loop in Conform Mode #165

renvenuti opened this issue Nov 29, 2023 · 4 comments
Labels
wrong input Caused by wrong input to CDT

Comments

@renvenuti
Copy link

Hi,
first of all congratulations on the project.
I would like to report a problem:

using Delaunay Conform Mode with vertices and edges we found an infinite loop in the KDTree insert function.
below the call stack:

Test.dll!CDT::KDTree::KDTree<double,32,32,32>::insert(const unsigned __int64 & iPoint, const std::vector<CDT::V2d<double>,std::allocator<CDT::V2d<double>>> & points) Line 146	C++
Test.dll!CDT::LocatorKDTree<double,32,32,32>::addPoint(const unsigned __int64 i, const std::vector<CDT::V2d<double>,std::allocator<CDT::V2d<double>>> & points) Line 50	C++
Test.dll!CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::tryAddVertexToLocator(const unsigned __int64 v) Line 2078	C++
Test.dll!CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::insertVertex_FlipFixedEdges(unsigned __int64 iV1) Line 1085	C++
Test.dll!CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::conformToEdgeIteration(CDT::Edge edge, const std::vector<CDT::Edge,std::allocator<CDT::Edge>> & originals, unsigned short overlaps, std::vector<std::tuple<CDT::Edge,std::vector<CDT::Edge,std::allocator<CDT::Edge>>,unsigned short>,std::allocator<std::tuple<CDT::Edge,std::vector<CDT::Edge,std::allocator<CDT::Edge>>,unsigned short>>> & remaining) Line 844	C++
Test.dll!CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::conformToEdge(CDT::Edge edge, std::vector<CDT::Edge,std::allocator<CDT::Edge>> originals, unsigned short overlaps, std::vector<std::tuple<CDT::Edge,std::vector<CDT::Edge,std::allocator<CDT::Edge>>,unsigned short>,std::allocator<std::tuple<CDT::Edge,std::vector<CDT::Edge,std::allocator<CDT::Edge>>,unsigned short>>> & remaining, double conformClosedPointsTolerance, unsigned int conformMaxLoop) Line 928	C++
Test.dll!CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::conformToEdges<std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<CDT::Edge>>>,unsigned __int64 (__cdecl*)(CDT::Edge const &),unsigned __int64 (__cdecl*)(CDT::Edge const &)>(std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<CDT::Edge>>> first, const std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<CDT::Edge>>> last, unsigned __int64(*)(const CDT::Edge &) getStart, unsigned __int64(*)(const CDT::Edge &) getEnd, double conformClosedPointsTolerance, unsigned int conformMaxLoop) Line 779	C++
Test.dll!CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::conformToEdges(const std::vector<CDT::Edge,std::allocator<CDT::Edge>> & edges, double conformClosedPointsTolerance, unsigned int conformMaxLoop) Line 373	C++
Test.dll!CdTriTriangulation::Triangulate(const std::vector<CdTriPoint,std::allocator<CdTriPoint>> & points, const std::vector<CdTriPolyline,std::allocator<CdTriPolyline>> & polylines, const CdTriConfig & config) Line 55	C++

if (pd.size() < NumVerticesInLeaf) // NumVerticesInLeaf == 32 and pd.size == 32 (loop condition)
   {
      pd.push_back(iPoint);
      return;
   }

if you want i can send a file who caused it

Thanks in Advance
Renzo Venuti
@artem-ogre
Copy link
Owner

Thank you for reporting the issue. Yes, I definitely need a minimal reproducer to start the investigation.

@renvenuti
Copy link
Author

renvenuti commented Nov 29, 2023 via email

@artem-ogre
Copy link
Owner

artem-ogre commented Nov 29, 2023 •
edited

The input is incorrect because it contains duplicate vertices with coordinates 1525723.0400 5021752.2100. CDT provides helpers to detect and fix duplicate vertices (please see other similar issues for more details). After fixing the duplicates the latest master code can build both constraint and conforming triangulations.

Also latest code in master throws an exception if duplicate vertices are provided in input (it does for your input).

@artem-ogre artem-ogre added the wrong input Caused by wrong input to CDT label Nov 29, 2023
@renvenuti
Copy link
Author

renvenuti commented Nov 29, 2023 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
wrong input Caused by wrong input to CDT
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@artem-ogre @renvenuti