CGAL users discussion list

[Adam Getchell <>]

On Jun 22, 2015, at 4:52 PM, Adam Getchell <> wrote:

Hello all,

I might have missed it, but I’m looking for a function that finds the index of a neighboring cell with respect to the first cell.

The catch is I have just created these cells.

I can use something like:

int neighbor_index;

first->has_neighbor(second, neighbor_index)

But that only works when adjacency relationships are set. (When they are not set, these ints seem to point to memory addresses.)

I’m working on the opposite problem, setting adjacencies by finding cells with overlapping sets of vertices.

So far I’m using std::set_difference and set::union from <algorithm> to do this by brute force.

That is, given a list of newly created 3D cells, pairwise find those that have exactly 3 vertices in common using set::union, and then use set_adjacency(first, neighbor_index, second, neighbor_mirror_index) to set adjacency relations.

(In higher dimensions I would change the criteria accordingly.)

BTW, it seems these want sorted ranges. Are Vertex_handles sortable (is operator< defined)?

I found that std::sort() works with a vector of Vertex_handles.

Without it, of course, std::set_difference does not work correctly.

This plan of attack seems to be working. Now, I just have to fix cell orientations.

auto find_disjoint_index(Cell_handle const first,

                         Cell_handle const second) noexcept {

  std::vector<Vertex_handle> first_vertices;

  std::vector<Vertex_handle> second_vertices;

  std::vector<Vertex_handle> disjoint_vector;

  for (auto i = 0; i < 4; ++i) {

    first_vertices.emplace_back(first->vertex(i));

    second_vertices.emplace_back(second->vertex(i));

  }

  // Sort vectors

  std::sort(first_vertices.begin(), first_vertices.end());

  std::sort(second_vertices.begin(), second_vertices.end());

  // Debugging

  // std::cout << "Cell 1 has the following vertices: " << std::endl;

  // for (auto i : first_vertices) {

  //   std::cout << i->point() << std::endl;

  // }

  // std::cout << "Cell 2 has the following vertices: " << std::endl;

  // for (auto i: second_vertices) {

  //   std::cout << i->point() << std::endl;

  // }

  // Find difference

  std::set_difference(first_vertices.begin(), first_vertices.end(),

                      second_vertices.begin(), second_vertices.end(),

                      std::inserter(disjoint_vector, disjoint_vector.begin()));

  CGAL_triangulation_precondition(disjoint_vector.size() == 1);

  // Debugging

  // std::cout << "The following vertices are disjoint between cell 1 & 2: "

  //           << std::endl;

  // for (auto i : disjoint_vector) {

  //   std::cout << i->point() << std::endl;

  // }

  auto result = disjoint_vector.front();

  // Debugging

  // std::cout << "We're going to return the vertex " << result->point()

  //           << " with an index of " << first->index(result) << std::endl;

  return first->index(result);

}  // find_disjoint_index()