三角形網格上的CGAL插值卡住

Question

要從一組散亂點（例如，將它們網格化到規則網格）內插，使用Delaunay_triangulation_2構建三角形網格，使用natural_neighbor_coordinates_2（）和linear_interpolation（）進行插值。

我遇到的一個問題是，當輸入點來自某些常規網格時，插值過程可能會在某個輸出位置「卡住」：進程被natural_neighbor_coordinates_2（）佔用，但它永遠不會返回。如果隨機噪聲被添加到輸入點的座標上，它將通過。

不知道是否有人也有這個問題，解決方案是什麼。添加隨機噪聲是可以的，但會影響插值的準確性。

插值的腳本如下（我使用的犰狳矩陣）

typedef CGAL::Exact_predicates_inexact_constructions_kernel K; 
typedef K::FT           Coord_type; 
Delaunay_triangulation T; 
arma::fmat points = ... ; //matrix saving point coordinates and function value 
float output_x=...,output_y=...; //location for interpolation 
std::map<Point, Coord_type, K::Less_xy_2> function_values; 
// build mesh 
for (long long i=0;i<points.n_cols;i++) 
{ 
    K::Point_2 p(points(0,i),points(1,i)); 
    T.insert(p); 
    function_values.insert(std::make_pair(p,points(2,i))); 
} 
// interpolate 
K::Point_2 p(output_x,output_y); 
std::vector< std::pair< Point, Coord_type > > coords; 
Coord_type norm = CGAL::natural_neighbor_coordinates_2(T, p,   std::back_inserter(coords)).second; 
Coord_type res = CGAL::linear_interpolation(coords.begin(), coords.end(), norm, Value_access(function_values)); //res is the interpolation result. 

Answer 1

這讓我想起一個問題與random_polygon_2（）被卡住，如果點對齊，這裏討論： http://cgal-discuss.949826.n4.nabble.com/random-polygon-2-gets-stuck-possible-CGAL-bug-td4659470.html

我建議嘗試用Sebastien的答案中的一組點來運行你的代碼。你的問題也可能與點對齊有關（只是猜測）。