寻求合并简化重合折线的经典算法或可用JavaScript实现

问题说明 #

我需要实现从线段列表生成折线集合的功能，核心目标是尽可能延长每条折线。现有一个Moly多折线组类，支持通过Add方法添加折线组，调用reduce方法完成折线合并。

示例输入输出 #

输入线段列表：

segments=[
 ['AxAy','BxBy'],
 ['BxBy','CxCy'],
 ...
 ['LxLy','MxMy'],
 ['NxNy','MxMy'],

 ['QxQy','RxRy'],
 ['RxRy','SxSy']
]

使用方式：

var moly= new Moly([segments.shift()])
segments.map(segment=>moly.Add(new Moly(segment)))
moly.reduce()

输出合并后的折线：

[
  ['AxAy','BxBy','CxCy',...,'LxLy','MxMy','NxNy'],
  ['QxQy','RxRy','SxSy']
]

当前代码能生成可用结果，但因调用频次极高，需要找到该经典问题的对应算法，或更高效的现成JavaScript实现。

我正在测试的代码 #

function Poly(polylines){
    this.polylines=[]
    for (i=0;i<polylines.length;i++)
        this.Add(polylines[i])
    return this
}

Poly.prototype.Add=function (polyline){
    this.polylines.push(polyline.map(JSON.stringify))
}

Poly.prototype.Reduce=function(){
    for (var i=0;i<this.polylines.length;i++){
        this.polylines=this.polylines.sort((a,b)=>b.length - a.length)
        for (var j=i+1;j<this.polylines.length;j++)
            this.Improve(i,j)
    }
    this.polylines=this.polylines.filter(p=>p.length>0)
}

Poly.prototype.Draw=function(){
    return this.polylines.map(polyline=>polyline.map(JSON.parse))
}

Poly.prototype.Improve=function(I,J){
    var a=this.polylines[I]
    var b=this.polylines[J]
    for (var i=0;i<a.length;i++)
        if (a[i]===b[0] || a[i]===b[b.length-1]){
            if (a[i]===b[b.length-1])
                b.reverse()
            if (i===0)
                a.reverse()
            if (i===0 || i===a.length-1){
                a.pop()
                this.polylines[I]=a.concat(b)
                this.polylines[J]=[]
                return true
            }

            if (i-1+b.length > a.length){
                this.polylines[I]=a.slice(0,i-1).concat(b)
                this.polylines[J]=a.slice(i)
                return true
            }
            if (a.length-i-1+b.length > a.length){
                this.polylines[I]=b.reverse().concat(a.slice(i+1))
                this.polylines[J]=a.slice(0,i+1)
                return true
            }  
        }
    return false
}
                
module.exports=Poly

对应经典算法与优化实现 #

这个问题本质是无向图的路径合并：每个线段是图中的边，坐标点是图的节点，我们需要找出所有的欧拉路径片段。高效实现的核心是用哈希表记录每个节点的邻接折线端点，避免暴力遍历，大幅提升合并效率。

优化后的JavaScript实现 #

class PolylineMerger {
    constructor(segments = []) {
        this.polylines = [];
        // 哈希表：节点 -> 折线的端点索引（0=起点，1=终点）及折线在polylines中的位置
        this.nodeMap = new Map();
        segments.forEach(seg => this.addSegment(seg));
    }

    // 添加单条线段
    addSegment(segment) {
        const [start, end] = segment.map(JSON.stringify);
        const polyline = [start, end];
        this.polylines.push(polyline);
        const idx = this.polylines.length - 1;
        // 更新节点映射
        this._updateNodeMap(start, idx, 0);
        this._updateNodeMap(end, idx, 1);
    }

    // 添加折线组
    addPolyline(polyline) {
        const strPoly = polyline.map(JSON.stringify);
        this.polylines.push(strPoly);
        const idx = this.polylines.length - 1;
        this._updateNodeMap(strPoly[0], idx, 0);
        this._updateNodeMap(strPoly.at(-1), idx, 1);
    }

    _updateNodeMap(node, polyIdx, endType) {
        if (!this.nodeMap.has(node)) {
            this.nodeMap.set(node, []);
        }
        this.nodeMap.get(node).push({ polyIdx, endType });
    }

    // 合并折线
    reduce() {
        // 遍历所有节点，处理有连接关系的折线
        for (const [node, connections] of this.nodeMap) {
            while (connections.length >= 2) {
                const conn1 = connections.shift();
                const conn2 = connections.shift();
                if (conn1.polyIdx === conn2.polyIdx) continue;

                const poly1 = this.polylines[conn1.polyIdx];
                const poly2 = this.polylines[conn2.polyIdx];
                if (!poly1 || !poly2) continue;

                let merged;
                // 处理不同的连接情况
                if (conn1.endType === 0 && conn2.endType === 0) {
                    // poly1起点连poly2起点，反转poly2后拼接
                    merged = poly2.reverse().concat(poly1.slice(1));
                } else if (conn1.endType === 0 && conn2.endType === 1) {
                    // poly1起点连poly2终点，直接拼接poly1到poly2
                    merged = poly2.concat(poly1.slice(1));
                } else if (conn1.endType === 1 && conn2.endType === 0) {
                    // poly1终点连poly2起点，直接拼接
                    merged = poly1.concat(poly2.slice(1));
                } else {
                    // poly1终点连poly2终点，反转poly2后拼接
                    merged = poly1.concat(poly2.reverse().slice(1));
                }

                // 更新polylines：标记原折线为null，添加新折线
                this.polylines[conn1.polyIdx] = null;
                this.polylines[conn2.polyIdx] = null;
                this.polylines.push(merged);
                const newIdx = this.polylines.length - 1;

                // 更新节点映射：移除原折线的端点，添加新折线的端点
                this._removeNodeConnections(conn1.polyIdx);
                this._removeNodeConnections(conn2.polyIdx);
                this._updateNodeMap(merged[0], newIdx, 0);
                this._updateNodeMap(merged.at(-1), newIdx, 1);

                // 将新折线的端点连接放回队列，继续合并
                const startConn = this.nodeMap.get(merged[0]);
                startConn.push({ polyIdx: newIdx, endType: 0 });
                const endConn = this.nodeMap.get(merged.at(-1));
                endConn.push({ polyIdx: newIdx, endType: 1 });
            }
        }

        // 过滤掉已合并的空折线，解析回原始格式
        this.polylines = this.polylines.filter(p => p !== null).map(p => p.map(JSON.parse));
    }

    _removeNodeConnections(polyIdx) {
        const poly = this.polylines[polyIdx];
        if (!poly) return;
        const start = poly[0];
        const end = poly.at(-1);
        // 移除该折线在节点映射中的记录
        this.nodeMap.set(start, this.nodeMap.get(start).filter(c => c.polyIdx !== polyIdx));
        this.nodeMap.set(end, this.nodeMap.get(end).filter(c => c.polyIdx !== polyIdx));
    }
}

// 使用示例
// const segments = [['AxAy','BxBy'], ['BxBy','CxCy'], ['NxNy','MxMy'], ['LxLy','MxMy'], ['QxQy','RxRy'], ['RxRy','SxSy']];
// const merger = new PolylineMerger(segments);
// merger.reduce();
// console.log(merger.polylines);

优化点说明 #

• 使用**哈希表（Map）**记录节点与折线端点的关联，避免暴力遍历所有折线对，时间复杂度从O(n²)优化为接近O(n)
• 合并时直接处理节点的连接关系，无需重复排序，减少不必要的计算
• 合并后及时更新节点映射，确保后续合并能正确找到可连接的折线

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