/* A big thanks to Mike Kamermans, who filled in a bunch of missing gaps in my head with his code from: http://processingjs.nihongoresources.com/bezierinfo/ */ var sketcher = [JSTCodeSketcher codeSketcherWithName:"Closest point on path to point"]; var curve = FMMakeBezierSegment(NSMakePoint(200,225), NSMakePoint(145,200), NSMakePoint(40,30), NSMakePoint(270, 115)); var MAX_ITERATIONS = 10; var mousePoint = NSMakePoint(0, 0); var globalBestT = 0; sketcher.mouseDragged = function() { mousePoint = [sketcher mouseLocation]; }; sketcher.setup = function() { [sketcher setSize:NSMakeSize(600, 300)]; [sketcher clear]; }; sketcher.drawRect = function() { [sketcher clear]; [[NSColor blueColor] set]; [curve stroke]; [[NSColor redColor] set]; var distance = FMMinDistanceForPointToCurve(mousePoint, curve, 0, 1, 0); [[NSColor greenColor] set]; FMStrokeCircleAtPoint(mousePoint, distance); [[NSColor redColor] set]; FMFillCircleAtPoint(mousePoint, 3); /* ok, that was the naive implementation above. here's a different take- I calculate 100 different points along the path and remember the t value for the point with the closest distance. Then I take that and iterate using that value (+-.1) as the starting point for narrowing down to a better value. I can still think of a couple of problems with this approach, but the number of false answers should be pretty darn small and would involve really tight turns in the curve. */ var bestT = 0; var bestDistance = FMDistanceBetweenPoints(FMPointForTInBezierSegment(curve, 0), mousePoint); int segs = 100; for (itIdx = 0; itIdx < segs; itIdx++) { var t = itIdx / segs; var p = FMPointForTInBezierSegment(curve, t); var dist = FMDistanceBetweenPoints(p, mousePoint); if (dist < bestDistance) { bestDistance = dist; bestT = t; } }; var t0 = Math.max(0, bestT-.1); var t1 = Math.min(1, bestT+.1); distance = FMMinDistanceForPointToCurve(mousePoint, curve, t0, t1, 0); [[NSColor redColor] set]; FMStrokeCircleAtPoint(mousePoint, distance); [[NSColor blackColor] set]; [NSBezierPath strokeLineFromPoint:FMPointForTInBezierSegment(curve, globalBestT) toPoint:mousePoint]; } function FMFillCircleAtPoint(point, radius) { var r = NSMakeRect(point.x-radius, point.y-radius, radius*2, radius*2); [[NSBezierPath bezierPathWithOvalInRect:r] fill]; } function FMStrokeCircleAtPoint(point, radius) { var r = NSMakeRect(point.x-radius, point.y-radius, radius*2, radius*2); [[NSBezierPath bezierPathWithOvalInRect:r] stroke]; } function FMMakeBezierSegment(spIn, epIn, cp1In, cp2In) { return { sp: spIn, ep: epIn, cp1: cp1In, cp2: cp2In, stroke: function() { if (this.cp1 && this.cp2) { var p = [NSBezierPath bezierPath]; [p moveToPoint:this.sp]; [p curveToPoint:this.ep controlPoint1:this.cp1 controlPoint2:this.cp2]; [p stroke]; } else { [NSBezierPath strokeLineFromPoint:this.sp toPoint:this.ep]; } }, } } function FMMidPoint(a, b) { return NSMakePoint((a.x + b.x)/2.0, (a.y + b.y)/2.0); } function FMDistanceBetweenPoints(a, b) { float xd = b.x - a.x; float yd = b.y - a.y; return Math.sqrt((xd * xd) + (yd * yd)); } function FMComputeCubicBaseValue(t, sp, cp1, cp2, ep) { double mt = 1.0-t; return mt*mt*mt*sp + 3*mt*mt*t*cp1 + 3*mt*t*t*cp2 + t*t*t*ep; } function FMPointForTInBezierSegment(seg, t) { var x = FMComputeCubicBaseValue(t, seg.sp.x, seg.cp1.x, seg.cp2.x, seg.ep.x); var y = FMComputeCubicBaseValue(t, seg.sp.y, seg.cp1.y, seg.cp2.y, seg.ep.y); return NSMakePoint(x, y); } function FMMinDistanceForPointToCurve(point, curve, t0, t1, iteration) { iteration++; var a = FMPointForTInBezierSegment(curve, t0); var b = FMPointForTInBezierSegment(curve, t1); var distanceA = FMDistanceBetweenPoints(point, a); var distanceB = FMDistanceBetweenPoints(point, b); var m = (t1 - t0) / 2.0; if (iteration > MAX_ITERATIONS) { // OK, we've gone deep enough. globalBestT = distanceA < distanceB ? t0 : t1; [[NSColor blackColor] set]; FMFillCircleAtPoint(FMPointForTInBezierSegment(curve, globalBestT), 3) return Math.min(distanceA, distanceB); } if (distanceA < distanceB) { t1 -= m; } else { t0 += m; } FMFillCircleAtPoint(FMPointForTInBezierSegment(curve, t0), 2) FMFillCircleAtPoint(FMPointForTInBezierSegment(curve, t1), 2) return FMMinDistanceForPointToCurve(point, curve, t0, t1, iteration); }