| 6dd74de | | | 1 | import type { LayoutData } from 'mermaid'; |
| 6dd74de | | | 2 | import type { Bounds, Point } from 'mermaid/src/types.js'; |
| 6dd74de | | | 3 | import { BoundingBox, Layout } from 'non-layered-tidy-tree-layout'; |
| 6dd74de | | | 4 | import type { |
| 6dd74de | | | 5 | Edge, |
| 6dd74de | | | 6 | LayoutResult, |
| 6dd74de | | | 7 | Node, |
| 6dd74de | | | 8 | PositionedEdge, |
| 6dd74de | | | 9 | PositionedNode, |
| 6dd74de | | | 10 | TidyTreeNode, |
| 6dd74de | | | 11 | } from './types.js'; |
| 6dd74de | | | 12 | |
| 6dd74de | | | 13 | /** |
| 6dd74de | | | 14 | * Execute the tidy-tree layout algorithm on generic layout data |
| 6dd74de | | | 15 | * |
| 6dd74de | | | 16 | * This function takes layout data and uses the non-layered-tidy-tree-layout |
| 6dd74de | | | 17 | * algorithm to calculate optimal node positions for tree structures. |
| 6dd74de | | | 18 | * |
| 6dd74de | | | 19 | * @param data - The layout data containing nodes, edges, and configuration |
| 6dd74de | | | 20 | * @param config - Mermaid configuration object |
| 6dd74de | | | 21 | * @returns Promise resolving to layout result with positioned nodes and edges |
| 6dd74de | | | 22 | */ |
| 6dd74de | | | 23 | export function executeTidyTreeLayout(data: LayoutData): Promise<LayoutResult> { |
| 6dd74de | | | 24 | let intersectionShift = 50; |
| 6dd74de | | | 25 | |
| 6dd74de | | | 26 | return new Promise((resolve, reject) => { |
| 6dd74de | | | 27 | try { |
| 6dd74de | | | 28 | if (!data.nodes || !Array.isArray(data.nodes) || data.nodes.length === 0) { |
| 6dd74de | | | 29 | throw new Error('No nodes found in layout data'); |
| 6dd74de | | | 30 | } |
| 6dd74de | | | 31 | |
| 6dd74de | | | 32 | if (!data.edges || !Array.isArray(data.edges)) { |
| 6dd74de | | | 33 | data.edges = []; |
| 6dd74de | | | 34 | } |
| 6dd74de | | | 35 | |
| 6dd74de | | | 36 | const { leftTree, rightTree, rootNode } = convertToDualTreeFormat(data); |
| 6dd74de | | | 37 | |
| 6dd74de | | | 38 | const gap = 20; |
| 6dd74de | | | 39 | const bottomPadding = 40; |
| 6dd74de | | | 40 | intersectionShift = 30; |
| 6dd74de | | | 41 | |
| 6dd74de | | | 42 | const bb = new BoundingBox(gap, bottomPadding); |
| 6dd74de | | | 43 | const layout = new Layout(bb); |
| 6dd74de | | | 44 | |
| 6dd74de | | | 45 | let leftResult = null; |
| 6dd74de | | | 46 | let rightResult = null; |
| 6dd74de | | | 47 | |
| 6dd74de | | | 48 | if (leftTree) { |
| 6dd74de | | | 49 | const leftLayoutResult = layout.layout(leftTree); |
| 6dd74de | | | 50 | leftResult = leftLayoutResult.result; |
| 6dd74de | | | 51 | } |
| 6dd74de | | | 52 | |
| 6dd74de | | | 53 | if (rightTree) { |
| 6dd74de | | | 54 | const rightLayoutResult = layout.layout(rightTree); |
| 6dd74de | | | 55 | rightResult = rightLayoutResult.result; |
| 6dd74de | | | 56 | } |
| 6dd74de | | | 57 | |
| 6dd74de | | | 58 | const positionedNodes = combineAndPositionTrees(rootNode, leftResult, rightResult); |
| 6dd74de | | | 59 | const positionedEdges = calculateEdgePositions( |
| 6dd74de | | | 60 | data.edges, |
| 6dd74de | | | 61 | positionedNodes, |
| 6dd74de | | | 62 | intersectionShift |
| 6dd74de | | | 63 | ); |
| 6dd74de | | | 64 | resolve({ |
| 6dd74de | | | 65 | nodes: positionedNodes, |
| 6dd74de | | | 66 | edges: positionedEdges, |
| 6dd74de | | | 67 | }); |
| 6dd74de | | | 68 | } catch (error) { |
| 6dd74de | | | 69 | reject(error); |
| 6dd74de | | | 70 | } |
| 6dd74de | | | 71 | }); |
| 6dd74de | | | 72 | } |
| 6dd74de | | | 73 | |
| 6dd74de | | | 74 | /** |
| 6dd74de | | | 75 | * Convert LayoutData to dual-tree format (left and right trees) |
| 6dd74de | | | 76 | * |
| 6dd74de | | | 77 | * This function builds two separate tree structures from the nodes and edges, |
| 6dd74de | | | 78 | * alternating children between left and right trees. |
| 6dd74de | | | 79 | */ |
| 6dd74de | | | 80 | function convertToDualTreeFormat(data: LayoutData): { |
| 6dd74de | | | 81 | leftTree: TidyTreeNode | null; |
| 6dd74de | | | 82 | rightTree: TidyTreeNode | null; |
| 6dd74de | | | 83 | rootNode: TidyTreeNode; |
| 6dd74de | | | 84 | } { |
| 6dd74de | | | 85 | const { nodes, edges } = data; |
| 6dd74de | | | 86 | |
| 6dd74de | | | 87 | const nodeMap = new Map<string, Node>(); |
| 6dd74de | | | 88 | nodes.forEach((node) => nodeMap.set(node.id, node)); |
| 6dd74de | | | 89 | |
| 6dd74de | | | 90 | const children = new Map<string, string[]>(); |
| 6dd74de | | | 91 | const parents = new Map<string, string>(); |
| 6dd74de | | | 92 | |
| 6dd74de | | | 93 | edges.forEach((edge) => { |
| 6dd74de | | | 94 | const parentId = edge.start; |
| 6dd74de | | | 95 | const childId = edge.end; |
| 6dd74de | | | 96 | |
| 6dd74de | | | 97 | if (parentId && childId) { |
| 6dd74de | | | 98 | if (!children.has(parentId)) { |
| 6dd74de | | | 99 | children.set(parentId, []); |
| 6dd74de | | | 100 | } |
| 6dd74de | | | 101 | children.get(parentId)!.push(childId); |
| 6dd74de | | | 102 | parents.set(childId, parentId); |
| 6dd74de | | | 103 | } |
| 6dd74de | | | 104 | }); |
| 6dd74de | | | 105 | |
| 6dd74de | | | 106 | const rootNodeData = nodes.find((node) => !parents.has(node.id)); |
| 6dd74de | | | 107 | if (!rootNodeData && nodes.length === 0) { |
| 6dd74de | | | 108 | throw new Error('No nodes available to create tree'); |
| 6dd74de | | | 109 | } |
| 6dd74de | | | 110 | |
| 6dd74de | | | 111 | const actualRoot = rootNodeData ?? nodes[0]; |
| 6dd74de | | | 112 | |
| 6dd74de | | | 113 | const rootNode: TidyTreeNode = { |
| 6dd74de | | | 114 | id: actualRoot.id, |
| 6dd74de | | | 115 | width: actualRoot.width ?? 100, |
| 6dd74de | | | 116 | height: actualRoot.height ?? 50, |
| 6dd74de | | | 117 | _originalNode: actualRoot, |
| 6dd74de | | | 118 | }; |
| 6dd74de | | | 119 | |
| 6dd74de | | | 120 | const rootChildren = children.get(actualRoot.id) ?? []; |
| 6dd74de | | | 121 | const leftChildren: string[] = []; |
| 6dd74de | | | 122 | const rightChildren: string[] = []; |
| 6dd74de | | | 123 | |
| 6dd74de | | | 124 | rootChildren.forEach((childId, index) => { |
| 6dd74de | | | 125 | if (index % 2 === 0) { |
| 6dd74de | | | 126 | leftChildren.push(childId); |
| 6dd74de | | | 127 | } else { |
| 6dd74de | | | 128 | rightChildren.push(childId); |
| 6dd74de | | | 129 | } |
| 6dd74de | | | 130 | }); |
| 6dd74de | | | 131 | |
| 6dd74de | | | 132 | const leftTree = leftChildren.length > 0 ? buildSubTree(leftChildren, children, nodeMap) : null; |
| 6dd74de | | | 133 | |
| 6dd74de | | | 134 | const rightTree = |
| 6dd74de | | | 135 | rightChildren.length > 0 ? buildSubTree(rightChildren, children, nodeMap) : null; |
| 6dd74de | | | 136 | |
| 6dd74de | | | 137 | return { leftTree, rightTree, rootNode }; |
| 6dd74de | | | 138 | } |
| 6dd74de | | | 139 | |
| 6dd74de | | | 140 | /** |
| 6dd74de | | | 141 | * Build a subtree from a list of root children |
| 6dd74de | | | 142 | * For horizontal trees, we need to transpose width/height since the tree will be rotated 90° |
| 6dd74de | | | 143 | */ |
| 6dd74de | | | 144 | function buildSubTree( |
| 6dd74de | | | 145 | rootChildren: string[], |
| 6dd74de | | | 146 | children: Map<string, string[]>, |
| 6dd74de | | | 147 | nodeMap: Map<string, Node> |
| 6dd74de | | | 148 | ): TidyTreeNode { |
| 6dd74de | | | 149 | const virtualRoot: TidyTreeNode = { |
| 6dd74de | | | 150 | id: `virtual-root-${Math.random()}`, |
| 6dd74de | | | 151 | width: 1, |
| 6dd74de | | | 152 | height: 1, |
| 6dd74de | | | 153 | children: rootChildren |
| 6dd74de | | | 154 | .map((childId) => nodeMap.get(childId)) |
| 6dd74de | | | 155 | .filter((child): child is Node => child !== undefined) |
| 6dd74de | | | 156 | .map((child) => convertNodeToTidyTreeTransposed(child, children, nodeMap)), |
| 6dd74de | | | 157 | }; |
| 6dd74de | | | 158 | |
| 6dd74de | | | 159 | return virtualRoot; |
| 6dd74de | | | 160 | } |
| 6dd74de | | | 161 | |
| 6dd74de | | | 162 | /** |
| 6dd74de | | | 163 | * Recursively convert a node and its children to tidy-tree format |
| 6dd74de | | | 164 | * This version transposes width/height for horizontal tree layout |
| 6dd74de | | | 165 | */ |
| 6dd74de | | | 166 | function convertNodeToTidyTreeTransposed( |
| 6dd74de | | | 167 | node: Node, |
| 6dd74de | | | 168 | children: Map<string, string[]>, |
| 6dd74de | | | 169 | nodeMap: Map<string, Node> |
| 6dd74de | | | 170 | ): TidyTreeNode { |
| 6dd74de | | | 171 | const childIds = children.get(node.id) ?? []; |
| 6dd74de | | | 172 | const childNodes = childIds |
| 6dd74de | | | 173 | .map((childId) => nodeMap.get(childId)) |
| 6dd74de | | | 174 | .filter((child): child is Node => child !== undefined) |
| 6dd74de | | | 175 | .map((child) => convertNodeToTidyTreeTransposed(child, children, nodeMap)); |
| 6dd74de | | | 176 | |
| 6dd74de | | | 177 | return { |
| 6dd74de | | | 178 | id: node.id, |
| 6dd74de | | | 179 | width: node.height ?? 50, |
| 6dd74de | | | 180 | height: node.width ?? 100, |
| 6dd74de | | | 181 | children: childNodes.length > 0 ? childNodes : undefined, |
| 6dd74de | | | 182 | _originalNode: node, |
| 6dd74de | | | 183 | }; |
| 6dd74de | | | 184 | } |
| 6dd74de | | | 185 | /** |
| 6dd74de | | | 186 | * Combine and position the left and right trees around the root node |
| 6dd74de | | | 187 | * Creates a bidirectional layout where left tree grows left and right tree grows right |
| 6dd74de | | | 188 | */ |
| 6dd74de | | | 189 | function combineAndPositionTrees( |
| 6dd74de | | | 190 | rootNode: TidyTreeNode, |
| 6dd74de | | | 191 | leftResult: TidyTreeNode | null, |
| 6dd74de | | | 192 | rightResult: TidyTreeNode | null |
| 6dd74de | | | 193 | ): PositionedNode[] { |
| 6dd74de | | | 194 | const positionedNodes: PositionedNode[] = []; |
| 6dd74de | | | 195 | |
| 6dd74de | | | 196 | const rootX = 0; |
| 6dd74de | | | 197 | const rootY = 0; |
| 6dd74de | | | 198 | |
| 6dd74de | | | 199 | const treeSpacing = rootNode.width / 2 + 30; |
| 6dd74de | | | 200 | const leftTreeNodes: PositionedNode[] = []; |
| 6dd74de | | | 201 | const rightTreeNodes: PositionedNode[] = []; |
| 6dd74de | | | 202 | |
| 6dd74de | | | 203 | if (leftResult?.children) { |
| 6dd74de | | | 204 | positionLeftTreeBidirectional(leftResult.children, leftTreeNodes, rootX - treeSpacing, rootY); |
| 6dd74de | | | 205 | } |
| 6dd74de | | | 206 | |
| 6dd74de | | | 207 | if (rightResult?.children) { |
| 6dd74de | | | 208 | positionRightTreeBidirectional( |
| 6dd74de | | | 209 | rightResult.children, |
| 6dd74de | | | 210 | rightTreeNodes, |
| 6dd74de | | | 211 | rootX + treeSpacing, |
| 6dd74de | | | 212 | rootY |
| 6dd74de | | | 213 | ); |
| 6dd74de | | | 214 | } |
| 6dd74de | | | 215 | |
| 6dd74de | | | 216 | let leftTreeCenterY = 0; |
| 6dd74de | | | 217 | let rightTreeCenterY = 0; |
| 6dd74de | | | 218 | |
| 6dd74de | | | 219 | if (leftTreeNodes.length > 0) { |
| 6dd74de | | | 220 | const leftTreeXPositions = [...new Set(leftTreeNodes.map((node) => node.x))].sort( |
| 6dd74de | | | 221 | (a, b) => b - a |
| 6dd74de | | | 222 | ); |
| 6dd74de | | | 223 | const firstLevelLeftX = leftTreeXPositions[0]; |
| 6dd74de | | | 224 | const firstLevelLeftNodes = leftTreeNodes.filter((node) => node.x === firstLevelLeftX); |
| 6dd74de | | | 225 | |
| 6dd74de | | | 226 | if (firstLevelLeftNodes.length > 0) { |
| 6dd74de | | | 227 | const leftMinY = Math.min( |
| 6dd74de | | | 228 | ...firstLevelLeftNodes.map((node) => node.y - (node.height ?? 50) / 2) |
| 6dd74de | | | 229 | ); |
| 6dd74de | | | 230 | const leftMaxY = Math.max( |
| 6dd74de | | | 231 | ...firstLevelLeftNodes.map((node) => node.y + (node.height ?? 50) / 2) |
| 6dd74de | | | 232 | ); |
| 6dd74de | | | 233 | leftTreeCenterY = (leftMinY + leftMaxY) / 2; |
| 6dd74de | | | 234 | } |
| 6dd74de | | | 235 | } |
| 6dd74de | | | 236 | |
| 6dd74de | | | 237 | if (rightTreeNodes.length > 0) { |
| 6dd74de | | | 238 | const rightTreeXPositions = [...new Set(rightTreeNodes.map((node) => node.x))].sort( |
| 6dd74de | | | 239 | (a, b) => a - b |
| 6dd74de | | | 240 | ); |
| 6dd74de | | | 241 | const firstLevelRightX = rightTreeXPositions[0]; |
| 6dd74de | | | 242 | const firstLevelRightNodes = rightTreeNodes.filter((node) => node.x === firstLevelRightX); |
| 6dd74de | | | 243 | |
| 6dd74de | | | 244 | if (firstLevelRightNodes.length > 0) { |
| 6dd74de | | | 245 | const rightMinY = Math.min( |
| 6dd74de | | | 246 | ...firstLevelRightNodes.map((node) => node.y - (node.height ?? 50) / 2) |
| 6dd74de | | | 247 | ); |
| 6dd74de | | | 248 | const rightMaxY = Math.max( |
| 6dd74de | | | 249 | ...firstLevelRightNodes.map((node) => node.y + (node.height ?? 50) / 2) |
| 6dd74de | | | 250 | ); |
| 6dd74de | | | 251 | rightTreeCenterY = (rightMinY + rightMaxY) / 2; |
| 6dd74de | | | 252 | } |
| 6dd74de | | | 253 | } |
| 6dd74de | | | 254 | |
| 6dd74de | | | 255 | const leftTreeOffset = -leftTreeCenterY; |
| 6dd74de | | | 256 | const rightTreeOffset = -rightTreeCenterY; |
| 6dd74de | | | 257 | |
| 6dd74de | | | 258 | positionedNodes.push({ |
| 6dd74de | | | 259 | id: String(rootNode.id), |
| 6dd74de | | | 260 | x: rootX, |
| 6dd74de | | | 261 | y: rootY + 20, |
| 6dd74de | | | 262 | section: 'root', |
| 6dd74de | | | 263 | width: rootNode._originalNode?.width ?? rootNode.width, |
| 6dd74de | | | 264 | height: rootNode._originalNode?.height ?? rootNode.height, |
| 6dd74de | | | 265 | originalNode: rootNode._originalNode, |
| 6dd74de | | | 266 | }); |
| 6dd74de | | | 267 | |
| 6dd74de | | | 268 | const leftTreeNodesWithOffset = leftTreeNodes.map((node) => ({ |
| 6dd74de | | | 269 | id: node.id, |
| 6dd74de | | | 270 | x: node.x - (node.width ?? 0) / 2, |
| 6dd74de | | | 271 | y: node.y + leftTreeOffset + (node.height ?? 0) / 2, |
| 6dd74de | | | 272 | section: 'left' as const, |
| 6dd74de | | | 273 | width: node.width, |
| 6dd74de | | | 274 | height: node.height, |
| 6dd74de | | | 275 | originalNode: node.originalNode, |
| 6dd74de | | | 276 | })); |
| 6dd74de | | | 277 | |
| 6dd74de | | | 278 | const rightTreeNodesWithOffset = rightTreeNodes.map((node) => ({ |
| 6dd74de | | | 279 | id: node.id, |
| 6dd74de | | | 280 | x: node.x + (node.width ?? 0) / 2, |
| 6dd74de | | | 281 | y: node.y + rightTreeOffset + (node.height ?? 0) / 2, |
| 6dd74de | | | 282 | section: 'right' as const, |
| 6dd74de | | | 283 | width: node.width, |
| 6dd74de | | | 284 | height: node.height, |
| 6dd74de | | | 285 | originalNode: node.originalNode, |
| 6dd74de | | | 286 | })); |
| 6dd74de | | | 287 | |
| 6dd74de | | | 288 | positionedNodes.push(...leftTreeNodesWithOffset); |
| 6dd74de | | | 289 | positionedNodes.push(...rightTreeNodesWithOffset); |
| 6dd74de | | | 290 | |
| 6dd74de | | | 291 | return positionedNodes; |
| 6dd74de | | | 292 | } |
| 6dd74de | | | 293 | |
| 6dd74de | | | 294 | /** |
| 6dd74de | | | 295 | * Position nodes from the left tree in a bidirectional layout (grows to the left) |
| 6dd74de | | | 296 | * Rotates the tree 90 degrees counterclockwise so it grows horizontally to the left |
| 6dd74de | | | 297 | */ |
| 6dd74de | | | 298 | function positionLeftTreeBidirectional( |
| 6dd74de | | | 299 | nodes: TidyTreeNode[], |
| 6dd74de | | | 300 | positionedNodes: PositionedNode[], |
| 6dd74de | | | 301 | offsetX: number, |
| 6dd74de | | | 302 | offsetY: number |
| 6dd74de | | | 303 | ): void { |
| 6dd74de | | | 304 | nodes.forEach((node) => { |
| 6dd74de | | | 305 | const distanceFromRoot = node.y ?? 0; |
| 6dd74de | | | 306 | const verticalPosition = node.x ?? 0; |
| 6dd74de | | | 307 | |
| 6dd74de | | | 308 | const originalWidth = node._originalNode?.width ?? 100; |
| 6dd74de | | | 309 | const originalHeight = node._originalNode?.height ?? 50; |
| 6dd74de | | | 310 | |
| 6dd74de | | | 311 | const adjustedY = offsetY + verticalPosition; |
| 6dd74de | | | 312 | |
| 6dd74de | | | 313 | positionedNodes.push({ |
| 6dd74de | | | 314 | id: String(node.id), |
| 6dd74de | | | 315 | x: offsetX - distanceFromRoot, |
| 6dd74de | | | 316 | y: adjustedY, |
| 6dd74de | | | 317 | width: originalWidth, |
| 6dd74de | | | 318 | height: originalHeight, |
| 6dd74de | | | 319 | originalNode: node._originalNode, |
| 6dd74de | | | 320 | }); |
| 6dd74de | | | 321 | |
| 6dd74de | | | 322 | if (node.children) { |
| 6dd74de | | | 323 | positionLeftTreeBidirectional(node.children, positionedNodes, offsetX, offsetY); |
| 6dd74de | | | 324 | } |
| 6dd74de | | | 325 | }); |
| 6dd74de | | | 326 | } |
| 6dd74de | | | 327 | |
| 6dd74de | | | 328 | /** |
| 6dd74de | | | 329 | * Position nodes from the right tree in a bidirectional layout (grows to the right) |
| 6dd74de | | | 330 | * Rotates the tree 90 degrees clockwise so it grows horizontally to the right |
| 6dd74de | | | 331 | */ |
| 6dd74de | | | 332 | function positionRightTreeBidirectional( |
| 6dd74de | | | 333 | nodes: TidyTreeNode[], |
| 6dd74de | | | 334 | positionedNodes: PositionedNode[], |
| 6dd74de | | | 335 | offsetX: number, |
| 6dd74de | | | 336 | offsetY: number |
| 6dd74de | | | 337 | ): void { |
| 6dd74de | | | 338 | nodes.forEach((node) => { |
| 6dd74de | | | 339 | const distanceFromRoot = node.y ?? 0; |
| 6dd74de | | | 340 | const verticalPosition = node.x ?? 0; |
| 6dd74de | | | 341 | |
| 6dd74de | | | 342 | const originalWidth = node._originalNode?.width ?? 100; |
| 6dd74de | | | 343 | const originalHeight = node._originalNode?.height ?? 50; |
| 6dd74de | | | 344 | |
| 6dd74de | | | 345 | const adjustedY = offsetY + verticalPosition; |
| 6dd74de | | | 346 | |
| 6dd74de | | | 347 | positionedNodes.push({ |
| 6dd74de | | | 348 | id: String(node.id), |
| 6dd74de | | | 349 | x: offsetX + distanceFromRoot, |
| 6dd74de | | | 350 | y: adjustedY, |
| 6dd74de | | | 351 | width: originalWidth, |
| 6dd74de | | | 352 | height: originalHeight, |
| 6dd74de | | | 353 | originalNode: node._originalNode, |
| 6dd74de | | | 354 | }); |
| 6dd74de | | | 355 | |
| 6dd74de | | | 356 | if (node.children) { |
| 6dd74de | | | 357 | positionRightTreeBidirectional(node.children, positionedNodes, offsetX, offsetY); |
| 6dd74de | | | 358 | } |
| 6dd74de | | | 359 | }); |
| 6dd74de | | | 360 | } |
| 6dd74de | | | 361 | |
| 6dd74de | | | 362 | /** |
| 6dd74de | | | 363 | * Calculate the intersection point of a line with a circle |
| 6dd74de | | | 364 | * @param circle - Circle coordinates and radius |
| 6dd74de | | | 365 | * @param lineStart - Starting point of the line |
| 6dd74de | | | 366 | * @param lineEnd - Ending point of the line |
| 6dd74de | | | 367 | * @returns The intersection point |
| 6dd74de | | | 368 | */ |
| 6dd74de | | | 369 | function computeCircleEdgeIntersection(circle: Bounds, lineStart: Point, lineEnd: Point): Point { |
| 6dd74de | | | 370 | const radius = Math.min(circle.width, circle.height) / 2; |
| 6dd74de | | | 371 | |
| 6dd74de | | | 372 | const dx = lineEnd.x - lineStart.x; |
| 6dd74de | | | 373 | const dy = lineEnd.y - lineStart.y; |
| 6dd74de | | | 374 | const length = Math.sqrt(dx * dx + dy * dy); |
| 6dd74de | | | 375 | |
| 6dd74de | | | 376 | if (length === 0) { |
| 6dd74de | | | 377 | return lineStart; |
| 6dd74de | | | 378 | } |
| 6dd74de | | | 379 | |
| 6dd74de | | | 380 | const nx = dx / length; |
| 6dd74de | | | 381 | const ny = dy / length; |
| 6dd74de | | | 382 | |
| 6dd74de | | | 383 | return { |
| 6dd74de | | | 384 | x: circle.x - nx * radius, |
| 6dd74de | | | 385 | y: circle.y - ny * radius, |
| 6dd74de | | | 386 | }; |
| 6dd74de | | | 387 | } |
| 6dd74de | | | 388 | |
| 6dd74de | | | 389 | function intersection(node: PositionedNode, outsidePoint: Point, insidePoint: Point): Point { |
| 6dd74de | | | 390 | const x = node.x; |
| 6dd74de | | | 391 | const y = node.y; |
| 6dd74de | | | 392 | |
| 6dd74de | | | 393 | if (!node.width || !node.height) { |
| 6dd74de | | | 394 | return { x: outsidePoint.x, y: outsidePoint.y }; |
| 6dd74de | | | 395 | } |
| 6dd74de | | | 396 | const dx = Math.abs(x - insidePoint.x); |
| 6dd74de | | | 397 | const w = node?.width / 2; |
| 6dd74de | | | 398 | let r = insidePoint.x < outsidePoint.x ? w - dx : w + dx; |
| 6dd74de | | | 399 | const h = node.height / 2; |
| 6dd74de | | | 400 | |
| 6dd74de | | | 401 | const Q = Math.abs(outsidePoint.y - insidePoint.y); |
| 6dd74de | | | 402 | const R = Math.abs(outsidePoint.x - insidePoint.x); |
| 6dd74de | | | 403 | |
| 6dd74de | | | 404 | if (Math.abs(y - outsidePoint.y) * w > Math.abs(x - outsidePoint.x) * h) { |
| 6dd74de | | | 405 | // Intersection is top or bottom of rect. |
| 6dd74de | | | 406 | const q = insidePoint.y < outsidePoint.y ? outsidePoint.y - h - y : y - h - outsidePoint.y; |
| 6dd74de | | | 407 | r = (R * q) / Q; |
| 6dd74de | | | 408 | const res = { |
| 6dd74de | | | 409 | x: insidePoint.x < outsidePoint.x ? insidePoint.x + r : insidePoint.x - R + r, |
| 6dd74de | | | 410 | y: insidePoint.y < outsidePoint.y ? insidePoint.y + Q - q : insidePoint.y - Q + q, |
| 6dd74de | | | 411 | }; |
| 6dd74de | | | 412 | |
| 6dd74de | | | 413 | if (r === 0) { |
| 6dd74de | | | 414 | res.x = outsidePoint.x; |
| 6dd74de | | | 415 | res.y = outsidePoint.y; |
| 6dd74de | | | 416 | } |
| 6dd74de | | | 417 | if (R === 0) { |
| 6dd74de | | | 418 | res.x = outsidePoint.x; |
| 6dd74de | | | 419 | } |
| 6dd74de | | | 420 | if (Q === 0) { |
| 6dd74de | | | 421 | res.y = outsidePoint.y; |
| 6dd74de | | | 422 | } |
| 6dd74de | | | 423 | |
| 6dd74de | | | 424 | return res; |
| 6dd74de | | | 425 | } else { |
| 6dd74de | | | 426 | if (insidePoint.x < outsidePoint.x) { |
| 6dd74de | | | 427 | r = outsidePoint.x - w - x; |
| 6dd74de | | | 428 | } else { |
| 6dd74de | | | 429 | r = x - w - outsidePoint.x; |
| 6dd74de | | | 430 | } |
| 6dd74de | | | 431 | const q = (Q * r) / R; |
| 6dd74de | | | 432 | let _x = insidePoint.x < outsidePoint.x ? insidePoint.x + R - r : insidePoint.x - R + r; |
| 6dd74de | | | 433 | let _y = insidePoint.y < outsidePoint.y ? insidePoint.y + q : insidePoint.y - q; |
| 6dd74de | | | 434 | |
| 6dd74de | | | 435 | if (r === 0) { |
| 6dd74de | | | 436 | _x = outsidePoint.x; |
| 6dd74de | | | 437 | _y = outsidePoint.y; |
| 6dd74de | | | 438 | } |
| 6dd74de | | | 439 | if (R === 0) { |
| 6dd74de | | | 440 | _x = outsidePoint.x; |
| 6dd74de | | | 441 | } |
| 6dd74de | | | 442 | if (Q === 0) { |
| 6dd74de | | | 443 | _y = outsidePoint.y; |
| 6dd74de | | | 444 | } |
| 6dd74de | | | 445 | |
| 6dd74de | | | 446 | return { x: _x, y: _y }; |
| 6dd74de | | | 447 | } |
| 6dd74de | | | 448 | } |
| 6dd74de | | | 449 | |
| 6dd74de | | | 450 | /** |
| 6dd74de | | | 451 | * Calculate edge positions based on positioned nodes |
| 6dd74de | | | 452 | * Now includes tree membership and node dimensions for precise edge calculations |
| 6dd74de | | | 453 | * Edges now stop at shape boundaries instead of extending to centers |
| 6dd74de | | | 454 | */ |
| 6dd74de | | | 455 | function calculateEdgePositions( |
| 6dd74de | | | 456 | edges: Edge[], |
| 6dd74de | | | 457 | positionedNodes: PositionedNode[], |
| 6dd74de | | | 458 | intersectionShift: number |
| 6dd74de | | | 459 | ): PositionedEdge[] { |
| 6dd74de | | | 460 | const nodeInfo = new Map<string, PositionedNode>(); |
| 6dd74de | | | 461 | positionedNodes.forEach((node) => { |
| 6dd74de | | | 462 | nodeInfo.set(node.id, node); |
| 6dd74de | | | 463 | }); |
| 6dd74de | | | 464 | |
| 6dd74de | | | 465 | return edges.map((edge) => { |
| 6dd74de | | | 466 | const sourceNode = nodeInfo.get(edge.start ?? ''); |
| 6dd74de | | | 467 | const targetNode = nodeInfo.get(edge.end ?? ''); |
| 6dd74de | | | 468 | |
| 6dd74de | | | 469 | if (!sourceNode || !targetNode) { |
| 6dd74de | | | 470 | return { |
| 6dd74de | | | 471 | id: edge.id, |
| 6dd74de | | | 472 | source: edge.start ?? '', |
| 6dd74de | | | 473 | target: edge.end ?? '', |
| 6dd74de | | | 474 | startX: 0, |
| 6dd74de | | | 475 | startY: 0, |
| 6dd74de | | | 476 | midX: 0, |
| 6dd74de | | | 477 | midY: 0, |
| 6dd74de | | | 478 | endX: 0, |
| 6dd74de | | | 479 | endY: 0, |
| 6dd74de | | | 480 | points: [{ x: 0, y: 0 }], |
| 6dd74de | | | 481 | sourceSection: undefined, |
| 6dd74de | | | 482 | targetSection: undefined, |
| 6dd74de | | | 483 | sourceWidth: undefined, |
| 6dd74de | | | 484 | sourceHeight: undefined, |
| 6dd74de | | | 485 | targetWidth: undefined, |
| 6dd74de | | | 486 | targetHeight: undefined, |
| 6dd74de | | | 487 | }; |
| 6dd74de | | | 488 | } |
| 6dd74de | | | 489 | |
| 6dd74de | | | 490 | const sourceCenter = { x: sourceNode.x, y: sourceNode.y }; |
| 6dd74de | | | 491 | const targetCenter = { x: targetNode.x, y: targetNode.y }; |
| 6dd74de | | | 492 | |
| 6dd74de | | | 493 | const isSourceRound = ['circle', 'cloud', 'bang'].includes( |
| 6dd74de | | | 494 | sourceNode.originalNode?.shape ?? '' |
| 6dd74de | | | 495 | ); |
| 6dd74de | | | 496 | const isTargetRound = ['circle', 'cloud', 'bang'].includes( |
| 6dd74de | | | 497 | targetNode.originalNode?.shape ?? '' |
| 6dd74de | | | 498 | ); |
| 6dd74de | | | 499 | |
| 6dd74de | | | 500 | let startPos = isSourceRound |
| 6dd74de | | | 501 | ? computeCircleEdgeIntersection( |
| 6dd74de | | | 502 | { |
| 6dd74de | | | 503 | x: sourceNode.x, |
| 6dd74de | | | 504 | y: sourceNode.y, |
| 6dd74de | | | 505 | width: sourceNode.width ?? 100, |
| 6dd74de | | | 506 | height: sourceNode.height ?? 100, |
| 6dd74de | | | 507 | }, |
| 6dd74de | | | 508 | targetCenter, |
| 6dd74de | | | 509 | sourceCenter |
| 6dd74de | | | 510 | ) |
| 6dd74de | | | 511 | : intersection(sourceNode, sourceCenter, targetCenter); |
| 6dd74de | | | 512 | |
| 6dd74de | | | 513 | let endPos = isTargetRound |
| 6dd74de | | | 514 | ? computeCircleEdgeIntersection( |
| 6dd74de | | | 515 | { |
| 6dd74de | | | 516 | x: targetNode.x, |
| 6dd74de | | | 517 | y: targetNode.y, |
| 6dd74de | | | 518 | width: targetNode.width ?? 100, |
| 6dd74de | | | 519 | height: targetNode.height ?? 100, |
| 6dd74de | | | 520 | }, |
| 6dd74de | | | 521 | sourceCenter, |
| 6dd74de | | | 522 | targetCenter |
| 6dd74de | | | 523 | ) |
| 6dd74de | | | 524 | : intersection(targetNode, targetCenter, sourceCenter); |
| 6dd74de | | | 525 | |
| 6dd74de | | | 526 | const midX = (startPos.x + endPos.x) / 2; |
| 6dd74de | | | 527 | const midY = (startPos.y + endPos.y) / 2; |
| 6dd74de | | | 528 | |
| 6dd74de | | | 529 | const points = [startPos]; |
| 6dd74de | | | 530 | if (sourceNode.section === 'left') { |
| 6dd74de | | | 531 | points.push({ |
| 6dd74de | | | 532 | x: sourceNode.x - (sourceNode.width ?? 0) / 2 - intersectionShift, |
| 6dd74de | | | 533 | y: sourceNode.y, |
| 6dd74de | | | 534 | }); |
| 6dd74de | | | 535 | } else if (sourceNode.section === 'right') { |
| 6dd74de | | | 536 | points.push({ |
| 6dd74de | | | 537 | x: sourceNode.x + (sourceNode.width ?? 0) / 2 + intersectionShift, |
| 6dd74de | | | 538 | y: sourceNode.y, |
| 6dd74de | | | 539 | }); |
| 6dd74de | | | 540 | } |
| 6dd74de | | | 541 | if (targetNode.section === 'left') { |
| 6dd74de | | | 542 | points.push({ |
| 6dd74de | | | 543 | x: targetNode.x + (targetNode.width ?? 0) / 2 + intersectionShift, |
| 6dd74de | | | 544 | y: targetNode.y, |
| 6dd74de | | | 545 | }); |
| 6dd74de | | | 546 | } else if (targetNode.section === 'right') { |
| 6dd74de | | | 547 | points.push({ |
| 6dd74de | | | 548 | x: targetNode.x - (targetNode.width ?? 0) / 2 - intersectionShift, |
| 6dd74de | | | 549 | y: targetNode.y, |
| 6dd74de | | | 550 | }); |
| 6dd74de | | | 551 | } |
| 6dd74de | | | 552 | |
| 6dd74de | | | 553 | points.push(endPos); |
| 6dd74de | | | 554 | |
| 6dd74de | | | 555 | const secondPoint = points.length > 1 ? points[1] : targetCenter; |
| 6dd74de | | | 556 | startPos = isSourceRound |
| 6dd74de | | | 557 | ? computeCircleEdgeIntersection( |
| 6dd74de | | | 558 | { |
| 6dd74de | | | 559 | x: sourceNode.x, |
| 6dd74de | | | 560 | y: sourceNode.y, |
| 6dd74de | | | 561 | width: sourceNode.width ?? 100, |
| 6dd74de | | | 562 | height: sourceNode.height ?? 100, |
| 6dd74de | | | 563 | }, |
| 6dd74de | | | 564 | secondPoint, |
| 6dd74de | | | 565 | sourceCenter |
| 6dd74de | | | 566 | ) |
| 6dd74de | | | 567 | : intersection(sourceNode, secondPoint, sourceCenter); |
| 6dd74de | | | 568 | points[0] = startPos; |
| 6dd74de | | | 569 | |
| 6dd74de | | | 570 | const secondLastPoint = points.length > 1 ? points[points.length - 2] : sourceCenter; |
| 6dd74de | | | 571 | endPos = isTargetRound |
| 6dd74de | | | 572 | ? computeCircleEdgeIntersection( |
| 6dd74de | | | 573 | { |
| 6dd74de | | | 574 | x: targetNode.x, |
| 6dd74de | | | 575 | y: targetNode.y, |
| 6dd74de | | | 576 | width: targetNode.width ?? 100, |
| 6dd74de | | | 577 | height: targetNode.height ?? 100, |
| 6dd74de | | | 578 | }, |
| 6dd74de | | | 579 | secondLastPoint, |
| 6dd74de | | | 580 | targetCenter |
| 6dd74de | | | 581 | ) |
| 6dd74de | | | 582 | : intersection(targetNode, secondLastPoint, targetCenter); |
| 6dd74de | | | 583 | points[points.length - 1] = endPos; |
| 6dd74de | | | 584 | |
| 6dd74de | | | 585 | return { |
| 6dd74de | | | 586 | id: edge.id, |
| 6dd74de | | | 587 | source: edge.start ?? '', |
| 6dd74de | | | 588 | target: edge.end ?? '', |
| 6dd74de | | | 589 | startX: startPos.x, |
| 6dd74de | | | 590 | startY: startPos.y, |
| 6dd74de | | | 591 | midX, |
| 6dd74de | | | 592 | midY, |
| 6dd74de | | | 593 | endX: endPos.x, |
| 6dd74de | | | 594 | endY: endPos.y, |
| 6dd74de | | | 595 | points, |
| 6dd74de | | | 596 | sourceSection: sourceNode?.section, |
| 6dd74de | | | 597 | targetSection: targetNode?.section, |
| 6dd74de | | | 598 | sourceWidth: sourceNode?.width, |
| 6dd74de | | | 599 | sourceHeight: sourceNode?.height, |
| 6dd74de | | | 600 | targetWidth: targetNode?.width, |
| 6dd74de | | | 601 | targetHeight: targetNode?.height, |
| 6dd74de | | | 602 | }; |
| 6dd74de | | | 603 | }); |
| 6dd74de | | | 604 | } |
| 6dd74de | | | 605 | |
| 6dd74de | | | 606 | /** |
| 6dd74de | | | 607 | * Validate layout data structure |
| 6dd74de | | | 608 | * @param data - The data to validate |
| 6dd74de | | | 609 | * @returns True if data is valid, throws error otherwise |
| 6dd74de | | | 610 | */ |
| 6dd74de | | | 611 | export function validateLayoutData(data: LayoutData): boolean { |
| 6dd74de | | | 612 | if (!data) { |
| 6dd74de | | | 613 | throw new Error('Layout data is required'); |
| 6dd74de | | | 614 | } |
| 6dd74de | | | 615 | |
| 6dd74de | | | 616 | if (!data.config) { |
| 6dd74de | | | 617 | throw new Error('Configuration is required in layout data'); |
| 6dd74de | | | 618 | } |
| 6dd74de | | | 619 | |
| 6dd74de | | | 620 | if (!Array.isArray(data.nodes)) { |
| 6dd74de | | | 621 | throw new Error('Nodes array is required in layout data'); |
| 6dd74de | | | 622 | } |
| 6dd74de | | | 623 | |
| 6dd74de | | | 624 | if (!Array.isArray(data.edges)) { |
| 6dd74de | | | 625 | throw new Error('Edges array is required in layout data'); |
| 6dd74de | | | 626 | } |
| 6dd74de | | | 627 | |
| 6dd74de | | | 628 | return true; |
| 6dd74de | | | 629 | } |