如何从三角化三角形数组中提取外围边界线？

核心思路非常直接：内部边必然被两个三角形共享，而外围边界线只会属于一个三角形。基于这个特性，我们可以通过统计每条边的出现次数来快速筛选出外围边，具体步骤如下：

1. 标准化边的表示 #

一条边的两个顶点顺序不影响其本质（比如A→B和B→A是同一条边），所以需要统一边的存储格式，避免重复统计。比如可以按顶点坐标的字典序排序：

• 先比较x坐标，x值小的顶点在前；
• x相等则比较y坐标，y值小的在前；
• y相等再比较z坐标，z值小的在前。
  经过标准化后，同一条边无论顶点顺序如何，都会被表示为同一个键。

2. 统计边的出现频次 #

用映射表（哈希表或有序映射）存储每条标准化后的边，键是标准化的边对象，值是这条边出现的次数。遍历所有三角形的三条边，每条边标准化后更新映射表中的计数。

3. 筛选外围边界线 #

遍历映射表，提取所有出现次数为1的边，这些就是你需要的外围边界线。

C++ 实现示例 #

假设你已经定义了Vec3（顶点）、triangle（包含三个Vec3顶点）和line（包含两个Vec3顶点）结构体：

#include <vector>
#include <map>
#include <cmath>

struct Vec3 {
    float x, y, z;
    
    // 浮点数精度比较，避免精度误差导致判断错误
    bool operator==(const Vec3& other) const {
        const float eps = 1e-6;
        return fabs(x - other.x) < eps &&
               fabs(y - other.y) < eps &&
               fabs(z - other.z) < eps;
    }
};

// 为Vec3实现比较运算符，用于map的键排序
bool operator<(const Vec3& a, const Vec3& b) {
    const float eps = 1e-6;
    if (fabs(a.x - b.x) > eps) return a.x < b.x;
    if (fabs(a.y - b.y) > eps) return a.y < b.y;
    return a.z < b.z;
}

struct triangle {
    Vec3 v1, v2, v3;
};

struct line {
    Vec3 p1, p2;
    line(Vec3 a, Vec3 b) : p1(a), p2(b) {}
};

// 标准化边的函数
std::pair<Vec3, Vec3> normalizeEdge(const Vec3& a, const Vec3& b) {
    return a < b ? std::make_pair(a, b) : std::make_pair(b, a);
}

std::vector<line> GetPerimeter(std::vector<triangle> triangles) {
    std::map<std::pair<Vec3, Vec3>, int> edgeCount;

    // 遍历所有三角形，统计边的出现次数
    for (const auto& tri : triangles) {
        auto e1 = normalizeEdge(tri.v1, tri.v2);
        auto e2 = normalizeEdge(tri.v2, tri.v3);
        auto e3 = normalizeEdge(tri.v3, tri.v1);
        edgeCount[e1]++;
        edgeCount[e2]++;
        edgeCount[e3]++;
    }

    std::vector<line> perimeter;
    // 筛选出现次数为1的边（外围边界）
    for (const auto& entry : edgeCount) {
        if (entry.second == 1) {
            perimeter.emplace_back(entry.first.first, entry.first.second);
        }
    }

    return perimeter;
}

补充说明 #

• 时间复杂度：O(N)（使用哈希表时）或O(N logM)（使用有序映射时，M为边的总数），其中N是三角形的数量。这个效率远高于暴力递归方案。
• 浮点数精度：如果顶点坐标是浮点数，必须用epsilon阈值进行比较，不能直接用==，否则会因为精度误差导致同一条边被多次统计。

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