From 129bca332b68bd6106079f58bd0de77baf21ec68 Mon Sep 17 00:00:00 2001 From: Ruben Beltran del Rio Date: Mon, 7 Jul 2025 21:52:16 +0200 Subject: Take Notes into account in smart labels --- .../SmartLabelPositioning.swift | 376 +++++++++++++++++++++ 1 file changed, 376 insertions(+) create mode 100644 Map/Business/SmartLabelPositioning/SmartLabelPositioning.swift (limited to 'Map/Business/SmartLabelPositioning/SmartLabelPositioning.swift') diff --git a/Map/Business/SmartLabelPositioning/SmartLabelPositioning.swift b/Map/Business/SmartLabelPositioning/SmartLabelPositioning.swift new file mode 100644 index 0000000..f765108 --- /dev/null +++ b/Map/Business/SmartLabelPositioning/SmartLabelPositioning.swift @@ -0,0 +1,376 @@ +// Copyright (C) 2024 Rubén Beltrán del Río + +// This program is free software: you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +import AppKit +// You should have received a copy of the GNU General Public License +// along with this program. If not, see https://map.tranquil.systems. +import CoreGraphics + +struct SmartLabelPositioning { + + static func calculateOptimalLabelPosition( + for vertex: Vertex, + mapSize: CGSize, + vertexSize: CGSize, + edges: [MapEdge], + opportunities: [Opportunity], + inertias: [Inertia], + axisLines: [Line], + allVertices: [Vertex] = [], + notes: [Note] = [] + ) -> CGPoint { + let vertexPixelPos = CGPoint( + x: w(vertex.position.x, mapSize: mapSize), + y: h(vertex.position.y, mapSize: mapSize) + ) + + let actualLabelSize = calculateLabelSize(for: vertex.label) + + let candidatePositions = generateCandidatePositions( + vertexPixelPos: vertexPixelPos, + vertexSize: vertexSize, + labelSize: actualLabelSize + ) + + let allLines = collectAllLines( + edges: edges, + opportunities: opportunities, + inertias: inertias, + axisLines: axisLines, + mapSize: mapSize, + vertexSize: vertexSize + ) + + let noteRects = collectNoteRects( + notes: notes, + mapSize: mapSize + ) + + let defaultPosition = candidatePositions[0] + + let defaultRect = CGRect(origin: defaultPosition, size: actualLabelSize) + if countCollisions(labelRect: defaultRect, lines: allLines) == 0 + && countNoteCollisions(labelRect: defaultRect, noteRects: noteRects) == 0 + { + return defaultPosition + } + + var bestPosition = defaultPosition + var bestScore = Double.infinity + + for (index, position) in candidatePositions.enumerated() { + let labelRect = CGRect( + origin: position, + size: actualLabelSize + ) + + let collisionCount = countCollisions(labelRect: labelRect, lines: allLines) + let noteCollisionCount = countNoteCollisions(labelRect: labelRect, noteRects: noteRects) + let distance = sqrt( + pow(position.x - (vertexPixelPos.x + vertexSize.width / 2), 2) + + pow(position.y - (vertexPixelPos.y + vertexSize.height / 2), 2)) + + let ownershipPenalty = calculateOwnershipPenalty( + labelRect: labelRect, + ownVertex: vertex, + allVertices: allVertices, + mapSize: mapSize, + vertexSize: vertexSize + ) + + let score = + Double(collisionCount * 100) + Double(noteCollisionCount * 500) + distance * 0.5 + Double( + index) * 0.1 + ownershipPenalty + + if score < bestScore { + bestScore = score + bestPosition = position + } + } + + return bestPosition + } + + private static func calculateLabelSize(for text: String) -> CGSize { + let cleanText = text.replacingOccurrences(of: "\\n", with: "\n") + let font = NSFont.systemFont(ofSize: 11) + let attributes: [NSAttributedString.Key: Any] = [.font: font] + let size = cleanText.boundingRect( + with: CGSize(width: CGFloat.greatestFiniteMagnitude, height: CGFloat.greatestFiniteMagnitude), + options: [.usesLineFragmentOrigin, .usesFontLeading], + attributes: attributes, + context: nil + ).size + + return CGSize(width: ceil(size.width) + 4, height: ceil(size.height) + 2) + } + + private static func calculateOwnershipPenalty( + labelRect: CGRect, + ownVertex: Vertex, + allVertices: [Vertex], + mapSize: CGSize, + vertexSize: CGSize + ) -> Double { + guard !allVertices.isEmpty else { return 0 } + + let labelCenter = CGPoint( + x: labelRect.midX, + y: labelRect.midY + ) + + let ownVertexPixelPos = CGPoint( + x: w(ownVertex.position.x, mapSize: mapSize), + y: h(ownVertex.position.y, mapSize: mapSize) + ) + let ownVertexCenter = CGPoint( + x: ownVertexPixelPos.x + vertexSize.width / 2, + y: ownVertexPixelPos.y + vertexSize.height / 2 + ) + + let distanceToOwnVertex = sqrt( + pow(labelCenter.x - ownVertexCenter.x, 2) + pow(labelCenter.y - ownVertexCenter.y, 2) + ) + + for otherVertex in allVertices { + if otherVertex.id == ownVertex.id { continue } + + let otherVertexPixelPos = CGPoint( + x: w(otherVertex.position.x, mapSize: mapSize), + y: h(otherVertex.position.y, mapSize: mapSize) + ) + let otherVertexCenter = CGPoint( + x: otherVertexPixelPos.x + vertexSize.width / 2, + y: otherVertexPixelPos.y + vertexSize.height / 2 + ) + + let distanceToOtherVertex = sqrt( + pow(labelCenter.x - otherVertexCenter.x, 2) + pow(labelCenter.y - otherVertexCenter.y, 2) + ) + + if distanceToOtherVertex < distanceToOwnVertex { + return 50.0 + } + } + + return 0 + } + + private static func generateCandidatePositions( + vertexPixelPos: CGPoint, + vertexSize: CGSize, + labelSize: CGSize + ) -> [CGPoint] { + let padding = CGFloat(5.0) + + return [ + CGPoint( + x: vertexPixelPos.x + vertexSize.width + padding, + y: vertexPixelPos.y + (vertexSize.height - labelSize.height) / 2 + ), + CGPoint( + x: vertexPixelPos.x - labelSize.width - padding, + y: vertexPixelPos.y + (vertexSize.height - labelSize.height) / 2 + ), + CGPoint( + x: vertexPixelPos.x + (vertexSize.width - labelSize.width) / 2, + y: vertexPixelPos.y - labelSize.height - padding + ), + CGPoint( + x: vertexPixelPos.x + (vertexSize.width - labelSize.width) / 2, + y: vertexPixelPos.y + vertexSize.height + padding + ), + CGPoint( + x: vertexPixelPos.x + vertexSize.width + padding, + y: vertexPixelPos.y - labelSize.height - padding + ), + CGPoint( + x: vertexPixelPos.x - labelSize.width - padding, + y: vertexPixelPos.y - labelSize.height - padding + ), + CGPoint( + x: vertexPixelPos.x + vertexSize.width + padding, + y: vertexPixelPos.y + vertexSize.height + padding + ), + CGPoint( + x: vertexPixelPos.x - labelSize.width - padding, + y: vertexPixelPos.y + vertexSize.height + padding + ), + ] + } + + private static func collectAllLines( + edges: [MapEdge], + opportunities: [Opportunity], + inertias: [Inertia], + axisLines: [Line], + mapSize: CGSize, + vertexSize: CGSize + ) -> [Line] { + var lines: [Line] = [] + + for edge in edges { + let origin = CGPoint( + x: w(edge.origin.x, mapSize: mapSize), y: h(edge.origin.y, mapSize: mapSize)) + let destination = CGPoint( + x: w(edge.destination.x, mapSize: mapSize), y: h(edge.destination.y, mapSize: mapSize)) + + let slope = (destination.y - origin.y) / (destination.x - origin.x) + let angle = atan(slope) + let multiplier = CGFloat(slope < 0 ? -1.0 : 1.0) + + let offsetOrigin = CGPoint( + x: origin.x + multiplier * (vertexSize.width / 2.0) * cos(angle), + y: origin.y + multiplier * (vertexSize.height / 2.0) * sin(angle) + ) + let offsetDestination = CGPoint( + x: destination.x - multiplier * (vertexSize.width / 2.0) * cos(angle), + y: destination.y - multiplier * (vertexSize.height / 2.0) * sin(angle) + ) + + let adjustedOrigin = CGPoint( + x: offsetOrigin.x + vertexSize.width / 2.0, + y: offsetOrigin.y + vertexSize.height / 2.0 + ) + let adjustedDestination = CGPoint( + x: offsetDestination.x + vertexSize.width / 2.0, + y: offsetDestination.y + vertexSize.height / 2.0 + ) + + lines.append(Line(start: adjustedOrigin, end: adjustedDestination)) + } + + for opportunity in opportunities { + let origin = CGPoint( + x: w(opportunity.origin.x, mapSize: mapSize), y: h(opportunity.origin.y, mapSize: mapSize)) + let destination = CGPoint( + x: w(opportunity.destination.x, mapSize: mapSize), + y: h(opportunity.destination.y, mapSize: mapSize)) + + let multiplier = CGFloat(opportunity.destination.x > opportunity.origin.x ? 1.0 : -1.0) + + let offsetOrigin = CGPoint( + x: origin.x + multiplier * (vertexSize.width / 2.0), + y: origin.y + ) + let offsetDestination = CGPoint( + x: destination.x - multiplier * (vertexSize.width / 2.0), + y: destination.y + ) + + let adjustedOrigin = CGPoint( + x: offsetOrigin.x + vertexSize.width / 2.0, + y: offsetOrigin.y + vertexSize.height / 2.0 + ) + let adjustedDestination = CGPoint( + x: offsetDestination.x + vertexSize.width / 2.0, + y: offsetDestination.y + vertexSize.height / 2.0 + ) + + lines.append(Line(start: adjustedOrigin, end: adjustedDestination)) + } + + lines.append(contentsOf: axisLines) + + return lines + } + + private static func countCollisions(labelRect: CGRect, lines: [Line]) -> Int { + var collisions = 0 + + for line in lines { + if lineIntersectsRect(line: line, rect: labelRect) { + collisions += 1 + } + } + + return collisions + } + + private static func lineIntersectsRect(line: Line, rect: CGRect) -> Bool { + let rectLines = [ + Line(start: CGPoint(x: rect.minX, y: rect.minY), end: CGPoint(x: rect.maxX, y: rect.minY)), + Line(start: CGPoint(x: rect.maxX, y: rect.minY), end: CGPoint(x: rect.maxX, y: rect.maxY)), + Line(start: CGPoint(x: rect.maxX, y: rect.maxY), end: CGPoint(x: rect.minX, y: rect.maxY)), + Line(start: CGPoint(x: rect.minX, y: rect.maxY), end: CGPoint(x: rect.minX, y: rect.minY)), + ] + + for rectLine in rectLines { + if linesIntersect(line1: line, line2: rectLine) { + return true + } + } + + return rect.contains(line.start) || rect.contains(line.end) + } + + private static func linesIntersect(line1: Line, line2: Line) -> Bool { + let x1 = line1.start.x + let y1 = line1.start.y + let x2 = line1.end.x + let y2 = line1.end.y + let x3 = line2.start.x + let y3 = line2.start.y + let x4 = line2.end.x + let y4 = line2.end.y + + let denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4) + + if abs(denom) < 1e-10 { + return false + } + + let t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom + let u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom + + return t >= 0 && t <= 1 && u >= 0 && u <= 1 + } + + private static func w(_ dimension: CGFloat, mapSize: CGSize) -> CGFloat { + max(0.0, min(mapSize.width, dimension * mapSize.width / 100.0)) + } + + private static func collectNoteRects( + notes: [Note], + mapSize: CGSize + ) -> [CGRect] { + return notes.map { note in + let notePixelPos = CGPoint( + x: w(note.position.x, mapSize: mapSize), + y: h(note.position.y, mapSize: mapSize) + ) + let noteSize = calculateLabelSize(for: note.text) + return CGRect(origin: notePixelPos, size: noteSize) + } + } + + private static func countNoteCollisions(labelRect: CGRect, noteRects: [CGRect]) -> Int { + var collisions = 0 + + for noteRect in noteRects { + if labelRect.intersects(noteRect) { + collisions += 1 + } + } + + return collisions + } + + private static func h(_ dimension: CGFloat, mapSize: CGSize) -> CGFloat { + max(0.0, min(mapSize.height, dimension * mapSize.height / 100.0)) + } +} + +struct Line { + let start: CGPoint + let end: CGPoint +} -- cgit