finding a point on a path

Question

I have an app that draws a bezier curve in a UIView and I need to find the X intersect when I set a value for Y. First, as I understand, there isn’t a way to find a point directly of a UIBezierPath but you can locate a point of a CGPath.

First, if I “stroke” my UIBezierPath (as I have done in my code) is this actually creating a CGPath or do I need to take further steps to actually convert this to a CGPath?

Second, I want to find the curves intersect at X by providing the value for Y.

My intention is to automatically calculate X for the given value of Y as the user moves the slider (which moves the curve left or right respectively).

My starting display.

What happens when I currently adjust slider.

What I want my display too look like.

GraphView.h

#import <UIKit/UIKit.h>

@interface GraphView : UIView
{
    float adjust;
    int x;
    int y;
}

- (IBAction)sliderChanged:(id)sender;
- (IBAction)yChanged:(id)sender;

@property (weak, nonatomic) IBOutlet UISlider *sliderValue;
@property (weak, nonatomic) IBOutlet UITextField *xValue;
@property (weak, nonatomic) IBOutlet UITextField *yValue;

@end

GraphView.m

#import "GraphView.h"

@interface GraphView ()


@end

@implementation GraphView

@synthesize sliderValue, xValue, yValue;

- (id)initWithCoder:(NSCoder *)graphView
{
    self = [super initWithCoder:graphView];
    if (self) {
        adjust = 194;
        y = 100;
    }
    return self;
}

- (IBAction)sliderChanged:(id)sender
{
    adjust = sliderValue.value;
    // Calcualtion of the X Value and setting of xValue.text textField goes here
    [self setNeedsDisplay];
}

- (IBAction)yChanged:(id)sender
{
    y = yValue.text.intValue;
    [self setNeedsDisplay];
    [self resignFirstResponder];
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    UITouch * touch = [touches anyObject];
    if(touch.phase == UITouchPhaseBegan) {
        y = yValue.text.intValue;
        [self setNeedsDisplay];
        [yValue resignFirstResponder];
    }
}

- (void)drawRect:(CGRect)rect
{
    UIBezierPath *lines = [[UIBezierPath alloc] init];
    [lines moveToPoint:CGPointMake(0, y)];
    [lines addLineToPoint:CGPointMake(200, y)];
    [lines addLineToPoint:CGPointMake(200, 280)];
    [lines setLineWidth:1];
    [[UIColor redColor] setStroke];
    float dashPattern[] = {2, 2};
    [lines setLineDash:dashPattern count:2 phase:0.0];
    [lines stroke];

    UIBezierPath *curve = [[UIBezierPath alloc] init];
    [curve moveToPoint:CGPointMake(0, 280)];
    [curve addCurveToPoint:CGPointMake(280, 0) controlPoint1:CGPointMake(adjust, 280) controlPoint2:CGPointMake(adjust, 0)];
    [curve setLineWidth:2];
    [[UIColor blueColor] setStroke];
    [curve stroke];

}

@end

Parasol

After thinking about this a little further... I think if I knew how much the control points adjusted the curve of the bezier path (the calculation used or the percentage) I could calculate the intersect instead of having to have my app return the intersect. I'm certain this is a standard calculation/percentage, does anyone know what this calculation is or where to find it? – Parasol

So the solution to calculating the intersect should be De Casteljau's algorithm. I don't have time to implement this right now but when I do I will post my solution. Once I have, I should be able to create my own method to calculate the intersect by providing the value of Y though. – Parasol

There was a post that has since been removed that sugested using Pythagorean's Theorem... My response to this is in the next comment. – Parasol

Yes, and this would work if I already knew the coordinates of two of the three points; however, in this I only know the value of one, and that would be Y (0, 100) which I set explicitly. I only know half of the other two coordinates, X (280, ?) which I am trying to calculate for and the intersect of the bezier path (?, 100). De Casteljau's algorithm should provide me with the calculation to get the intersect since I know the coordinates of the start point, end point, and two control points. FYI, my UIView (graph area) is 280x280 pixels and is how I know half of my value for Y. – Parasol

Answer 1

A cubic Bézier curve is defined by 4 points

P0 = (x0, y0) = start point,
P1 = (x1, y1) = first control point,
P2 = (x2, y2) = second control point,
P3 = (x3, y3) = end point,

and consists of all points

x(t) = (1-t)^3 * x0 + 3*t*(1-t)^2 * x1 + 3*t^2*(1-t) * x2 + t^3 * x3
y(t) = (1-t)^3 * y0 + 3*t*(1-t)^2 * y1 + 3*t^2*(1-t) * y2 + t^3 * y3

where t runs from 0 to 1.

Therefore, to calculate X for a given value of Y, you first have to calculate a parameter value T such that 0 <= T <= 1 and

 Y = (1-T)^3 * y0 + 3*T*(1-T)^2 * y1 + 3*T^2*(1-T) * y2 + T^3 * y3      (1)

and then compute the X coordinate with

 X = (1-T)^3 * x0 + 3*T*(1-T)^2 * x1 + 3*T^2*(1-T) * x2 + T^3 * x3      (2)

So you have to solve the cubic equation (1) for T and substitute the value into (2).

Cubic equations can be solved explicitly (see e.g. http://en.wikipedia.org/wiki/Cubic_function) or iteratively (for example using the http://en.wikipedia.org/wiki/Bisection_method).

In general, a cubic equation can have up to three different solutions. In your concrete case we have

P0 = (0, 280), P1 = (adjust, 280), P3 = (adjust, 0), P4 = (280, 0)

so that the equation (1) becomes

Y = (1-T)^3 * 280 + 3*T*(1-T)^2 * 280

which simplifies to

Y/280 = 1 - 3*T^2 + 2*T^3    (3)

The right hand side of (3) is a strictly decreasing function of T in the interval [0, 1], so it is not difficult to see that (3) has exactly one solution if 0 <= Y <= 280. Substituting this solution into (2) gives the desired X value.

Miranda

Very impressive! Great answer! Can't wait to implement this! – Parasol

I've used the parametric calculation but I'm running into a little issue. If i set my Y value to 75 on a Y axis that is 100 pixels and than set my T value to 75% it returns the coordinates at 75% of the line and not the value lying at the Y value of 75. Any suggestion? – Parasol

@ShannonBuckland: You have to solve the equation (3) for T. So you have to find a value T such that 1 + 3*T^2 + T^3 = 75/100 = 0.75. The solution (in this special case) is approximately T = 0.3045. – Miranda

After stepping away for a bit and looking from a different perspective I think my solution is to calculate T for Y to then calculate X for the value of T. – Parasol

Yea, I see that now. I figured you had provided the answer... it just didn't register! Thanks again! – Parasol

@ShannonBuckland: You are welcome. - So your new question #16780424 is obsolete? – Miranda

in (3) is that 280 the value from P0 or P1? – Parasol

Yes! I can delete it if that would be appropriate. Why is my response deleting your name using @ – Parasol

@ShannonBuckland: From both. The general formula is (1). In your question you had y0 = y1 = 280, y2 = y3 = 0. If you substitute that into (1) then you get (3). – Miranda

@ShannonBuckland: I think that you can delete your new question if it does not contain a new problem. – Miranda

I feel like an idiot! I can't figure out how to arrange the equation to solve for T. Should have payed more attention in algebra class I guess! – Parasol

@ShannonBuckland: Solving a cubic equation is not trivial! You probably should use some iterative method, for example en.wikipedia.org/wiki/Bisection_method or en.wikipedia.org/wiki/False_position_method. – Miranda

@martin_r, I've been working on this since my last comment... I've gone back and read two algebra books (algebra 1 and algebra 2) I understand how you came to Y/280 = in solution (3) but I'm not clear how you factored the out the (1 - t) to get 1 - 3*T^2 + 2*T^3. I can get to Y/280 = (1-T)^3 + 3*T*(1-T)^2 but then I'm missing how to factor from that point. – Parasol

@ShannonBuckland: Expand (1-T)^3 = 1 - 3*T + 3*T^2 - T^3 and (1-T)^2 = 1 - 2*T + T^2, then combine the terms... – Miranda

@MartinR, This is very helpful for us, but one thing I would like to know if i use this formula then will i get all possible x and y coordinate of Path value. Appreciate your feedback. – Belomancy

@user1955086: This question was about computing the y-value from a given x-value. If you want to compute all (x, y) coordinates of the Bezier curve then you can use the above formula x(t) = ..., y(t) = ... where t runs from 0 to 1. – Miranda

@MartinR we are using UIBezierPath and stuck at one place. let me share the link :(#58989675) We really need your help to resolve this issue. If you can review the link and just guide us on same would be really helpful for us to proceed further in our development. – Belomancy

Answer 2

It took me a while but the code below is how I solved finding a point on a bezier curve. The math only finds one of the potential 3 values so I suspect if there is more than one it will fail, but in my circumstance my bezier should only ever have one solution since my curve should never cross the same X or Y plane more than once. I wanted to share what I have and I welcome any questions, comments, or suggestions.

#import "Calculation.h"

@implementation Calculation

@synthesize a, b, c, d, xy;

- (float) calc
{

    float squareRootCalc =
    sqrt(
    6*pow(xy,2)*b*d
    +4*a*pow(c,3)
    -3*pow(b,2)*pow(c,2)
    +9*pow(xy,2)*pow(c,2)
    -6*a*c*b*d
    +6*a*xy*c*b
    -18*pow(xy,2)*b*c
    +6*a*pow(xy,2)*c
    -12*a*xy*pow(c,2)
    -2*pow(a,2)*xy*d
    +pow(a,2)*pow(d,2)
    +4*pow(b,3)*d
    +pow(xy,2)*pow(d,2)
    -4*pow(b,3)*xy
    -4*pow(c,3)*xy
    +pow(a,2)*pow(xy,2)
    +6*c*b*d*xy
    +6*a*c*d*xy
    +6*a*b*d*xy
    -12*pow(b,2)*d*xy
    +6*xy*c*pow(b,2)
    +6*xy*b*pow(c,2)
    -2*a*pow(xy,2)*d
    -2*a*xy*pow(d,2)
    -6*c*d*pow(xy,2)
    +9*pow(xy,2)*pow(b,2)
    -6*a*pow(xy,2)*b)
    ;

    float aCalc = 24*c*d*xy + 24*a*pow(c,2) - 36*xy*pow(c,2) + 4 * squareRootCalc * a;

    float bCalc = -12 * squareRootCalc * b;

    float cCalc = 12 * squareRootCalc * c;

    float dCalc = -4 * squareRootCalc * d;


    float xyCalc =
    24*xy*a*b
    -24*xy*b*d
    -12*b*a*d
    -12*c*a*d
    -12*c*b*d
    +8*xy*a*d
    +8*pow(b,3)
    +8*pow(c,3)
    +4*pow(a,2)*d
    +24*pow(b,2)*d
    -4*xy*pow(a,2)
    -4*xy*pow(d,2)
    +4*a*pow(d,2)
    -12*c*pow(b,2)
    -12*b*pow(c,2)
    -12*a*b*c
    -24*xy*a*c
    +72*xy*c*b
    -36*xy*pow(b,2)
    ;

    float cubeRootCalc = cbrt(aCalc + bCalc + cCalc + dCalc + xyCalc);

    float denomCalc = (a-3*b+3*c-d);

    float secOneCalc = 0.5 * cubeRootCalc / denomCalc;

    float secTwoCalc = -2 * ((a*c - a*d - pow(b,2) + c*b + b*d - pow(c,2)) / (denomCalc * cubeRootCalc));

    float secThreeCalc = (a - 2*b + c) / denomCalc;

    return secOneCalc + secTwoCalc + secThreeCalc;


}

- (Calculation *) initWithA:(float)p0 andB:(float)p1 andC:(float)p2 andD:(float)p3 andXy:(float)xyValue
{
    self = [super init];

    if (self) {
        [self setA:p0];
        [self setB:p1];
        [self setC:p2];
        [self setD:p3];
        [self setXy:xyValue];
    }
    return self;
}

- (void) setA:(float)p0 andB:(float)p1 andC:(float)p2 andD:(float)p3 andXy:(float)xyValue
{
    [self setA:p0];
    [self setB:p1];
    [self setC:p2];
    [self setD:p3];
    [self setXy:xyValue];
}

@end

Parasol