1 files changed, 376 insertions, 0 deletions
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
+}