Line结构体线段列表按连通性排序的高效实现方法

核心思路 #

通过哈希表建立线段端点的快速索引，避免暴力迭代匹配，整个流程每个线段仅需处理1次，均摊时间复杂度为O(n)，远优于原暴力方案。

实现步骤 #

• 预处理阶段：构建两个哈希映射，endToLine的键为线段终点EndPos，值为对应线段的索引/引用；startToLine的键为线段起点StartPos，值为对应线段的索引/引用。同时创建访问标记数组，记录线段是否已被整理到结果中。
• 查找段首：遍历所有未访问的线段，若某条线段的StartPos不存在于endToLine映射中，说明没有其他线段的终点可以对接它的起点，这条线段就是一个独立连续段的开头。
• 拼接连续段：找到段首后，将其标记为已访问并加入结果列表，以段首的EndPos作为当前对接点，从startToLine中查找是否存在起点等于当前对接点的线段。如果存在则将该线段标记为已访问、加入结果列表，更新对接点为该线段的EndPos，重复该过程直到找不到可对接的线段为止。
• 处理剩余线段：如果遍历完所有段首后仍有未访问的线段，说明这些线段构成了首尾相接的闭合环，任选其中一条作为起点按照上述拼接逻辑处理即可。

示例代码（C++） #

#include <vector>
#include <unordered_map>
#include <functional>
#include <cmath>

// 假设Vector的定义如下，需自定义哈希和相等判断
struct Vector {
    float x, y;
    bool operator==(const Vector& other) const {
        // 浮点型需加精度阈值，避免精度丢失导致匹配失败
        return fabs(x - other.x) < 1e-6 && fabs(y - other.y) < 1e-6;
    }
};

// 自定义Vector的哈希函数
struct VectorHash {
    size_t operator()(const Vector& v) const {
        return std::hash<float>()(v.x) ^ (std::hash<float>()(v.y) << 1);
    }
};

struct Line {
    Vector StartPos;
    Vector EndPos;
};

std::vector<Line> sortLinesToContinuous(std::vector<Line> originalLines) {
    int n = originalLines.size();
    std::unordered_map<Vector, int, VectorHash> endToLine, startToLine;
    std::vector<bool> visited(n, false);
    std::vector<Line> result;
    result.reserve(n);

    // 预处理构建哈希映射
    for (int i = 0; i < n; i++) {
        endToLine[originalLines[i].EndPos] = i;
        startToLine[originalLines[i].StartPos] = i;
    }

    // 先处理所有非闭合的独立段
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        // 判断是否是段首：没有其他线段的终点等于当前线段的起点
        if (endToLine.count(originalLines[i].StartPos) == 0) {
            int currIdx = i;
            while (currIdx != -1 && !visited[currIdx]) {
                visited[currIdx] = true;
                result.push_back(originalLines[currIdx]);
                // 找下一个可对接的线段
                Vector nextStart = originalLines[currIdx].EndPos;
                currIdx = startToLine.count(nextStart) ? startToLine[nextStart] : -1;
            }
        }
    }

    // 处理剩余的闭合环线段
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int currIdx = i;
            int startIdx = i;
            do {
                visited[currIdx] = true;
                result.push_back(originalLines[currIdx]);
                Vector nextStart = originalLines[currIdx].EndPos;
                currIdx = startToLine[nextStart];
            } while (currIdx != startIdx && !visited[currIdx]);
        }
    }

    return result;
}

注意事项 #

• 如果存在多个线段共享同一个终点/起点的情况（即一个端点对应多条线段），可将哈希映射的值改为vector<int>存储所有对应线段的索引，拼接时按需选择即可。

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