SPB Git

Repository Public

CanvasLayout.swift 9.6 KB 201 lines swift

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
Files main
Menu

Theme