포인트 삽입 후 CGAL Delaunay 삼각 측량에서 Cell_handle의 안전한 사용

Question

CGAL Delaunay 삼각 측량 데이터 구조를 사용할 알고리즘을 작성할 계획입니다. 기본적으로 삼각형 분할에 일부 지점을 삽입하고 일부 셀에 대한 참조를 저장 한 다음 다른 삽입을해야합니다.

삼각 측량에 새 포인트를 삽입 한 후 무효화되지 않은 셀에 대한 참조를 어떻게 저장할 수 있습니까?

Cell_handle은 내부 구조체에 대한 포인터 일 뿐이므로 내부 컨테이너를 다시 할당하기 때문에 저장하는 것이 위험합니다. 반면에 Cell_handle에서 인덱스를 저장하는 Triangulation_3 인터페이스에서는 아무 것도 볼 수 없습니다.

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; 
} 

이 코드는 체계적으로 충돌하지만, 나는 10000 newP을 변경하면이 나에게 정말 이상하다,이 코드는 마술처럼 작동합니다.

누군가이 문제를 해결하는 방법을 설명해 주시겠습니까?

Answer 1

새 점을 삽입하는 동안 셀이 사라질 수 있으므로 저장 한 핸들 은 예상 한 것을 가리 키지 않습니다.

내부 컨테이너의 셀을 내부적으로 생성하고 제거하는 삼각 측량 계층을 사용하기 때문에 충돌이 발생합니다. CGAL :: Delaunay_triangulation_3을 사용하면 충돌이 발생하지 않습니다.

문제가 있으면 Vertex_handleS의 4 중주를 저장하고 is_cell 함수 (here에 설명되어 있음)를 사용해야합니다.

Answer 2

실제로, 세포는 삽입시 사라질 수있다. find_conflicts() 함수를 사용하여 삽입에 의해 삭제 될 셀을 찾을 수 있으므로 관련 셀프 관련 항목을 업데이트 할 수 있습니다.