Безопасное использование Cell_handle в триангуляции CGAL Delaunay после вставки точки

Question

Я планирую написать алгоритм, который будет использовать структуру данных триангуляции CGAL Delaunay. В основном мне нужно вставить какую-то точку в триангуляцию, сохранить ссылку на некоторые ячейки, а затем сделать другую вставку.

Мне интересно, как я могу хранить ссылку на ячейки, которые не являются недействительными после вставки новых точек в триангуляцию?

Мне кажется, что Cell_handle - это просто указатель на внутреннюю структуру, поэтому опасно хранить его из-за перераспределения внутреннего контейнера. С другой стороны, я не вижу пути в интерфейсе Triangulation_3 для хранения индекса из Cell_handle.

typedef CGAL::Exact_predicates_inexact_constructions_kernel K; 
typedef CGAL::Triangulation_vertex_base_3<K>    Vb; 
typedef CGAL::Triangulation_hierarchy_vertex_base_3<Vb> Vbh; 
typedef CGAL::Triangulation_data_structure_3<Vbh>  Tds; 
typedef CGAL::Delaunay_triangulation_3<K,Tds>   Dt; 
typedef CGAL::Triangulation_hierarchy_3<Dt>    Dh; 
typedef Dh::Vertex_iterator Vertex_iterator; 
typedef Dh::Vertex_handle Vertex_handle; 
typedef Dh::Point   Point; 

int main(){ 

    Dh T; 
    for(int i = 0; i < 100; ++i) 
     T.insert(Point(rand()%1000,rand()%1000,rand()%1000)); 

    assert(T.is_valid()); 
    assert(T.number_of_vertices() == 100); 
    assert(T.dimension() == 3); 

    typedef Dh::Cell_iterator CellIterator; 

    std::vector<Dh::Cell_handle> hnd; 
    CellIterator itEnd = T.finite_cells_end(); 
    for(CellIterator it = T.finite_cells_begin(); it!=itEnd; ++it){ 
     const int dist = std::distance(T.cells_begin(),it); 
     hnd.push_back(it); 
    } 

    const int newP(1000); 
    for(int i = 0; i < newP; ++i) 
     T.insert(Point(rand()%1000,rand()%1000,rand()%1000)); 

    int finiteC(0),infiniteC(0); 
    for(int i = 0; i < hnd.size(); ++i){ 
     const int dist = std::distance(T.cells_begin(),hnd[i]); 
     if(T.is_infinite(hnd[i])) 
    ++infiniteC; 
    else 
    ++finiteC; 
    } 
    assert(T.is_valid()); 
    return 0; 
} 

Этот код систематически врезаться, но, и это действительно странно для меня, если я изменю NEWp 10000, этот код волшебно работает.

Может кто-нибудь объяснить мне, как справиться с этой проблемой?

Answer 1

Поскольку ячейка может исчезнуть при вставке новой точки, ручка, которую вы сохранили , не гарантирует указания на то, что вы ожидаете.

У вас есть сбой, потому что вы используете иерархию триангуляции, которая внутренне создает и удаляет ячейки во внутреннем контейнере. Если вы используете CGAL :: Delaunay_triangulation_3, у вас не будет сбоя.

Для вашей проблемы вы должны сохранить квадруплет Vertex_handleS и использовать функцию is_cell (задокументировано here).

Answer 2

Действительно, ячейки могут исчезнуть при вставке. Вы также можете использовать функцию find_conflicts(), чтобы найти ячейки, которые будут удалены с помощью вставки, чтобы вы могли обновлять все, что вы поддерживаете, связанные с ними.