CGAL RTree处理39,651,210个2D点时内存暴涨问题及优化请求

针对你用CGAL Range Tree处理3900多万2D点时内存暴涨的问题，以下是几个切实可行的优化方向：

1. 替换为空间效率更高的索引结构 #

CGAL的Range_tree_2属于范围树结构，空间复杂度为O(n log n)，对于千万级点云会产生大量冗余的分层区间节点，这是内存暴涨的核心原因。建议替换为以下两种更适合大规模数据的结构：

方案A：使用CGAL Kd-tree #

Kd-tree的空间复杂度为O(n)，内存占用远低于范围树，且支持高效的区间查询：

typedef CGAL::Exact_predicates_inexact_constructions_kernel EPIC;
typedef EPIC::Point_2 Point_2;
typedef CGAL::Search_traits_2<EPIC> SearchTraits;
typedef CGAL::Kd_tree<SearchTraits> KdTree;

// 直接存储Point_2，无需键值对
std::vector<Point_2> points;
points.reserve(numPoints);

for (size_t pointIndex = 0; pointIndex < numPoints; ++pointIndex) {
    const size_t offset = pointIndex * pointDimension;
    points.emplace_back(pPoints[offset], pPoints[offset + 1]);
}

// 构建Kd-tree，内存占用仅为点集本身加少量节点开销
KdTree kdTree(points.begin(), points.end());

// 区间查询示例
typedef CGAL::Rectangle_2<EPIC> QueryRect;
QueryRect queryRect(xMin, xMax, yMin, yMax);
CGAL::Range_search<SearchTraits> search(kdTree, queryRect);

for (const auto& point : search) {
    // 处理查询到的点
}

方案B：使用CGAL RTree（5.0+版本支持） #

CGAL的RTree实现基于R树结构，空间利用率高，支持批量插入，内存占用接近O(n)：

typedef CGAL::Exact_predicates_inexact_constructions_kernel EPIC;
typedef EPIC::Point_2 Point_2;
// 2维RTree，直接存储Point_2
typedef CGAL::RTree<Point_2, CGAL::Dimension_tag<2>> RTree;

RTree rTree;
rTree.reserve(numPoints); // 预分配内存避免扩容开销

for (size_t pointIndex = 0; pointIndex < numPoints; ++pointIndex) {
    const size_t offset = pointIndex * pointDimension;
    rTree.insert(Point_2(pPoints[offset], pPoints[offset + 1]));
}

// 边界框区间查询示例
CGAL::Bbox_2 queryBbox(xMin, yMin, xMax, yMax);
std::vector<Point_2> queryResults;
rTree.search(std::back_inserter(queryResults), queryBbox);

2. 若必须保留Range Tree的优化 #

如果业务上必须使用Range Tree，可通过以下方式降低内存：

• 去除冗余键值对：改用Range_tree_traits_2而非Range_tree_map_traits_2，直接存储Point_2作为元素，不需要额外的布尔值占位：

  typedef CGAL::Range_tree_traits_2<EPIC, Point_2> Traits;
  typedef CGAL::Range_tree_2<Traits> Range_tree_2;
  
  std::vector<Point_2> rTreeInput;
  rTreeInput.reserve(numPoints);
  // 填充Point_2逻辑...
  
  // 使用移动语义转移vector所有权，避免拷贝
  Range_tree_2 rTree(std::move(rTreeInput));
  

• 启用内存池优化：编译CGAL时开启内存池相关编译宏（如CGAL_USE_MEMORY_POOL），减少动态内存分配带来的碎片和额外开销。

3. 其他通用优化 #

• 移除代码中重复定义的std::vector<Key> rTreeInput;，避免不必要的内存申请。
• 优先使用emplace_back构造Point_2，减少临时对象的内存开销。

内容的提问来源于stack exchange，提问作者user13583700