Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Invalid TDS after inserting vertices and creating cells & neighbors

Subject: CGAL users discussion list

List archive

[cgal-discuss] Invalid TDS after inserting vertices and creating cells & neighbors


Chronological Thread 
  • From: Adam Getchell <>
  • To:
  • Subject: [cgal-discuss] Invalid TDS after inserting vertices and creating cells & neighbors
  • Date: Tue, 5 May 2015 18:06:30 -0700

Hello all,

I’m attempting to implement the (2,6) move which may be described pictorially as:


However, it appears that once I insert a new vertex (v_center), the triangulation is re-calculated without taking into account the new cells and neighbors that I create in the following code (starting on line 207) of https://github.com/acgetchell/CDT-plusplus/blob/master/src/S3ErgodicMoves.h 

When I run unit tests, I consistently get:

┌─[adam][Hapkido][±][master ][~/CDT-plusplus]
└─▪ ./build/unittests --gtest_filter=S3ErgodicMoves.MakeA26Move 
Note: Google Test filter = S3ErgodicMoves.MakeA26Move
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from S3ErgodicMoves
[ RUN      ] S3ErgodicMoves.MakeA26Move
Generating universe ...
Pass #1
Fixing foliation....
Pass #2
Fixing foliation....
Pass #3
Fixing foliation....
Pass #4
Fixing foliation....
Pass #5
Fixing foliation....
Pass #6
Fixing foliation....
Pass #7
Fixing foliation....
Classifying simplices....
Valid foliation: true
Delaunay triangulation has 96874 cells.
There are 30144 (3,1) simplices and 36291 (2,2) simplices and 30439 (1,3) simplices.
Number of vertices before = 15268
Random number is 1272
Neighbor 0 is of type 31
Neighbor 1 is of type 22
Neighbor 2 is of type 13
Neighbor 3 is of type 13
(1,3) simplex 1272 is movable.
The neighboring simplex 0 is of type 31
Vertex index 1 is 1 with coordinates of -3.05843 1.64532 1.98468
Vertex index 2 is 2 with coordinates of -2.90759 2.10945 1.75958
Vertex index 3 is 3 with coordinates of -3.10277 2.03405 1.49515
Vertex v_bottom is 0 with coordinates of -2.33325 1.26426 1.39913
Vertex v_top is 0 with coordinates of -3.86226 2.33575 2.15109
Average x-coord is -3.02293
Average y-coord is 1.92961
Average z-coord is 1.74647
Timeslice is 4
Inserted vertex -3.02293 1.92961 1.74647 with timeslice 4
Number of vertices after = 15269
Classifying simplices....
../unittests/S3ErgodicMovesTest.cpp:185: Failure
Value of: T.tds().is_valid()
  Actual: false
Expected: true
Triangulation is invalid.
../unittests/S3ErgodicMovesTest.cpp:197: Failure
Value of: N3_31_after
Expected: is equal to 30146
  Actual: 30149 (of type unsigned long)
(3,1) simplices did not increase by 2.
../unittests/S3ErgodicMovesTest.cpp:200: Failure
Value of: N3_22_after
Expected: is equal to 36291
  Actual: 36287 (of type unsigned long)
(2,2) simplices changed.
../unittests/S3ErgodicMovesTest.cpp:203: Failure
Value of: N3_13_after
Expected: is equal to 30441
  Actual: 30444 (of type unsigned long)
(1,3) simplices did not increase by 2.
[  FAILED  ] S3ErgodicMoves.MakeA26Move (2064 ms)
[----------] 1 test from S3ErgodicMoves (2064 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (2064 ms total)
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] S3ErgodicMoves.MakeA26Move

 1 FAILED TEST

My questions:

1. Is it correct to delete the two old cells before creating the new ones?
2. Is there a way to create a vertex without inserting it into the Delaunay triangulation?
3. If not, is there a way to prevent the Delaunay triangulation from re-triangulating with the newly inserted vertex before other operations are created?
4. What is the correct way to create new cells in a region with older ones?
5. How do I know that I need to change orientation (e.g. line 2097 in https://github.com/CGAL/cgal/blob/master/Triangulation_3/include/CGAL/Triangulation_data_structure_3.h )?

Thanks for any advice!


PNG image




Archive powered by MHonArc 2.6.18.

Top of Page