Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm developing an iPhone app that allows users to cut out part of an image from its background. In order to do this, they'll connect a bunch of bezier curves together to form the clipping path. Rather than have them move the control points of the curves in order to change the curve, I'd like them to be able to move a point on the curve itself. At this point, I'm not set on using quadratic rather than cubic beziers, or vice versa. The rest of this post will discuss the issue from the point of view of quadratic curves, but I would love an answer that provides solutions to both.

It seems to me that there are two possible methods for accomplishing this:

  1. By determining the relationship between the point on the curve and the true control point. If this can be done, then the new location of the control point can be calculated based on the new location of the point on the curve.

  2. By using an equation that can estimate a bezier curve based on two end points and a third point on the curve (if cubic, then a third and fourth point on the curve).

Are either of these possible? I've been googling this for a while and have come across a couple potential solutions using method #2, but I don't fully understand either:

Solution 1 (click here): I think I understand the code in this example well enough, but I don't know how to calculate t.

Solution 2 (click here): This code is written in C#. I tried converting it to Objective-C (the language used for iPhone apps), but ultimately got stuck on the "solvexy()" function because I don't see how i or j are used after calculating their values.

In regards to method #1, it seems to me that there should be some mathematical relationship between the control point, and the point on the curve through which a tangent to the curve at that point would be perpendicular to a line drawn from the control point to that point.

Here are a couple illustrations: quadratic, cubic.

The idea is that this point which lies on the curve, through which the perpendicular tangent is drawn, is the point that users would be dragging in order to modify the curve.

share|improve this question
    
Solution 1: $t$ looks like the parameter along the curve, with $t\in[0,1]$, I'd say. Solution 2: i and j are output parameters; they get assigned to the corresponding argument in the caller; in this case first x1, x2, then y1, y2. You might want to take a look at the sidebar to the right; there are lots of answers to similar questions there; e.g. math.stackexchange.com/questions/5166/…, math.stackexchange.com/questions/42395/…. –  joriki Jul 26 '11 at 11:22
    
Thanks for the clarification in the C# code. I'll give it another try with that info. And I did read those two questions you linked to. The first one's answer is that a Bezier should not be used, but rather a parametric spline. So I spent a while looking into how to create a parametric spline (as well as what one is in the first place) in objective-c, but couldn't come up with anything. In the second post you link to it seems that the OP is asking about how to create a Bezier simply from two end points, but I will know at least one other point that the curve must pass through. –  maxedison Jul 26 '11 at 12:12
    
Approach 2 is underspecified. Given $P(0)$, $P(1)$, $P(t)$, and $t\in(0,1)$ you have a unique quadratic Bézier curve and can find the non-interpolated control point using the Bernstein polynomials, but you're not specifying $t$. I suspect you could specify two interpolated points and get a unique quadratic Bézier curve, but I haven't worked through the details. –  Peter Taylor Jul 26 '11 at 12:23
    
Someone should have inserted the linked illustrations into the question before FreeImageHosting deleted them... (Using the StackExchange "insert image" button uploads the images to Imgur, which SE has a partnership with, so the images will stay up as long as SE does.) –  Rahul May 25 at 18:07
add comment

3 Answers 3

If your only problem is to find the point at which the tangent line is perpendicular to the direction to the control point and to find the control point that has this property for a given waypoint on the curve, you can try the following. Let's do quadratic curves. If A is the beginning, B is the end (both fixed), C is the control and X is the waypoint, we have the system

$X=(1-t)^2A+2t(1-t)C+t^2B$ (curve equation)

$\langle X-C,-(1-t)A+(1-2t)C+tB\rangle=0$ (orthogonality relation).

Suppose we know $C$. Then plugging $X$ from the first equation into the second, we get a cubic equation for $t$, which we can solve quickly by either bisection, or Newton, or a combination of both.

The inverse problem is similar. Express $C$ from the first equation and plug the result into the second one. Now you'll get a fifth degree equation to solve but if bisection is quick enough for you (you do not need really high precision for point dragging), you can do everything without too heavy thinking (we need to make sure that the singularities at the endpoints are dealt with in some reasonable way, so if the user drags the point close to one of the endpoints you don't have an aberrant behavior but I do not want to think of this singularity problem before you tell me if this approach works for you in general).

The cubic curves have two controls, so the problem is ill-posed for them as stated.

share|improve this answer
add comment

I think the simplest thing that would work in your application is to show the user 4 special points on the parametric cubic curve, and allow the user to manipulate those 4 special points. (Allowing the user to pick any point on the curve, and move it, makes things more complicated).

I think this is the same as what Stephen H. Noskowicz calls "Cubic Four Point" representation, aka the quadratic Lagrange with t1 = 1/3 and t2 = 2/3.

While your user is moving those 4 special points U0, U1, U2, U3 around, periodically you find a cubic Bezier curve that goes through those 4 points using John Burkardt's approach:

P0 = U0
P1 = (1/6)*( -5*U0 + 18*U1 - 9*U2 + 2*U3 )
P2 = (1/6)*(  2*U0 -  9*U1 +18*U2 - 5*U3 )
P3 = U3.

That gives you the Bezier curve representation of the same cubic curve -- a series of 4 control points. You then feed those 4 control points (the endpoints P0 and P3, and the intemediate control points P1 and P2) into any Bezier curve plotter.

The resulting curve (usually) doesn't touch P1 or P2, but it will start at X0, go exactly through X1 and X2, and end at X3.

(This uses the special points at t=0, 1/3, 2/3, and 1. It's possible to, instead, use the special points at t=1, 1/4, 3/4, and 1, as shown at How do I find a Bezier curve that goes through a series of points? . Or, I suppose, any 4 distinct t values. But I suspect the 0, 1/3, 2/3, 1 values are used most often, and I don't see any advantage to using any other fixed values).

share|improve this answer
add comment

This site: http://pomax.github.io/bezierinfo/

describes a way of using de Casteljau's algorithm 'in reverse' to do something like this, they call it 'curve moulding'. It has javascript source code as well.

(de Casteljau uses points on lines (linear interpolation) to draw beziers, not higher degree equations)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.