Skip to Content.
Sympa Menu

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

Subject: CGAL users discussion list

List archive

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


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

Sorry, I should be explicit about my questions.



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 


The code in question is:

void move_26(Delaunay* const D3,
             Cell_handle one_three_simplex,
             unsigned neighbor_index,
             Cell_handle three_one_simplex) noexcept {
  // Preconditions
  CGAL_triangulation_precondition((dimension() == 3)
                                   && (0 <= neighbor_index)
                                   && (neighbor_index < 4));
  CGAL_triangulation_precondition(one_three_simplex.has_neighbor
                                  (three_one_simplex));
  CGAL_triangulation_expensive_precondition(is_cell(one_three_simplex,
                                                    three_one_simplex));

  // Get vertices of common face
  unsigned i1 = (neighbor_index + 1)&3;
  unsigned i2 = (neighbor_index + 2)&3;
  unsigned i3 = (neighbor_index + 3)&3;

  Vertex_handle v1 = one_three_simplex->vertex(i1);
  Vertex_handle v2 = one_three_simplex->vertex(i2);
  Vertex_handle v3 = one_three_simplex->vertex(i3);

  // Bottom vertex is the one opposite of the common face
  Vertex_handle v_bottom = one_three_simplex->vertex(neighbor_index);

  // Likewise, top vertex is one opposite of common face on the neighbor
  Vertex_handle v_top = D3->mirror_vertex(one_three_simplex, neighbor_index);

  // Debugging
  std::cout << "Vertex index 1 is " << i1
            << " with coordinates of " << v1->point() << std::endl;
  std::cout << "Vertex index 2 is " << i2
            << " with coordinates of " << v2->point() << std::endl;
  std::cout << "Vertex index 3 is " << i3
            << " with coordinates of " << v3->point() << std::endl;
  std::cout << "Vertex v_bottom is " << neighbor_index
            << " with coordinates of " << v_bottom->point() << std::endl;
  std::cout << "Vertex v_top is " << neighbor_index
            << " with coordinates of " << v_top->point() << std::endl;


  // Average vertices to get new one in their center
  auto center_of_X = average_coordinates(v1->point().x(),
                                         v2->point().x(),
                                         v3->point().x());
  auto center_of_Y = average_coordinates(v1->point().y(),
                                         v2->point().y(),
                                         v3->point().y());
  auto center_of_Z = average_coordinates(v1->point().z(),
                                         v2->point().z(),
                                         v3->point().z());

  // Debugging
  std::cout << "Average x-coord is " << center_of_X << std::endl;
  std::cout << "Average y-coord is " << center_of_Y << std::endl;
  std::cout << "Average z-coord is " << center_of_Z << std::endl;

  // Timeslices of v1, v2, and v3 should be same
  CGAL_triangulation_precondition(v1->info() == v2->info());
  CGAL_triangulation_precondition(v1->info() == v3->info());

  // Insert new vertex
  // Vertex_handle v_center = D3->insert(Point(center_of_X,
  //                                                  center_of_Y,
  //                                                  center_of_Z));
  Point p = Point(center_of_X, center_of_Y, center_of_Z);
  Vertex_handle v_center = D3->insert(p);

  // Assign a timeslice to the new vertex
  auto timeslice = v1->info();
  std::cout << "Timeslice is " << timeslice << std::endl;
  v_center->info() = timeslice;
  std::cout << "Inserted vertex " << v_center->point()
            << " with timeslice " << v_center->info()
            << std::endl;

  // Get neighbors
  Cell_handle neighbor_13_1 = one_three_simplex->neighbor(i1);
  Cell_handle neighbor_13_2 = one_three_simplex->neighbor(i2);
  Cell_handle neighbor_13_3 = one_three_simplex->neighbor(i3);
  Cell_handle neighbor_31_1 = three_one_simplex->neighbor(i1);
  Cell_handle neighbor_31_2 = three_one_simplex->neighbor(i2);
  Cell_handle neighbor_31_3 = three_one_simplex->neighbor(i3);

  // Delete old cells
  D3->tds().delete_cell(one_three_simplex);
  D3->tds().delete_cell(three_one_simplex);

  // Create new ones
  Cell_handle bottom_12 = D3->tds().create_cell(v1, v_center, v2, v_bottom);
  Cell_handle bottom_23 = D3->tds().create_cell(v2, v_center, v3, v_bottom);
  Cell_handle bottom_31 = D3->tds().create_cell(v3, v_center, v1, v_bottom);
  Cell_handle top_12 = D3->tds().create_cell(v1, v_center, v2, v_top);
  Cell_handle top_23 = D3->tds().create_cell(v2, v_center, v3, v_top);
  Cell_handle top_31 = D3->tds().create_cell(v3, v_center, v1, v_top);

  // Set neighbors for bottom_12
  bottom_12->set_neighbor(bottom_12->index(v_center), neighbor_13_3);
  bottom_12->set_neighbor(bottom_12->index(v1), bottom_23);
  bottom_12->set_neighbor(bottom_12->index(v2), bottom_31);
  bottom_12->set_neighbor(bottom_12->index(v_bottom), top_12);

  // Set neighbors for bottom_23
  bottom_23->set_neighbor(bottom_23->index(v_center), neighbor_13_1);
  bottom_23->set_neighbor(bottom_23->index(v2), bottom_31);
  bottom_23->set_neighbor(bottom_23->index(v3), bottom_12);
  bottom_23->set_neighbor(bottom_23->index(v_bottom), top_23);

  // Set neighbors for bottom_31
  bottom_31->set_neighbor(bottom_31->index(v_center), neighbor_13_2);
  bottom_31->set_neighbor(bottom_31->index(v3), bottom_12);
  bottom_31->set_neighbor(bottom_31->index(v1), bottom_23);
  bottom_31->set_neighbor(bottom_31->index(v_bottom), top_31);

  // Set neighbors for top_12
  top_12->set_neighbor(top_12->index(v_center), neighbor_31_3);
  top_12->set_neighbor(top_12->index(v1), top_23);
  top_12->set_neighbor(top_12->index(v2), top_31);
  top_12->set_neighbor(top_12->index(v_top), bottom_12);

  // Set neighbors for top_23
  top_23->set_neighbor(top_23->index(v_center), neighbor_31_1);
  top_23->set_neighbor(top_23->index(v2), top_31);
  top_23->set_neighbor(top_23->index(v3), top_12);
  top_23->set_neighbor(top_23->index(v_top), bottom_23);

  // Set neighbors for top_31
  top_31->set_neighbor(top_31->index(v_center), neighbor_31_2);
  top_31->set_neighbor(top_31->index(v3), top_12);
  top_31->set_neighbor(top_31->index(v1), top_23);
  top_31->set_neighbor(top_31->index(v_top), bottom_31);
}  // move_26()


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