Repository Public
1// SP Notes Core2// File: Sources/SPNotesDocument/CanvasLayout.swift3// Description: Automatic layout of a canvas: a size-aware grid and a deterministic, seeded force-directed layout4// (repulsion between cards, springs along edges), shared by the macOS and iOS canvas editors.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation9import CoreGraphics1011/// A small deterministic generator (SplitMix64): the same seed gives the same layout on every device.12public struct CanvasLayoutRandom: Sendable, Hashable {13 var state: UInt6414 public init(seed: UInt64) { state = seed }1516 public mutating func next() -> UInt64 {17 state &+= 0x9E3779B97F4A7C1518 var z = state19 z = (z ^ (z >> 30)) &* 0xBF58476D1CE4E5B920 z = (z ^ (z >> 27)) &* 0x94D049BB133111EB21 return z ^ (z >> 31)22 }2324 /// A value in −1…1.25 public mutating func signedUnit() -> Double { Double(next() >> 11) / Double(1 << 53) * 2 - 1 }26}2728public enum CanvasLayout {29 /// Parameters of the force-directed layout. Distances are canvas units.30 public struct Forces: Sendable, Hashable {31 /// Free space wanted between two cards.32 public var spacing: Double33 /// Strength of the push between cards closer than their sizes plus `spacing`.34 public var repulsion: Double35 /// Strength of the pull along an edge longer than its rest length.36 public var attraction: Double37 /// Largest move of a card in one step at temperature 1.38 public var maxStep: Double3940 public init(spacing: Double = 48, repulsion: Double = 0.5, attraction: Double = 0.08, maxStep: Double = 120) {41 self.spacing = spacing42 self.repulsion = repulsion43 self.attraction = attraction44 self.maxStep = maxStep45 }46 }4748 // MARK: Grid4950 /// Places the nodes on a grid, in array order, row by row. Each column is as wide as its widest card and each51 /// row as tall as its tallest, so cards never overlap. `columns` nil picks ⌈√n⌉. Sizes, edges and ids are52 /// untouched; nodes listed in `pinned` keep their position and take no cell.53 public static func grid(_ document: CanvasDocument, columns: Int? = nil, spacing: Double = 48, origin: CGPoint = .zero,54 pinned: Set<String> = []) -> CanvasDocument {55 var out = document56 let movable = out.nodes.indices.filter { !pinned.contains(out.nodes[$0].id) }57 guard !movable.isEmpty else { return out }58 let cols = max(1, columns ?? Int(Double(movable.count).squareRoot().rounded(.up)))59 let gap = spacing.isFinite ? max(0, spacing) : 060 func size(_ i: Int) -> (Double, Double) { (max(0, out.nodes[i].w), max(0, out.nodes[i].h)) }61 var colWidth = [Double](repeating: 0, count: cols)62 var rowHeight = [Double](repeating: 0, count: (movable.count + cols - 1) / cols)63 for (n, i) in movable.enumerated() {64 colWidth[n % cols] = max(colWidth[n % cols], size(i).0)65 rowHeight[n / cols] = max(rowHeight[n / cols], size(i).1)66 }67 var colX = [Double](repeating: Double(origin.x), count: cols)68 for c in 1..<max(1, cols) where c < cols { colX[c] = colX[c - 1] + colWidth[c - 1] + gap }69 var rowY = [Double](repeating: Double(origin.y), count: rowHeight.count)70 for r in rowHeight.indices.dropFirst() { rowY[r] = rowY[r - 1] + rowHeight[r - 1] + gap }71 for (n, i) in movable.enumerated() {72 out.nodes[i].x = colX[n % cols]73 out.nodes[i].y = rowY[n / cols]74 }75 return out76 }7778 // MARK: Force-directed7980 /// Runs `iterations` steps of the force-directed layout with a linearly decreasing temperature.81 /// Deterministic: the same canvas, seed and parameters give the same result. `pinned` nodes do not move.82 public static func forceDirected(_ document: CanvasDocument, iterations: Int = 200, seed: UInt64 = 1, forces: Forces = Forces(),83 pinned: Set<String> = []) -> CanvasDocument {84 var out = document85 var rng = CanvasLayoutRandom(seed: seed)86 let n = max(0, iterations)87 for i in 0..<n {88 let temperature = 1 - Double(i) / Double(n)89 step(&out, temperature: temperature, forces: forces, pinned: pinned, random: &rng)90 }91 return out92 }9394 /// One step: every movable card is pushed away from the cards it is too close to and pulled along its edges,95 /// then moved by at most `forces.maxStep × temperature`. Cards at the same centre are separated in a direction96 /// drawn from `random`. Positions are rounded to 1/100 of a unit.97 public static func step(_ document: inout CanvasDocument, temperature: Double = 1, forces: Forces = Forces(), pinned: Set<String> = [],98 random: inout CanvasLayoutRandom) {99 let count = document.nodes.count100 guard count > 0 else { return }101 var cx = [Double](repeating: 0, count: count), cy = cx, radius = cx102 var index: [String: Int] = [:]103 for (i, node) in document.nodes.enumerated() {104 let w = max(0, node.w), h = max(0, node.h)105 cx[i] = node.x + w / 2106 cy[i] = node.y + h / 2107 radius[i] = (w * w + h * h).squareRoot() / 2108 if index[node.id] == nil { index[node.id] = i }109 }110 let spacing = forces.spacing.isFinite ? max(0, forces.spacing) : 0111 var fx = [Double](repeating: 0, count: count), fy = fx112 for i in 0..<count {113 for j in (i + 1)..<max(i + 1, count) where j < count {114 var dx = cx[i] - cx[j], dy = cy[i] - cy[j]115 var d = (dx * dx + dy * dy).squareRoot()116 if d < 1e-6 {117 dx = random.signedUnit()118 dy = random.signedUnit()119 if abs(dx) < 1e-3, abs(dy) < 1e-3 { dx = 1 }120 d = (dx * dx + dy * dy).squareRoot()121 dx /= d; dy /= d122 d = 0123 } else {124 dx /= d; dy /= d125 }126 let rest = radius[i] + radius[j] + spacing127 guard d < rest else { continue }128 let push = (rest - d) * forces.repulsion129 fx[i] += dx * push; fy[i] += dy * push130 fx[j] -= dx * push; fy[j] -= dy * push131 }132 }133 for edge in document.edges {134 guard let a = index[edge.from], let b = index[edge.to], a != b else { continue }135 let dx = cx[b] - cx[a], dy = cy[b] - cy[a]136 let d = (dx * dx + dy * dy).squareRoot()137 let rest = radius[a] + radius[b] + spacing138 guard d > rest, d > 1e-6 else { continue }139 let pull = (d - rest) * forces.attraction140 fx[a] += dx / d * pull; fy[a] += dy / d * pull141 fx[b] -= dx / d * pull; fy[b] -= dy / d * pull142 }143 let limit = max(0, forces.maxStep.isFinite ? forces.maxStep : 0) * min(1, max(0, temperature.isFinite ? temperature : 0))144 for i in 0..<count where !pinned.contains(document.nodes[i].id) {145 var mx = fx[i], my = fy[i]146 let m = (mx * mx + my * my).squareRoot()147 guard m.isFinite, m > 0 else { continue }148 if m > limit { mx = mx / m * limit; my = my / m * limit }149 let nx = ((document.nodes[i].x + mx) * 100).rounded() / 100150 let ny = ((document.nodes[i].y + my) * 100).rounded() / 100151 guard nx.isFinite, ny.isFinite else { continue }152 if nx != document.nodes[i].x { document.nodes[i].x = nx }153 if ny != document.nodes[i].y { document.nodes[i].y = ny }154 }155 }156157 // MARK: Measures158159 /// Total area shared by pairs of cards (0 = no overlap).160 public static func overlapArea(_ document: CanvasDocument) -> Double {161 var total = 0.0162 let frames = document.nodes.map(\.frame)163 for i in frames.indices {164 for j in frames.indices where j > i {165 let r = frames[i].intersection(frames[j])166 if !r.isNull, r.width > 0, r.height > 0 { total += Double(r.width * r.height) }167 }168 }169 return total170 }171172 /// What the force-directed layout minimises: for each pair of cards, the square of how much closer they are173 /// than their rest distance; for each edge, the square of how much longer it is than its rest length174 /// (weighted like the forces).175 public static func energy(_ document: CanvasDocument, forces: Forces = Forces()) -> Double {176 let nodes = document.nodes177 func centre(_ n: CanvasNode) -> (Double, Double, Double) {178 let w = max(0, n.w), h = max(0, n.h)179 return (n.x + w / 2, n.y + h / 2, (w * w + h * h).squareRoot() / 2)180 }181 let c = nodes.map(centre)182 var e = 0.0183 for i in c.indices {184 for j in c.indices where j > i {185 let d = ((c[i].0 - c[j].0) * (c[i].0 - c[j].0) + (c[i].1 - c[j].1) * (c[i].1 - c[j].1)).squareRoot()186 let rest = c[i].2 + c[j].2 + forces.spacing187 if d < rest { e += forces.repulsion * (rest - d) * (rest - d) }188 }189 }190 var index: [String: Int] = [:]191 for (i, n) in nodes.enumerated() where index[n.id] == nil { index[n.id] = i }192 for edge in document.edges {193 guard let a = index[edge.from], let b = index[edge.to], a != b else { continue }194 let d = ((c[a].0 - c[b].0) * (c[a].0 - c[b].0) + (c[a].1 - c[b].1) * (c[a].1 - c[b].1)).squareRoot()195 let rest = c[a].2 + c[b].2 + forces.spacing196 if d > rest { e += forces.attraction * (d - rest) * (d - rest) }197 }198 return e199 }200}201