如何基于相邻顶点间距筛选随机顶点列表？（C++&CGAL）

一、先解决顶点有序化问题 #

原始顶点随机存储的情况下，必须先按交线的连续路径排序，否则相邻点的距离计算没有意义。这里提供两种适配CGAL的实现方式：

方式1：基于Kd树构建交线路径 #

把相交点看作无向图，通过Kd树快速查找相邻点，构建有序路径：

#include <CGAL/Search_traits_3.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <vector>
#include <unordered_set>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Search_traits_3<Kernel> Traits;
typedef CGAL::Kd_tree<Traits> Kd_tree;

std::vector<Point_3> order_intersection_points(const std::vector<Point_3>& points) {
    if (points.empty()) return {};

    Kd_tree kd_tree(points.begin(), points.end());
    std::vector<Point_3> ordered;
    std::unordered_set<int> visited;
    int current_idx = 0; // 从第一个点启动路径构建

    while (visited.size() < points.size()) {
        ordered.push_back(points[current_idx]);
        visited.insert(current_idx);

        // 查找最近的2个邻点（排除自身）
        std::vector<std::pair<Point_3, int>> neighbors;
        kd_tree.search(std::back_inserter(neighbors), points[current_idx], CGAL::Emptyset(), 2);

        int next_idx = -1;
        for (const auto& neighbor : neighbors) {
            auto it = std::find(points.begin(), points.end(), neighbor.first);
            if (it != points.end()) {
                int idx = std::distance(points.begin(), it);
                if (!visited.count(idx)) {
                    next_idx = idx;
                    break;
                }
            }
        }

        // 找不到未访问邻点，说明是开放交线的终点，退出循环
        if (next_idx == -1) break;
        current_idx = next_idx;
    }

    return ordered;
}

注意：如果存在多条独立交线，需要遍历未访问点，分别处理每条分支

方式2：直接提取CGAL交线生成的有序点 #

如果是用CGAL的intersection函数生成的交线，很多重载会直接返回有序的曲线段/折线，无需手动排序：

// 假设mesh1、mesh2是你的两个曲面网格
std::vector<CGAL::Object> intersections;
CGAL::intersection(mesh1, mesh2, std::back_inserter(intersections));

std::vector<Point_3> all_intersection_points;
for (const auto& obj : intersections) {
    CGAL::Polyline_3<Kernel> polyline;
    if (CGAL::assign(polyline, obj)) {
        // 折线本身就是有序的，直接提取点
        for (const auto& p : polyline) {
            all_intersection_points.push_back(p);
        }
    }
    CGAL::Segment_3<Kernel> seg;
    if (CGAL::assign(seg, obj)) {
        all_intersection_points.push_back(seg.source());
        all_intersection_points.push_back(seg.target());
    }
}

这个方法更可靠，因为CGAL已经帮你处理了交线的连续性和顺序。

二、有序顶点的筛选实现 #

有序之后，按目标间距过滤的逻辑很直接：

std::vector<Point_3> filter_points_by_target_length(const std::vector<Point_3>& ordered_points, double target_length) {
    if (ordered_points.empty()) return {};

    std::vector<Point_3> filtered;
    filtered.push_back(ordered_points[0]);
    Point_3 last_kept = ordered_points[0];
    const double target_sq = target_length * target_length; // 预计算平方距离，避免开根号提升性能

    for (size_t i = 1; i < ordered_points.size(); ++i) {
        double dist_sq = CGAL::squared_distance(last_kept, ordered_points[i]);
        if (dist_sq >= target_sq) {
            filtered.push_back(ordered_points[i]);
            last_kept = ordered_points[i];
        }
    }

    // 处理闭合交线：如果最后一个点和第一个点过近，移除最后一个点
    if (!filtered.empty() && CGAL::squared_distance(filtered.front(), filtered.back()) < target_sq) {
        filtered.pop_back();
    }

    return filtered;
}

三、更高效的替代方案：直接曲线采样 #

如果交线是连续曲线（比如CGAL返回的Polyline_3或Curve_3），可以跳过密集点生成+筛选的步骤，直接用CGAL的曲线采样功能按目标间距生成点：

#include <CGAL/curve_sampling.h>

std::vector<Point_3> sample_curve_by_target_length(const CGAL::Polyline_3<Kernel>& polyline, double target_length) {
    std::vector<Point_3> sampled_points;
    CGAL::curve_sampling(polyline, std::back_inserter(sampled_points), target_length);
    return sampled_points;
}

这个方法性能更优，因为它直接在曲线上按要求间距采样，无需处理冗余的密集点。

注意事项 #

• 多分支交线要分开处理，避免不同分支的点被错误排序；
• Kernel选择：精度要求高用Exact_predicates_exact_constructions_kernel，追求速度用Exact_predicates_inexact_constructions_kernel。

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