Repository Public
1// SP Notes iOS2// File: Core/Ink/ShapeRecognizer.swift3// Description: Smart shapes: recognises a line, an arrow, a rectangle, a triangle or an ellipse / circle in the points of one4// hand-drawn stroke. Pure geometry (resampling, corner detection, closedness, least-squares fits, a confidence5// threshold); no machine learning, no UI framework. Anything that is not clearly one of the five shapes is left alone.6//7// Author: Simon-Pierre Boucher8// Contact: contact@spboucher.ai9import CoreGraphics10import Foundation1112/// A clean shape, in the coordinates of the stroke it was recognised from.13enum RecognizedShape: Equatable, Sendable {14 case line(from: CGPoint, to: CGPoint)15 /// The head is at `to`.16 case arrow(from: CGPoint, to: CGPoint)17 /// `rotation` in radians, in (−π/4, π/4]: the angle of the side called `width`.18 case rectangle(center: CGPoint, size: CGSize, rotation: CGFloat)19 /// `radii.width` along the axis at `rotation` (radians), `radii.height` across. A circle has equal radii and rotation 0.20 case ellipse(center: CGPoint, radii: CGSize, rotation: CGFloat)21 case triangle(CGPoint, CGPoint, CGPoint)2223 enum Kind: String, Sendable { case line, arrow, rectangle, ellipse, triangle }2425 var kind: Kind {26 switch self {27 case .line: .line28 case .arrow: .arrow29 case .rectangle: .rectangle30 case .ellipse: .ellipse31 case .triangle: .triangle32 }33 }3435 /// The corners of a rectangle, clockwise on screen from the top-left one of the unrotated box.36 static func corners(center: CGPoint, size: CGSize, rotation: CGFloat) -> [CGPoint] {37 let c = cos(rotation), s = sin(rotation), w = size.width / 2, h = size.height / 238 return [(-w, -h), (w, -h), (w, h), (-w, h)].map { CGPoint(x: center.x + $0.0 * c - $0.1 * s, y: center.y + $0.0 * s + $0.1 * c) }39 }4041 /// The two barbs of an arrow head at `to`.42 static func arrowHead(from: CGPoint, to: CGPoint) -> (CGPoint, CGPoint) {43 let length = hypot(to.x - from.x, to.y - from.y)44 guard length > 0 else { return (to, to) }45 let barb = min(max(length * 0.22, 10), 28), angle = atan2(from.y - to.y, from.x - to.x), spread = CGFloat.pi / 746 return (CGPoint(x: to.x + barb * cos(angle + spread), y: to.y + barb * sin(angle + spread)),47 CGPoint(x: to.x + barb * cos(angle - spread), y: to.y + barb * sin(angle - spread)))48 }4950 /// The outline as polylines whose vertices are the corners of the shape (an ellipse is sampled every few degrees).51 var outlines: [[CGPoint]] {52 switch self {53 case .line(let a, let b): return [[a, b]]54 case .arrow(let a, let b):55 let (l, r) = Self.arrowHead(from: a, to: b)56 return [[a, b], [l, b, r]]57 case .rectangle(let center, let size, let rotation):58 let c = Self.corners(center: center, size: size, rotation: rotation)59 return [c + [c[0]]]60 case .triangle(let a, let b, let c): return [[a, b, c, a]]61 case .ellipse(let center, let radii, let rotation):62 let c = cos(rotation), s = sin(rotation), n = 7263 return [(0...n).map { i -> CGPoint in64 let t = CGFloat(i % n) / CGFloat(n) * 2 * .pi, x = radii.width * cos(t), y = radii.height * sin(t)65 return CGPoint(x: center.x + x * c - y * s, y: center.y + x * s + y * c)66 }]67 }68 }6970 /// True for the outlines whose vertices are sharp corners (everything but the ellipse).71 var hasCorners: Bool { kind != .ellipse }72}7374struct ShapeMatch: Equatable, Sendable {75 var shape: RecognizedShape76 /// 0…1: 1 = the stroke lies exactly on the shape.77 var confidence: Double78}7980enum ShapeRecognizer {81 struct Options: Sendable {82 /// Below this the stroke is left as drawn.83 var minimumConfidence = 0.5584 /// Strokes smaller than this (diagonal of their box, in points) are never shapes: dots, commas, small letters.85 var minimumSize: CGFloat = 2886 /// A rectangle within this angle of the axes is made upright; a line within it is made horizontal / vertical.87 var snapAngle: CGFloat = 5 * .pi / 18088 static let standard = Options()89 }9091 static func recognize(_ raw: [CGPoint], options: Options = .standard) -> ShapeMatch? {92 let input = dedupe(raw.filter { $0.x.isFinite && $0.y.isFinite })93 guard input.count >= 3 else { return nil }94 let box = bounds(input), diagonal = hypot(box.width, box.height)95 guard diagonal >= options.minimumSize else { return nil }96 let length = pathLength(input)97 guard length > 0 else { return nil }9899 var candidates: [ShapeMatch] = []100 if let closed = closedLoop(input, length: length) {101 let loop = resample(closed, count: 128)102 if let polygon = polygon(loop, diagonal: diagonal, options: options) { candidates.append(polygon) }103 if let ellipse = ellipse(loop, options: options) { candidates.append(ellipse) }104 } else {105 let points = resample(input, count: 96)106 if let line = line(points, length: length, options: options) { candidates.append(line) }107 else if let arrow = arrow(points, diagonal: diagonal) { candidates.append(arrow) }108 }109 guard let best = candidates.max(by: { $0.confidence < $1.confidence }), best.confidence >= options.minimumConfidence else { return nil }110 return best111 }112113 // MARK: line114115 private static func line(_ points: [CGPoint], length: CGFloat, options: Options) -> ShapeMatch? {116 guard let first = points.first, let last = points.last else { return nil }117 let chord = distance(first, last)118 // the length of the stroke without the tremor of the hand119 let steady = pathLength(smoothedOpen(points, window: 2))120 guard chord > 0, steady / chord < 1.06 else { return nil }121 let (centroid, direction) = principalAxis(points)122 let normal = CGPoint(x: -direction.y, y: direction.x)123 var worst: CGFloat = 0, sum: CGFloat = 0124 for p in points {125 let d = abs((p.x - centroid.x) * normal.x + (p.y - centroid.y) * normal.y)126 worst = max(worst, d); sum += d127 }128 let mean = sum / CGFloat(points.count)129 let error = max(worst / chord / 0.05, mean / chord / 0.02)130 guard error < 1 else { return nil }131 func project(_ p: CGPoint) -> CGPoint {132 let t = (p.x - centroid.x) * direction.x + (p.y - centroid.y) * direction.y133 return CGPoint(x: centroid.x + t * direction.x, y: centroid.y + t * direction.y)134 }135 var a = project(first), b = project(last)136 let angle = atan2(b.y - a.y, b.x - a.x)137 // nearly horizontal or vertical: made exactly so, around the middle of the line138 let mid = CGPoint(x: (a.x + b.x) / 2, y: (a.y + b.y) / 2), half = distance(a, b) / 2139 for target in [0, CGFloat.pi / 2, .pi, -CGFloat.pi / 2, -.pi] where abs(angle - target) < options.snapAngle {140 a = CGPoint(x: mid.x - half * cos(target), y: mid.y - half * sin(target))141 b = CGPoint(x: mid.x + half * cos(target), y: mid.y + half * sin(target))142 }143 return ShapeMatch(shape: .line(from: a, to: b), confidence: Double(1 - error * 0.5))144 }145146 // MARK: arrow147148 /// A one-stroke arrow: the shaft, then the head drawn without lifting — barb, back to the tip, other barb (`A T B T B`), or149 /// the head closed as a small triangle (`A T B B T`).150 private static func arrow(_ points: [CGPoint], diagonal: CGFloat) -> ShapeMatch? {151 let vertices = mergeClose(simplify(points, tolerance: diagonal * 0.035), minimum: diagonal * 0.05)152 guard vertices.count == 5 else { return nil }153 let tail = vertices[0], tip = vertices[1], shaft = distance(tail, tip)154 guard shaft > diagonal * 0.6 else { return nil }155 let barbs: [CGPoint]156 if distance(vertices[3], tip) < shaft * 0.14 { barbs = [vertices[2], vertices[4]] } // A T B T B157 else if distance(vertices[4], tip) < shaft * 0.14 { barbs = [vertices[2], vertices[3]] } // A T B B T158 else { return nil }159 let back = atan2(tail.y - tip.y, tail.x - tip.x)160 var sides: [CGFloat] = [], error: CGFloat = 0161 for barb in barbs {162 let length = distance(barb, tip)163 guard length > shaft * 0.07, length < shaft * 0.6 else { return nil }164 let angle = normalized(atan2(barb.y - tip.y, barb.x - tip.x) - back)165 guard abs(angle) > 10 * .pi / 180, abs(angle) < 75 * .pi / 180 else { return nil }166 sides.append(angle)167 error = max(error, abs(abs(angle) - .pi / 6) / (.pi / 3))168 }169 guard sides[0] * sides[1] < 0 else { return nil } // one barb on each side of the shaft170 // the shaft itself must be straight171 let shaftPoints = points.prefix { distance($0, tip) > shaft * 0.05 }172 let deviation = shaftPoints.map { segmentDistance($0, tail, tip) }.max() ?? 0173 guard deviation / shaft < 0.06 else { return nil }174 error = max(error, deviation / shaft / 0.06)175 return ShapeMatch(shape: .arrow(from: tail, to: tip), confidence: Double(1 - error * 0.45))176 }177178 // MARK: polygons (triangle, rectangle)179180 private static func polygon(_ loop: [CGPoint], diagonal: CGFloat, options: Options) -> ShapeMatch? {181 // start at the point farthest from the centroid — a corner of any polygon — so no corner is split by the closure182 let centroid = mean(loop)183 guard let start = loop.indices.max(by: { distance(loop[$0], centroid) < distance(loop[$1], centroid) }) else { return nil }184 let rotated = Array(loop[start...] + loop[..<start]) + [loop[start]]185 var vertices = mergeClose(simplify(rotated, tolerance: diagonal * 0.045), minimum: diagonal * 0.08)186 while vertices.count > 1, distance(vertices[0], vertices[vertices.count - 1]) < diagonal * 0.08 { vertices.removeLast() }187 vertices = dropFlat(vertices, maximumAngle: 152 * .pi / 180)188 guard vertices.count == 3 || vertices.count == 4 else { return nil }189 // every point of the stroke must lie near the polygon190 var sum: CGFloat = 0, worst: CGFloat = 0191 for p in loop {192 var best = CGFloat.infinity193 for i in vertices.indices { best = min(best, segmentDistance(p, vertices[i], vertices[(i + 1) % vertices.count])) }194 sum += best; worst = max(worst, best)195 }196 let error = max(sum / CGFloat(loop.count) / diagonal / 0.022, worst / diagonal / 0.075)197 guard error < 1 else { return nil }198 let confidence = Double(1 - error * 0.45)199200 if vertices.count == 3 {201 let angles = interiorAngles(vertices)202 guard angles.allSatisfy({ $0 > 14 * .pi / 180 }) else { return nil }203 return ShapeMatch(shape: .triangle(vertices[0], vertices[1], vertices[2]), confidence: confidence)204 }205 let angles = interiorAngles(vertices)206 guard angles.allSatisfy({ abs($0 - .pi / 2) < 20 * .pi / 180 }) else { return nil }207 let sides = (0..<4).map { distance(vertices[$0], vertices[($0 + 1) % 4]) }208 guard min(sides[0], sides[2]) / max(sides[0], sides[2]) > 0.72, min(sides[1], sides[3]) / max(sides[1], sides[3]) > 0.72 else { return nil }209 // orientation: the mean direction of the four sides, modulo a quarter turn210 var sx: CGFloat = 0, sy: CGFloat = 0211 for i in 0..<4 {212 let a = vertices[i], b = vertices[(i + 1) % 4], angle = atan2(b.y - a.y, b.x - a.x) * 4213 sx += cos(angle) * sides[i]; sy += sin(angle) * sides[i]214 }215 var rotation = atan2(sy, sx) / 4 // in (−π/4, π/4]216 if abs(rotation) < options.snapAngle { rotation = 0 }217 let c = cos(-rotation), s = sin(-rotation)218 let local = vertices.map { CGPoint(x: $0.x * c - $0.y * s, y: $0.x * s + $0.y * c) }219 let xs = local.map(\.x).sorted(), ys = local.map(\.y).sorted()220 // each side of the box is the mean of the two corners that define it221 let minX = (xs[0] + xs[1]) / 2, maxX = (xs[2] + xs[3]) / 2, minY = (ys[0] + ys[1]) / 2, maxY = (ys[2] + ys[3]) / 2222 let lc = CGPoint(x: (minX + maxX) / 2, y: (minY + maxY) / 2)223 let center = CGPoint(x: lc.x * cos(rotation) - lc.y * sin(rotation), y: lc.x * sin(rotation) + lc.y * cos(rotation))224 return ShapeMatch(shape: .rectangle(center: center, size: CGSize(width: maxX - minX, height: maxY - minY), rotation: rotation), confidence: confidence)225 }226227 // MARK: ellipse228229 private static func ellipse(_ loop: [CGPoint], options: Options) -> ShapeMatch? {230 // one turn, always the same way231 var winding: CGFloat = 0232 let smooth = smoothed(loop, window: 3)233 // along the stroke as drawn (the closing jump from its end to its start is not a turn of the pen)234 for i in 0..<max(0, smooth.count - 2) {235 let a = smooth[i], b = smooth[i + 1], c = smooth[i + 2]236 winding += normalized(atan2(c.y - b.y, c.x - b.x) - atan2(b.y - a.y, b.x - a.x))237 }238 guard abs(winding) > 1.6 * .pi, abs(winding) < 2.5 * .pi else { return nil }239 let (centroid, direction) = principalAxis(loop)240 let c = direction.x, s = direction.y241 let local = loop.map { CGPoint(x: ($0.x - centroid.x) * c + ($0.y - centroid.y) * s, y: -($0.x - centroid.x) * s + ($0.y - centroid.y) * c) }242 let minX = local.map(\.x).min() ?? 0, maxX = local.map(\.x).max() ?? 0, minY = local.map(\.y).min() ?? 0, maxY = local.map(\.y).max() ?? 0243 var a = (maxX - minX) / 2, b = (maxY - minY) / 2244 guard a > 4, b > 4, b / a > 0.12 else { return nil }245 let lc = CGPoint(x: (minX + maxX) / 2, y: (minY + maxY) / 2)246 var sum: CGFloat = 0, worst: CGFloat = 0247 for p in local {248 let r = sqrt(pow((p.x - lc.x) / a, 2) + pow((p.y - lc.y) / b, 2))249 sum += (r - 1) * (r - 1); worst = max(worst, abs(r - 1))250 }251 let rms = sqrt(sum / CGFloat(local.count))252 let error = max(rms / 0.085, worst / 0.24)253 guard error < 1 else { return nil }254 let center = CGPoint(x: centroid.x + lc.x * c - lc.y * s, y: centroid.y + lc.x * s + lc.y * c)255 var rotation = atan2(s, c)256 if abs(a - b) / max(a, b) < 0.12 {257 // nearly round: a circle258 a = (a + b) / 2; b = a; rotation = 0259 } else {260 rotation = normalizedHalfTurn(rotation)261 for target in [0, CGFloat.pi / 2, -CGFloat.pi / 2] where abs(rotation - target) < options.snapAngle { rotation = target }262 }263 return ShapeMatch(shape: .ellipse(center: center, radii: CGSize(width: a, height: b), rotation: rotation), confidence: Double(1 - error * 0.45))264 }265266 // MARK: closedness267268 /// The stroke as a closed loop (ends trimmed where they overlap), or nil when it is open.269 private static func closedLoop(_ points: [CGPoint], length: CGFloat) -> [CGPoint]? {270 guard let first = points.first, let last = points.last else { return nil }271 // where the end of the stroke comes closest to its start (the pen often goes a little past it)272 let tailStart = Int(Double(points.count) * 0.8)273 guard tailStart > 2, let nearest = (tailStart..<points.count).min(by: { distance(points[$0], first) < distance(points[$1], first) }) else { return nil }274 let closes = distance(first, last) / length < 0.1 || distance(points[nearest], first) / length < 0.05275 guard closes else { return nil }276 var loop = Array(points[...nearest])277 if let end = loop.last, distance(end, first) < 0.5, loop.count > 3 { loop.removeLast() }278 return loop279 }280281 // MARK: geometry282283 static func distance(_ a: CGPoint, _ b: CGPoint) -> CGFloat { hypot(a.x - b.x, a.y - b.y) }284285 static func pathLength(_ points: [CGPoint]) -> CGFloat {286 guard points.count > 1 else { return 0 }287 return (1..<points.count).reduce(0) { $0 + distance(points[$1 - 1], points[$1]) }288 }289290 static func bounds(_ points: [CGPoint]) -> CGRect {291 guard let first = points.first else { return .null }292 var minX = first.x, maxX = first.x, minY = first.y, maxY = first.y293 for p in points { minX = min(minX, p.x); maxX = max(maxX, p.x); minY = min(minY, p.y); maxY = max(maxY, p.y) }294 return CGRect(x: minX, y: minY, width: maxX - minX, height: maxY - minY)295 }296297 private static func dedupe(_ points: [CGPoint]) -> [CGPoint] {298 var out: [CGPoint] = []299 for p in points where out.last.map({ distance($0, p) > 0.01 }) ?? true { out.append(p) }300 return out301 }302303 private static func mean(_ points: [CGPoint]) -> CGPoint {304 let n = CGFloat(max(1, points.count))305 return CGPoint(x: points.reduce(0) { $0 + $1.x } / n, y: points.reduce(0) { $0 + $1.y } / n)306 }307308 /// `count` points at equal distances along the polyline.309 static func resample(_ points: [CGPoint], count: Int) -> [CGPoint] {310 let total = pathLength(points)311 guard points.count > 1, total > 0, count > 1 else { return points }312 let step = total / CGFloat(count - 1)313 var out: [CGPoint] = [points[0]], carried: CGFloat = 0, previous = points[0], i = 1314 while i < points.count, out.count < count - 1 {315 let d = distance(previous, points[i])316 if carried + d >= step, d > 0 {317 let t = (step - carried) / d318 let q = CGPoint(x: previous.x + t * (points[i].x - previous.x), y: previous.y + t * (points[i].y - previous.y))319 out.append(q); previous = q; carried = 0320 } else {321 carried += d; previous = points[i]; i += 1322 }323 }324 out.append(points[points.count - 1])325 return out326 }327328 /// Centroid and unit direction of the largest spread (total least squares).329 private static func principalAxis(_ points: [CGPoint]) -> (CGPoint, CGPoint) {330 let c = mean(points)331 var sxx: CGFloat = 0, sxy: CGFloat = 0, syy: CGFloat = 0332 for p in points { let dx = p.x - c.x, dy = p.y - c.y; sxx += dx * dx; sxy += dx * dy; syy += dy * dy }333 let angle = 0.5 * atan2(2 * sxy, sxx - syy)334 return (c, CGPoint(x: cos(angle), y: sin(angle)))335 }336337 static func segmentDistance(_ p: CGPoint, _ a: CGPoint, _ b: CGPoint) -> CGFloat {338 let dx = b.x - a.x, dy = b.y - a.y, len2 = dx * dx + dy * dy339 let t = len2 > 0 ? min(1, max(0, ((p.x - a.x) * dx + (p.y - a.y) * dy) / len2)) : 0340 return hypot(p.x - (a.x + t * dx), p.y - (a.y + t * dy))341 }342343 /// Ramer–Douglas–Peucker: the corners of a polyline.344 private static func simplify(_ points: [CGPoint], tolerance: CGFloat) -> [CGPoint] {345 guard points.count > 2 else { return points }346 var keep = [Bool](repeating: false, count: points.count)347 keep[0] = true; keep[points.count - 1] = true348 var stack = [(0, points.count - 1)]349 while let (a, b) = stack.popLast() {350 guard b > a + 1 else { continue }351 var worst: CGFloat = 0, index = -1352 for i in (a + 1)..<b {353 let d = segmentDistance(points[i], points[a], points[b])354 if d > worst { worst = d; index = i }355 }356 if worst > tolerance, index > 0 { keep[index] = true; stack.append((a, index)); stack.append((index, b)) }357 }358 return points.indices.filter { keep[$0] }.map { points[$0] }359 }360361 /// Consecutive vertices closer than `minimum` are merged into their middle (a corner drawn as a tiny hook).362 private static func mergeClose(_ vertices: [CGPoint], minimum: CGFloat) -> [CGPoint] {363 var out: [CGPoint] = []364 for (index, v) in vertices.enumerated() {365 if let last = out.last, distance(last, v) < minimum, index != vertices.count - 1, out.count > 1 {366 out[out.count - 1] = CGPoint(x: (last.x + v.x) / 2, y: (last.y + v.y) / 2)367 } else if let last = out.last, distance(last, v) < minimum, index == vertices.count - 1, out.count > 1 {368 out[out.count - 1] = v // the end point is kept exactly369 } else {370 out.append(v)371 }372 }373 return out374 }375376 /// Removes the vertices of a closed polygon where the outline barely turns.377 private static func dropFlat(_ vertices: [CGPoint], maximumAngle: CGFloat) -> [CGPoint] {378 var current = vertices379 while current.count > 3 {380 let angles = interiorAngles(current)381 guard let flattest = angles.indices.max(by: { angles[$0] < angles[$1] }), angles[flattest] > maximumAngle else { break }382 current.remove(at: flattest)383 }384 return current385 }386387 private static func interiorAngles(_ polygon: [CGPoint]) -> [CGFloat] {388 polygon.indices.map { i in389 let p = polygon[i], a = polygon[(i + polygon.count - 1) % polygon.count], b = polygon[(i + 1) % polygon.count]390 return abs(normalized(atan2(a.y - p.y, a.x - p.x) - atan2(b.y - p.y, b.x - p.x)))391 }392 }393394 private static func smoothed(_ loop: [CGPoint], window: Int) -> [CGPoint] {395 let n = loop.count396 guard n > 2 * window + 1 else { return loop }397 return (0..<n).map { i in398 var x: CGFloat = 0, y: CGFloat = 0399 for k in -window...window { let p = loop[(i + k + n) % n]; x += p.x; y += p.y }400 return CGPoint(x: x / CGFloat(2 * window + 1), y: y / CGFloat(2 * window + 1))401 }402 }403404 private static func smoothedOpen(_ points: [CGPoint], window: Int) -> [CGPoint] {405 let n = points.count406 guard n > 2 * window + 1 else { return points }407 return (0..<n).map { i in408 let lo = max(0, i - window), hi = min(n - 1, i + window), count = CGFloat(hi - lo + 1)409 return CGPoint(x: points[lo...hi].reduce(0) { $0 + $1.x } / count, y: points[lo...hi].reduce(0) { $0 + $1.y } / count)410 }411 }412413 /// An angle brought back to (−π, π].414 static func normalized(_ angle: CGFloat) -> CGFloat {415 var a = angle.truncatingRemainder(dividingBy: 2 * .pi)416 if a > .pi { a -= 2 * .pi }417 if a <= -.pi { a += 2 * .pi }418 return a419 }420421 /// The orientation of an axis (no direction), in (−π/2, π/2].422 static func normalizedHalfTurn(_ angle: CGFloat) -> CGFloat {423 var a = normalized(angle)424 if a > .pi / 2 { a -= .pi }425 if a <= -.pi / 2 { a += .pi }426 return a427 }428}429