UIBezierPath Percent of Length at Point

Question

I'm building an app that features some graphical manipulation. I'm storing shapes as UIBezierPaths, and I want to allow users to touch points along the line to create saved locations. Using the wonderful answer to this question, and more specifically, this project, I'm able to place a point on a line knowing the percentage of its length the point rests on. This is half of my problem.

I want a way to take a point on a path, and derive the percent of its length.

My math-fu is extremely weak. I've studied bezier curves but I simply don't have the math to understand it.

I would humbly submit that "go back and learn geometry and trigonometry" is a correct answer, but sadly one I don't have time for at present. What I need is a way to fill in this method:

- (CGFloat)percentOfLengthAtPoint:(CGPoint)point onPath:(UIBezierPath*)path

Any help appreciated!

Who says there's only one percentage for a point on a path? The path could intercept itself and there could be many. — Rhythmic Fistman, Nov 09 '15 at 01:32
I guess I do. I'll be composing the paths; they won't be arbitrary. I'll be dealing with straightforward lines, arcs and curves. — Aaron Vegh, Nov 09 '15 at 05:26

score 1 · Accepted Answer · answered Nov 10 '15 at 01:44

I have working code that solves my problem. I'm not particularly proud of it; the overall technique is essentially a brute-force attack on a UIBezierPath, which is kind of funny if you think about it. (Please don't think about it).

As I mentioned, I have access to a method that allows me to get a point from a given percentage of a line. I have taken advantage of that power to find the closest percentage to the given point by running through 1000 percentage values. To wit:

Start with a CGPoint that represents where on the line the user touched.

let pointA = // the incoming CGPoint

Run through the 0-1 range in the thousands. This is the set of percentages we're going to brute-force and see if we have a match. For each, we run pointAtPercentOfLength, from the linked project above.

var pointArray:[[String:Any]] = []
for (var i:Int = 0; i <= 1000; i++) {
    let value = CGFloat(round((CGFloat(i) / CGFloat(1000)) * 1000) / 1000)
    let testPoint = path.pointAtPercentOfLength(value)

    let pointB = CGPoint(x: floor(testPoint.x), y: floor(testPoint.y))
    pointArray.append(["point" : pointB, "percent" : value])
}

That was the hard part. Now we take the returning values and calculate the distance between each point and the touched point. Closest one is our winner.

// sort the damned array by distance so we find the closest
var distanceArray:[[String:Any]] = []
for point in pointArray {
    distanceArray.append([
        "distance" : self.distanceFrom(point["point"] as! CGPoint, point2: pointA),
        "point" : point["point"],
        "percent" : point["percent"] as! CGFloat
        ])
}

Here's the sorting function if you're interested:

func distanceFrom(point1:CGPoint, point2:CGPoint) -> CGFloat {
    let xDist = (point2.x - point1.x);
    let yDist = (point2.y - point1.y);
    return sqrt((xDist * xDist) + (yDist * yDist));
}

Finally, I sort the array by the distance of the values, and pick out the winner as our closest percent.

let ordered = distanceArray.sort { return CGFloat($0["distance"] as! CGFloat) < CGFloat($1["distance"] as! CGFloat) }

ordered is a little dictionary that includes percent, the correct value for a percentage of a line's length.

This is not pretty code, I know. I know. But it gets the job done and doesn't appear to be computationally expensive.

As a postscript, I should point to what appears to be a proper resource for doing this. During my research I read this beautiful article by David Rönnqvist, which included an equation for calculating the percentage distance along a path:

start⋅(1-t)3 + 3⋅c1⋅t(1-t)2 + 3⋅c2⋅t2(1-t) + end⋅t3

I was just about to try implementing that before my final solution occurred to me. Math, man. I can't even brain it. But if you're more ambitious than I, and wish to override my 30 lines of code with a five-line alternative, everyone would appreciate it!

As you wish. I wasn't able to do that at the time. – Aaron Vegh Nov 13 '15 at 01:33 — Aaron Vegh, Nov 13 '15 at 01:33

score 1 · Answer 2 · answered Nov 10 '15 at 04:47

I think your approach is sound, but you could do this far more efficiently.

Instead of creating an two arrays of dicts (with a thousand elements each) and then sorting the array - just use a while loop to move from 0.0 to 1.0, calculate the distance to the touch point and keep track of the minimum distance.

For example:

    var t:CGFloat = 0.0
    let step:CGFloat = 0.001
    var minDistance:CGFloat = -1.0
    var minPoint:CGPoint = CGPointZero
    var minT:CGFloat = -1;
    while (t<1.0) {

        let point = pointAtPercentOfLength(t)
        let distance:CGFloat = self.distanceFrom(point, point2: pointA)

        if (minDistance == -1.0 || distance < minDistance) {
            minDistance = distance
            minPoint = point
            minT = t
        }
        t += step
    }
    print("minDistance: \(minDistance) minPoint: \(minPoint.x) \(minPoint.y) t\(minT)\n")

You're absolutely right. I guess when you're in a brute force frame of mind, everything looks like a nail. Or something. — Aaron Vegh, Nov 10 '15 at 14:19
Ha, yeah, dictionaries are a last resort for me - there's usually a better way to do it. btw, Another easy optimization is to exit the while loop early if distance is less than some threshold. — Jason Moore, Nov 10 '15 at 20:30

UIBezierPath Percent of Length at Point

2 Answers2