function riverLayout(biases, arcs, causes) { // 记录开始时间 const startTime = new Date(); // 定义常量 const topk = 100; const nodes = []; const edges = []; const circlePadding = 15; const padding = 9; const hardpadding = 4.5; const nodePerWidth = 25; const randomDummyNodes = 1000; const rng = new FixedRandomGenerator(12345); class Graph { constructor() { this.adjacencyList = new Map(); this.vertexCapacity = new Map(); this.isStartPoint = new Set(); this.originalWeights = new Map(); } addVertex(vertex, capacity = Number.MAX_VALUE) { if (!this.adjacencyList.has(vertex)) { this.adjacencyList.set(vertex, []); this.vertexCapacity.set(vertex, capacity); } } setStartPoint(vertex) { this.isStartPoint.add(vertex); } setCapacity(vertex, capacity) { this.vertexCapacity.set(vertex, capacity); } augmentFlow(path, flow) { for (let i = 0; i < path.length; ++i) { this.setCapacity(path[i], this.vertexCapacity.get(path[i]) - flow); } } clearFlow(vertex) { this.setCapacity(vertex, 0); } reduceCapacity(vertex, capacity) { this.vertexCapacity.set( vertex, this.vertexCapacity.get(vertex) - capacity ); } hasVertex(vertex) { return this.adjacencyList.has(vertex); } addEdge(v1, v2, w) { if (!this.adjacencyList.has(v1)) { this.addVertex(v1); } if (!this.adjacencyList.has(v2)) { this.addVertex(v2); } this.adjacencyList.get(v1).push([v2, w]); this.adjacencyList.get(v2).push([v1, w]); this.originalWeights.set(`${v1}-${v2}`, w); this.originalWeights.set(`${v2}-${v1}`, w); } addDirectedEdge(v1, v2, w) { if (!this.adjacencyList.has(v1)) { this.addVertex(v1); } if (!this.adjacencyList.has(v2)) { this.addVertex(v2); } this.adjacencyList.get(v1).push([v2, w]); this.originalWeights.set(`${v1}-${v2}`, w); } addEdgesFrom(edges) { for (const [v1, v2, w] of edges) { this.addEdge(v1, v2, w); } } neighbors(vertex) { return this.adjacencyList.get(vertex); } scaleEdgeWeight(v1, v2, scale) { const edges1 = this.adjacencyList.get(v1); for (let i = 0; i < edges1.length; i++) { if (edges1[i][0] === v2) { edges1[i][1] = this.originalWeights.get(`${v1}-${v2}`) * scale; break; } } const edges2 = this.adjacencyList.get(v2); for (let i = 0; i < edges2.length; i++) { if (edges2[i][0] === v1) { edges2[i][1] = this.originalWeights.get(`${v2}-${v1}`) * scale; break; } } } revertEdgeWeight(v1, v2) { const originalWeight = this.originalWeights.get(`${v1}-${v2}`); const edges1 = this.adjacencyList.get(v1); for (let i = 0; i < edges1.length; i++) { if (edges1[i][0] === v2) { edges1[i][1] = originalWeight; break; } } const edges2 = this.adjacencyList.get(v2); for (let i = 0; i < edges2.length; i++) { if (edges2[i][0] === v1) { edges2[i][1] = originalWeight; break; } } } revertAllEdgeWeights() { for (const [edge, originalWeight] of this.originalWeights) { const [v1, v2] = edge.split("-"); this.revertEdgeWeight(v1, v2); } } findPathsFromMidPoint(vertices, start, flows) { // 找到距离所有起始点最近的中间点 const totalFlow = flows.reduce((sum, flow) => sum + flow, 0); vertices.push(start); flows.push(totalFlow); const midPoint = this.findClosestPointToMultiple(vertices, flows); // 存储所有路径的结果 const paths = []; // 对每个起始点找路径 for (let i = 0; i < vertices.length; i++) { const vertex = vertices[i]; const flow = flows[i]; // 找到从中间点到起始点的路径 const path = i == vertices.length - 1 ? this.findPath(vertex, midPoint, flow) : this.findPath(midPoint, vertex, flow); // 将路径添加到结果中 paths.push(path); } let combinedPaths = JSON.parse(JSON.stringify(paths)); const startPath = combinedPaths[combinedPaths.length - 1]; combinedPaths.pop(); startPath.pop(); combinedPaths = combinedPaths.map((path) => startPath.concat(path)); return { midPoint, paths, combinedPaths, flows }; } dijkstra(start, flow, end = null) { const queue = new PriorityQueue(); const distances = new Map(); const prev = new Map(); for (let node of this.adjacencyList.keys()) { distances.set(node, Infinity); prev.set(node, null); } distances.set(start, 0); queue.enqueue(0, start); while (queue.size() > 0) { const [dist, u] = queue.dequeue(); if (dist > distances.get(u)) continue; if (end !== null && u === end) break; if (!this.adjacencyList.has(u)) continue; for (let [v, weight] of this.adjacencyList.get(u)) { if (this.vertexCapacity.get(v) >= flow) { let newDist = distances.get(u) + weight; if (newDist < distances.get(v)) { distances.set(v, newDist); prev.set(v, u); if (!this.isStartPoint.has(v) || v === end) { queue.enqueue(newDist, v); } } } } } return { distances, prev }; } findClosestPointToMultiple(vertices, flows) { let totalDistances = new Map(); for (let i = 0; i < vertices.length; i++) { let vertex = vertices[i]; let flow = flows[i]; const weight = Math.sqrt(flows[i]); let { distances } = this.dijkstra(vertex, flow); for (let [node, dist] of distances) { totalDistances.set( node, (totalDistances.get(node) || 0) + dist * weight ); } } let minDist = Infinity; let closestPoint = null; for (let [node, dist] of totalDistances) { if ( !this.isStartPoint.has(node) && dist < minDist && this.vertexCapacity.get(node) >= Math.max(...flows) ) { minDist = dist; closestPoint = node; } } return closestPoint; } findPath(start, end, flow = 1) { const { prev } = this.dijkstra(start, flow, end); return this.constructPath(prev, end); } constructPath(prev, end) { const path = []; let at = end; while (at) { path.push(at); at = prev.get(at); } return path.reverse(); } numberOfNodes() { return this.adjacencyList.size; } nodes() { return [...this.adjacencyList.keys()]; } numberOfEdges() { let totalEdges = 0; this.adjacencyList.forEach((neighbors) => { totalEdges += neighbors.length; }); return totalEdges / 2; } edges() { return [].concat( ...this.nodes().map((v1) => this.adjacencyList.get(v1).map((d) => [v1, d[0], d[1]]) ) ); } } class PriorityQueue { constructor() { this.heap = []; } enqueue(value, id) { this.heap.push([value, id]); this.bubbleUp(this.heap.length - 1); } dequeue() { const min = this.heap[0]; const end = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = end; this.bubbleDown(0); } return min; } top() { return this.heap[0]; } size() { return this.heap.length; } bubbleUp(index) { const element = this.heap[index]; while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); const parent = this.heap[parentIndex]; if (element[0] >= parent[0]) break; this.heap[index] = parent; index = parentIndex; } this.heap[index] = element; } bubbleDown(index) { const length = this.heap.length; const element = this.heap[index]; while (true) { let leftChildIndex = 2 * index + 1; let rightChildIndex = 2 * index + 2; let leftChild, rightChild; let swap = null; if (leftChildIndex < length) { leftChild = this.heap[leftChildIndex]; if (leftChild[0] < element[0]) { swap = leftChildIndex; } } if (rightChildIndex < length) { rightChild = this.heap[rightChildIndex]; if ( (swap === null && rightChild[0] < element[0]) || (swap !== null && rightChild[0] < leftChild[0]) ) { swap = rightChildIndex; } } if (swap === null) break; this.heap[index] = this.heap[swap]; index = swap; } this.heap[index] = element; } } // 在直线上移动点 function movePoint(x1, y1, x2, y2, k) { const dx = x2 - x1; const dy = y2 - y1; const length = Math.sqrt(dx * dx + dy * dy); const unitX = dx / length; const unitY = dy / length; const newX = x1 + unitX * k; const newY = y1 + unitY * k; return [newX, newY]; } // 在圆周上移动点 function moveAlongCircle(x, y, cx, cy, k) { const radius = Math.sqrt((x - cx) ** 2 + (y - cy) ** 2); let angle = Math.atan2(y - cy, x - cx); const angleIncrement = k / radius; angle += angleIncrement; const newX = cx + radius * Math.cos(angle); const newY = cy + radius * Math.sin(angle); return [newX, newY]; } // 判断点是否在线段上 function isPointOnLineSegment(x1, y1, x2, y2, px, py) { let crossProduct = (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1); if (crossProduct !== 0) return false; let minX = Math.min(x1, x2); let maxX = Math.max(x1, x2); let minY = Math.min(y1, y2); let maxY = Math.max(y1, y2); return px >= minX && px <= maxX && py >= minY && py <= maxY; } // 判断点是否在矩形内 function isPointInRectangle(x1, y1, x2, y2, px, py) { let minX = Math.min(x1, x2); let maxX = Math.max(x1, x2); let minY = Math.min(y1, y2); let maxY = Math.max(y1, y2); return px >= minX && px <= maxX && py >= minY && py <= maxY; } // 判断线段是否与圆相交 function doesLineIntersectCircle(p1, p2, c, padding) { const { x: x1, y: y1 } = p1; const { x: x2, y: y2 } = p2; const { x: cx, y: cy, size: r } = c; const dx = x2 - x1; const dy = y2 - y1; const A = dy; const B = -dx; const C = dx * y1 - dy * x1; const dist = Math.abs(A * cx + B * cy + C) / Math.sqrt(A * A + B * B); if (dist > r + padding) { return false; } const t = ((cx - x1) * dx + (cy - y1) * dy) / (dx * dx + dy * dy); if (t >= 0 && t <= 1) { return true; } const distP1ToC = Math.sqrt((cx - x1) ** 2 + (cy - y1) ** 2); const distP2ToC = Math.sqrt((cx - x2) ** 2 + (cy - y2) ** 2); return distP1ToC <= r + padding || distP2ToC <= r + padding; } // 寻找瓶颈 function findBottlenecks(circles) { const points = circles.map((d) => [d.x, d.y]).flat(); const delaunay = new d3.Delaunay(points); const halfedges = delaunay.halfedges, triangles = delaunay.triangles; const hull = delaunay.hull; const ret = []; for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = triangles[i]; const tj = triangles[j]; ret.push([ti, tj]); } for (let i = 0; i < hull.length; ++i) { const j = hull[i], k = hull[(i + 1) % hull.length]; if ( getDistance(circles[j], circles[k]) > 5 * (circles[j].size + circles[k].size) ) { continue; } ret.push([j, k]); } return ret; } // 判断两线段是否相交 function doesSegmentIntersect(p1, p2, p3, p4) { function crossProduct(p, q, r) { return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x); } const d1 = crossProduct(p3, p4, p1); const d2 = crossProduct(p3, p4, p2); const d3 = crossProduct(p1, p2, p3); const d4 = crossProduct(p1, p2, p4); if (d1 * d2 < 0 && d3 * d4 < 0) { return true; } return false; } // 判断线段是否与圆集相交 function doesSegmentCrossCircles(p1, p2, circles, padding = hardpadding) { for (let k = 0; k < circles.length; ++k) { if (doesLineIntersectCircle(p1, p2, circles[k], padding)) { return true; } } return false; } // 判断线段是否与矩形集相交 function doesSegmentCrossRects(p1, p2, rects) { for (let { x1, y1, x2, y2 } of rects) { if ( doesSegmentIntersect(p1, p2, { x: x1, y: y1 }, { x: x2, y: y2 }) || doesSegmentIntersect(p1, p2, { x: x1, y: y2 }, { x: x2, y: y1 }) ) { return true; } } return false; } // 判断线段是否与瓶颈相交 function doesSegmentCrossBottlenecks(p1, p2, bottlenecks) { for (let [p3, p4] of bottlenecks) { if ( !isPointOnLineSegment(p3.x, p3.y, p4.x, p4.y, p1.x, p1.y) && !isPointOnLineSegment(p3.x, p3.y, p4.x, p4.y, p2.x, p2.y) && doesSegmentIntersect(p1, p2, p3, p4) ) { if (p1.type == "gap" && p2.type == "gap") { if ( p1.bottleneck[0] == p2.bottleneck[0] && p1.bottleneck[1] == p2.bottleneck[1] ) { return true; } if ( p1.bottleneck[0] == p2.bottleneck[0] || p1.bottleneck[0] == p2.bottleneck[1] || p1.bottleneck[1] == p2.bottleneck[0] || p1.bottleneck[1] == p2.bottleneck[1] ) { continue; } } return true; } } return false; } // 判断线段是否合法（不与瓶颈、圆和矩形相交） function doesSegmentLegal( p1, p2, bottlenecks, circles, rects, padding = hardpadding ) { if (doesSegmentCrossBottlenecks(p1, p2, bottlenecks)) { return false; } if (doesSegmentCrossCircles(p1, p2, circles, padding)) { return false; } if (doesSegmentCrossRects(p1, p2, rects)) { return false; } return true; } // 判断点是否合法（不在圆内或矩形内） function doesPointLegal(p, circles, rects, padding = hardpadding) { for (let circle of circles) { if (getDistance(p, circle) < circle.size + padding) { return false; } } for (let { x1, y1, x2, y2 } of rects) { if (isPointInRectangle(x1, y1, x2, y2, p.x, p.y)) { return false; } } return true; } const bottleneckRelations = findBottlenecks(biases); const bottlenecks = bottleneckRelations.map(([i, j]) => [ biases[i], biases[j] ]); // Step1. Add bottleneck nodes. for (let [i, j] of bottleneckRelations) { const p1 = biases[i], p2 = biases[j], dist = getDistance(biases[i], biases[j]); const width = dist - p1.size - p2.size - padding * 2; const n = Math.ceil(width / nodePerWidth); const gap = width / n; for (let k = 0; k < n; ++k) { const [x, y] = movePoint( p1.x, p1.y, p2.x, p2.y, p1.size + padding + (k + 0.5) * gap ); const cap = width / n; const newnode = { id: `dn${nodes.length}`, type: "gap", x, y, p1, p2, bottleneck: [i, j], capacity: cap }; nodes.push(newnode); } } const obstackes = []; for (let bias of biases) { const x = bias.x + bias.consequent.lx; const y = bias.y + bias.consequent.ly; const width = bias.consequent.width; const height = bias.consequent.fontsize; obstackes.push({ x1: x, // - width / 2, y1: y - height / 2, x2: x + width / 2, y2: y + height / 2 }); } // Step2. Add dummy nodes for biases. const dummyPerBias = 16; for (let bias of biases) { for (let i = 0; i < dummyPerBias; ++i) { const angle = (i / dummyPerBias) * Math.PI * 2; const x = bias.x + Math.cos(angle) * (bias.size + padding); const y = bias.y + Math.sin(angle) * (bias.size + padding); const capacity = Number.MAX_VALUE; if (!doesPointLegal({ x, y }, biases, obstackes)) { continue; } const newnode = { id: `dn${nodes.length}`, x, y, capacity, sink: bias, type: "circle" }; nodes.push(newnode); } } // Step3. Add dummy nodes for arcs. const center = { x: setting.circularWidth / 2, y: setting.circularHeight / 2 }; let innerRadius; for (let d of arcs) { const R = getDistance(d, center); const R1 = R - 20; innerRadius = R1; const x = center.x + ((d.x - center.x) / R) * R1; const y = center.y + ((d.y - center.y) / R) * R1; const capacity = Number.MAX_VALUE; const arc = { id: `dn${nodes.length}`, type: "arc", x, y, capacity }; nodes.push(arc); edges.push({ source: d, target: arc }); } // Step4. Add random dummy nodes for arcs. for (let i = 0; i < randomDummyNodes; ++i) { let x, y; do { const radius = Math.sqrt(rng.nextFloat()) * innerRadius; const rad = rng.nextFloat() * Math.PI * 2; x = Math.cos(rad) * radius + center.x; y = Math.sin(rad) * radius + center.y; } while (!doesPointLegal({ x, y }, biases, obstackes)); const point = { id: `dn${nodes.length}`, type: "dummy", x, y, capacity: Number.MAX_VALUE }; nodes.push(point); } nodes.forEach((d, index) => (d.index = index)); const addEdgeStartTime = new Date(); // Step5. Add edges const extent = [ d3.extent(nodes.map((d) => d.x)), d3.extent(nodes.map((d) => d.y)) ]; const quadtree = d3 .quadtree() .extent([ [extent[0][0] - 1, extent[1][0] - 1], [extent[0][1] + 1, extent[1][1] + 1] ]) .x((d) => d.x) .y((d) => d.y) .addAll(nodes); let neighbors = []; function search(quadtree, [[x0, y0], [x3, y3]]) { quadtree.visit((node, x1, y1, x2, y2) => { if (!Array.isArray(node)) { do { const { data: d, data: { x, y } } = node; if (x >= x0 && x < x3 && y >= y0 && y < y3) { neighbors.push(d); } } while ((node = node.next)); } return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0; }); } const searchRange = 100; for (let i = 0; i < nodes.length; ++i) { neighbors = []; search(quadtree, [ [nodes[i].x - searchRange, nodes[i].y - searchRange], [nodes[i].x + searchRange, nodes[i].y + searchRange] ]); const currentNeighbors = neighbors .filter((d) => d.index > nodes[i].index) .map((d) => [d, getDistance(d, nodes[i])]) .sort((a, b) => a[1] - b[1]) .slice(0, topk) .map((d) => d[0]); const bottlenecks_ = bottlenecks.filter(([p1, p2]) => { return ( Math.max(p1.x, p2.x) >= nodes[i].x - searchRange && Math.min(p1.x, p2.x) <= nodes[i].x + searchRange && Math.max(p1.y, p2.y) >= nodes[i].y - searchRange && Math.min(p1.y, p2.y) <= nodes[i].y + searchRange ); }); const biases_ = biases.filter(({ x, y, size }) => { return ( x + size + padding >= nodes[i].x - searchRange && x - size - padding <= nodes[i].x + searchRange && y + size + padding >= nodes[i].y - searchRange && y - size - padding <= nodes[i].y + searchRange ); }); const obstackes_ = obstackes.filter(({ x1, y1, x2, y2 }) => { return ( x2 >= nodes[i].x - searchRange && x1 <= nodes[i].x + searchRange && y2 >= nodes[i].y - searchRange && y1 <= nodes[i].y + searchRange ); }); for (let neighbor of currentNeighbors) { if (getDistance(neighbor, nodes[i]) > searchRange) { break; } //TODO if ( doesSegmentLegal(nodes[i], neighbor, bottlenecks_, biases_, []) //obstackes_) ) { edges.push({ source: nodes[i], target: neighbor }); } } } const addEdgeEndTime = new Date(); console.log("add edge time", addEdgeEndTime - addEdgeStartTime); const G = new Graph(); edges.forEach((d) => { const dx = d.target.x - d.source.x; const dy = d.target.y - d.source.y; const midpointX = (d.source.x + d.target.x) / 2; const midpointY = (d.source.y + d.target.y) / 2; const edgeVector = [dx, dy]; const centerVector = [center.x - midpointX, center.y - midpointY]; // 计算两个向量的点积 const dotProduct = edgeVector[0] * centerVector[0] + edgeVector[1] * centerVector[1]; // 计算两个向量的模 const edgeMagnitude = Math.sqrt(dx * dx + dy * dy); const centerMagnitude = Math.sqrt( centerVector[0] * centerVector[0] + centerVector[1] * centerVector[1] ); // 计算夹角的余弦值 const cosAngle = dotProduct / (edgeMagnitude * centerMagnitude); // 将余弦值映射到[0, 1]区间，0表示垂直（不鼓励），1表示平行（鼓励） const angleBonus = (cosAngle + 1) / 2; const euclideanDistance = getDistance(d.source, d.target); const angleWeight = 0.3; // 角度权重 d.dist = euclideanDistance * (1 - angleBonus * angleWeight); G.addEdge(d.source.id, d.target.id, d.dist); }); nodes.forEach((d) => { if (d.sink) { G.addEdge(d.id, d.sink.id, 0); } else { G.setCapacity(d.id, d.capacity); } }); biases.forEach((d) => { G.setStartPoint(d.id); }); const pointWidth = {}; for (let d of nodes) { pointWidth[d.id] = 0; } const midTime1 = new Date(); let paths = causes.map((d) => ({ start: d.arc.id, end: d.parent.id, color: d.color, width: d.width })); const trees = [...new Set(paths.map((d) => d.start))].map((root) => ({ root, paths: paths.filter((d) => d.start == root) })); const differentPathPenalty = 1.2; //1.2; const mapNodes = new Map( nodes .concat(biases) .concat(arcs) .map((d) => [d.id, d]) ); trees.forEach((tree) => { let usedPaths = new Set(); const endPoints = [...new Set(tree.paths.map((d) => d.end))]; tree.segments = []; let allPaths, newPaths; if (endPoints.length === 1) { // 如果只有一个终点，直接使用findPath const path = G.findPath(tree.root, endPoints[0], tree.paths[0].width); allPaths = { paths: [path], combinedPaths: [path], flows: [tree.paths[0].width] }; } else { // 如果有多个终点，使用findPathsFromMidPoint allPaths = G.findPathsFromMidPoint( endPoints, tree.root, tree.paths.map((d) => d.width) ); } for (let i = 0; i < allPaths.paths.length; ++i) { tree.segments.push({ path: allPaths.paths[i] .map((id) => mapNodes.get(id)) .map((d) => [d.x, d.y]), width: allPaths.flows[i], color: tree.paths[0].color }); } tree.paths.forEach((d, index) => { let path = allPaths.combinedPaths[index]; G.augmentFlow(path, d.width); G.clearFlow(path[path.length - 2]); for (let i = 0; i < path.length - 1; ++i) { G.scaleEdgeWeight(path[i], path[i + 1], differentPathPenalty); pointWidth[path[i]] = (pointWidth[path[i]] || 0) + d.width; } d.path = path; }); }); const points = {}; for (let d of arcs) { const p1 = moveAlongCircle(d.x, d.y, center.x, center.y, -pointWidth[d.id]); points[d.id] = { start: p1, type: "circle" }; } for (let d of causes) { points[d.id] = { start: [d.x, d.y], type: "direct" }; } for (let d of biases) { points[d.id] = { start: [d.x, d.y], type: "direct" }; } for (let d of nodes) { if (d.type == "gap" || d.type == "dummy-gap") { const p1 = movePoint(d.x, d.y, d.p1.x, d.p1.y, pointWidth[d.id] / 2); const p2 = [d.p2.x, d.p2.y]; points[d.id] = { start: p1, end: p2, type: "line" }; } else if (d.type == "circle") { const p2 = movePoint(d.x, d.y, d.sink.x, d.sink.y, pointWidth[d.id]); const p1 = movePoint(d.x, d.y, d.sink.x, d.sink.y, -pointWidth[d.id]); points[d.id] = { start: p1, end: p2, type: "line" }; } else if (d.type == "arc") { const p1 = moveAlongCircle( d.x, d.y, center.x, center.y, -pointWidth[d.id] ); points[d.id] = { start: p1, type: "circle" }; } else { points[d.id] = { start: [d.x, d.y], type: "circle" }; } } const removeInnerpoint = (path) => { if (path.length >= 3) { let start = path.length - 1, end = 0; for (let i = 0; i < path.length; ++i) { if (mapNodes.has(path[i]) && mapNodes.get(path[i]).type == "gap") { start = i; break; } } for (let i = path.length - 1; i >= 0; --i) { if (mapNodes.has(path[i]) && mapNodes.get(path[i]).type == "gap") { end = i; break; } } console.log("start - end", start, end, path.length, path); path = path.filter( (d, i) => i < start || i > end || (mapNodes.has(d) && mapNodes.get(d).type == "gap") ); } return path; }; const removeExcess = (path) => { while (path.length >= 3) { let hasExcess = 0; for (let i = 1; i < path.length - 3; ++i) { const p1 = mapNodes.get(path[i]), p2 = mapNodes.get(path[i + 1]); if (!doesSegmentCrossCircles(p1, p2, biases, padding)) { hasExcess = 1; path.splice(i + 1, 1); break; } } if (!hasExcess) { break; } } return path; }; for (let tree of trees) { for (let d of tree.paths) { d.single = tree.paths.length == 1; d.path = removeInnerpoint(d.path); // 将路径分为两部分：第一部分不包含"gap"，第二部分从"gap"开始 let gapIndex = d.path.findIndex( (p) => mapNodes.has(p) && mapNodes.get(p).type === "gap" ); if (gapIndex !== -1) { d.pathBeforeGap = d.path.slice(0, gapIndex); d.pathFromGap = d.path.slice(gapIndex); } else { d.pathBeforeGap = d.path; d.pathFromGap = []; } //d.pathBeforeGap = removeExcess(d.pathBeforeGap); const endPoint = mapNodes.get( d.pathBeforeGap[d.pathBeforeGap.length - 1] ); const start = mapNodes.get(d.pathBeforeGap[0]); d.endAngle = Math.atan2(endPoint.y - start.y, endPoint.x - start.x); } tree.paths = tree.paths.sort((a, b) => b.endAngle - a.endAngle); } console.log("trees", JSON.parse(JSON.stringify(trees))); for (let tree of trees) { for (let d of tree.paths) { const processPath = (path) => { return path.map((k) => { const point = points[k]; let current; if (point.type == "circle") { current = moveAlongCircle( point.start[0], point.start[1], center.x, center.y, d.width ); } else if (point.type == "line") { current = movePoint( point.start[0], point.start[1], point.end[0], point.end[1], d.width ); } else { current = point.start; } point.start = [current[0], current[1]]; if (point.type == "circle") { current = moveAlongCircle( point.start[0], point.start[1], center.x, center.y, -d.width / 2 ); } else if (point.type == "line") { current = movePoint( point.start[0], point.start[1], point.end[0], point.end[1], -d.width / 2 ); } return current; }); }; d.pathBeforeGap = processPath(d.pathBeforeGap); d.pathFromGap = processPath(d.pathFromGap); d.path = d.pathFromGap; if (d.pathBeforeGap.length > 0 && d.pathFromGap.length > 0) { d.pathBeforeGap.push(d.pathFromGap[0]); } if (d.pathFromGap.length > 2) { const [x1, y1] = d.pathFromGap[d.pathFromGap.length - 2]; const [x2, y2] = d.pathFromGap[d.pathFromGap.length - 1]; d.pathFromGap[d.pathFromGap.length - 1] = movePoint(x1, y1, x2, y2, 15); } } } const endTime = new Date(); console.log( "total time", endTime - startTime, "short path time", endTime - midTime1 ); return { dummyNodes: nodes, dummyEdges: edges, paths: [].concat(...trees.map((d) => d.segments)) }; }