So I've encountered a rather interesting, and likely highly math related problem to do with apple's implementation of the Bezier Curve.
So to cut to the chase, I've got a UIBezierCurve. I've plotted 3 points to generate an curve. A left point, the control point and the right point. Here is an example:
UIBezierPath *bezierCurve = [UIBezierPath bezierPath];
[bezierCurve moveToPoint:leftCorner];
[bezierCurve addQuadCurveToPoint:rightCorner controlPoint:controlPoint];
Where leftCorner, rightCorner and controlPoint are all CGPoints. Its pretty much an upside down parabola (with the values I am using usually, although this likely doesn't matter, its a parabola in some fashion that would pass the vertical line test). Like this: https://www.wolframalpha.com/input/?i=graph+of+y+%3D+-x%5E2
Now what I want to do is gather a list of points along this bezierCurve. Not just the 3 points I used to create it. For example, I would like to have, lets say a fine-grained list of probably hundreds of points along the curve that are all evenly spaced.
How I approached solving this: Hill-climb algorithm. My implementation of it was basically to start at the left of the curve (left corner) and walk along the curve until I got to the right corner. While walking 1 unit to the right each time I would try to hug the curve using:
- (BOOL)containsPoint:(CGPoint)point
This worked reasonably well, I got a list of a few hundred points along the curve. The problem however is they are certainly not equally spaced (equidistant is likely the term I am looking for here). Where the slope of the curve is relatively flat I get many points, and they are reasonably evenly spaced. When the slope is large however I get very few points compared to the length of the line in those areas. Sometimes only a point or two in very steep areas (when there should be many).
How I think I should solve this problem is to go with my hill climb algorithm (doing a pass horizontally, by walking along the x-axis hugging the curve) and add a second pass vertically (walking along the y-axis, hugging the curve). And then merge those 2 sets of points by sorting by x-value, and then within each x-value I sort by y-value.
However I am thinking there must be an easier, trivial way to do this. On Android all you have to do on the similar class to UIBezierCurve (android's "Path" class) is:
for (int i = 0; i < pathMeasure.getLength(); i++)
{
float[] point = new float[2];
float[] tangent = new float[2];
boolean success = pathMeasure.getPosTan(i, point, tangent);
if (success)
{
curvePoints.add(new Point((int)point[0], (int)point[1]));
}
}
In the end of that I basically have a list of points (curvePoints) that are all equidistant. PathMeasure is the class that works on android's Path (they are both built-in Android classes). I was hoping there was something similar to PathMeasure to easily get a list of equidistant points (of fine-grained granularity) on a UIBezierCurve and to avoid having to get heavy into the math of doing this all by hand. Is there something I'm missing?
Thanks!
