Finds the closest point along a Bezier path to a given arbitrary point

FindClosestPointOnBezierPath.swift

// Made to answer http://stackoverflow.com/questions/38512761/how-do-i-find-the-x-y-coordinates-of-the-point-q-on-a-closed-2d-composite-bez

struct BezierPoint {
	let q0: CGPoint
	let point: CGPoint
	let q1: CGPoint
}

struct SimpleBezierCurve {
	let left: BezierPoint
	let right: BezierPoint
}

class BezierPath {
	var pathPoints = [BezierPoint]()
	
	func findClosestPoint(to targetPoint: CGPoint) -> CGPoint {
		let segments = allSegments()
		guard segments.count > 0 else { return targetPoint }
		var closestPoint = (distance: CGFloat.infinity, point: CGPoint(x: CGFloat.infinity, y: CGFloat.infinity))
		segments.forEach{ curve in
			let thisPoint = BezierPath.findClosestPoint(to: targetPoint, along: curve)
			let distance = findDistance(from: targetPoint, to: thisPoint)
			
			if (distance < closestPoint.distance) {
				closestPoint = (distance: distance, point: thisPoint)
			}
		}
		return closestPoint.point
	}
	
	func allSegments() -> [SimpleBezierCurve] {
		guard pathPoints.count > 0 else { return [] }
		var segments = [SimpleBezierCurve]()
		var prevPoint = pathPoints[0]
		for i in 1 ..< pathPoints.count {
			let thisPoint = pathPoints[i]
			segments.append(SimpleBezierCurve(left: prevPoint, right: thisPoint))
			prevPoint = thisPoint
		}
		segments.append(SimpleBezierCurve(left: prevPoint, right: pathPoints[0]))
		return segments
	}
	
	static func findClosestPoint(to point: CGPoint, along curve: SimpleBezierCurve) -> CGPoint {
		return findClosestPointToCubicBezier(to: point, slices: 10, iterations: 10, along: curve)
	}

	// Adapted from http://stackoverflow.com/a/34520607/3939277
	static func findClosestPointToCubicBezier(to target: CGPoint, slices: Int, iterations: Int, along curve: SimpleBezierCurve) -> CGPoint {
		return findClosestPointToCubicBezier(iterations: iterations, to: target, start: 0, end: 1, slices: slices, along: curve)
	}
	
	// Adapted from http://stackoverflow.com/a/34520607/3939277
	private static func findClosestPointToCubicBezier(iterations iterations: Int, to: CGPoint, start: CGFloat, end: CGFloat, slices: Int, along curve: SimpleBezierCurve) -> CGPoint {
		if iterations <= 0 {
			let position = (start + end) / 2
			let point = self.point(for: position, along: curve)
			return point
		}
		let tick = (end - start) / slices
		var best = CGFloat(0)
		var bestDistance = CGFloat.infinity
		var currentDistance: CGFloat
		var t = start
		
		while (t <= end) {
			//B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
			let point = self.point(for: t, along: curve)
			
			var dx = point.x - to.x;
			var dy = point.y - to.y;
			dx *= dx;
			dy *= dy;
			currentDistance = dx + dy;
			if (currentDistance < bestDistance) {
				bestDistance = currentDistance;
				best = t;
			}
			t += tick;
		}
		return findClosestPointToCubicBezier(iterations: iterations - 1, to: to, start: max(best - tick, 0.0), end: min(best + tick, 1.0), slices: slices, along: curve);
	}
	
	static func point(for t: CGFloat, along curve: SimpleBezierCurve) -> CGPoint {
		// This had to be broken up to avoid the "Expression too complex" error
		
		let x0 = curve.left.point.x
		let x1 = curve.left.q1.x
		let x2 = curve.right.q0.x
		let x3 = curve.right.point.x
		
		let y0 = curve.left.point.y
		let y1 = curve.left.q1.y
		let y2 = curve.right.q0.y
		let y3 = curve.right.point.y
		
		let x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3
		let y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3
		
		return CGPoint(x: x, y: y)
	}
}

// Possibly in another file
func findDistance(from a: CGPoint, to b: CGPoint) -> CGFloat {
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

For a little speed gain you don't need the sqrt() operation in findDistance, because you don't care about the actual distance, just how the distances compare to each other.

For example, for a given point (0, 0) , and a set of points

(1,0)
(1,1)
(2,0)
(2,1)
(2,2)

Both sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)) and (pow(a.x - b.x, 2) + pow(a.y - b.y, 2)) will return the same 'nearest point'