# it's a bezier problem.

• Sep 8th 2010, 01:20 PM
it's a bezier problem.
I don't know how to classify this problem, so I thought I'd stick it under Other.
I wrote a python program to help me solve this, but the process takes much too long and I can't get the accuracy down to where I'd like it. Close, but no cookie.

This problem is one of a few variations, so if a method is found to solve this, then I could use it to finish what I started 2 years ago. I'm not a math expert, but I would like to understand.

Problem:
Finding a curve that lines up to a series of data points.
Answer needs accuracy of 10 decimal places. 10 may be overkill but I do need precision

Data:
starting at point 'a' with tangent angle=90 degrees
ending at point 'b' with tangent angle=140 degrees
all points along curve are divided by the same denomonator minus the starting angle

For this example I'm using 61 points. 0-60. 140-90==50 and 50/60 == .8333
data points formula: .8333 * (point1of60) + 90 would make the first midpoint 90.8333

so we are looking at a chart of tangents
140
139.1667
...
92.5
91.6667
90.8333
90

Needed:
Location of two points on a 2d grid
Length of tangent lines at two points

Given:
Point 'a' lies along line( x>0, y=0 )
Point 'b' lies along line( x>0, y=60 )

Hint:
Point 'a' can start at (0,0), what is needed is rise and run of ending point 'b'
It sounds like a circle, but that idea doesn't work for other variations. But maybe I've applied it wrong too.

I know many other people have asked for bezier formulas and been told that such formulas don't exist. So I've tried to provide as much information as possible as simplified as possible regarding my own problem.
Any response would be appreciated.
• Sep 8th 2010, 01:37 PM
Ackbeet
I'm a bit confused. You say that the problem is to "find a curve that lines up to a series of data points." That's fine. There's loads of ways to do that. But then this statement, "all points along curve are divided by the same denomonator minus the starting angle" is nonsensical. I don't see how you can properly say that a point can be divided by the same denominator.

And then you say that you need the "location of 2 points on a second grid". What does that mean? Which two points? What is a grid?

You say you need the "length of tangent lines at two points". Again, that sentence does not parse mathematically.

I have a hunch that cubic splines might serve your purpose well, whatever that is.
• Sep 9th 2010, 10:13 PM
I do apologize for not being able to explain myself clearly. I read the cubic splines article, but it's not what I'm looking for. It was interesting though, thank you.

The set up is similar to a cubic spline, but the points are actually ON the line. As far as the 2 dimensional grid comment, I was just saying that I'm working with an x and y axis grid, sorry.
As for the points on the line, I have 61 total. If you were to take away point 'a' and point 'b' which are my key elements, you have 59 points on the line that are evenly spaced out and all have tangent angles of their own.

Part of what makes this complicated is... well, you'll notice that in the image the tangent line from point 'a' is significantly longer than the tangent line from point 'b'. (yes I know that line wouldn't work unless 140 degrees were flipped by 180.) If I were to check the first point based on percentage, the distance would not be the same as if I were to check the distance from point 'b' with the same percentage. I had to write a program to find the correct distance for each point (that was interesting).

I think I got all your questions... wait.
A couple of math formulas I found require (x,y) locations of both points and tangents, but I decided to write a program that logs a (x,y) location for the point and (angle,length) for the tangent. This was far easier to handle than doing all that extra processing.

The data I store looks something like this:
A = Point ( location(x,y), tangent(angle, length) )
B = Point ( location(x,y), tangent(angle, length) )

and of course the list of tangent angles which all have a change of .833 starting at 90 degrees
C = Array( 90.833, 91.66667, ..... 139.166 )
# length( C ) == 59

• Sep 10th 2010, 02:30 AM
Ackbeet
Quote:

The set up is similar to a cubic spline, but the points are actually ON the line.
I don't understand. With cubic splines, all of your data points ARE on the lines. You take a bunch of cubic polynomials and paste them together in such a way that all your data points are on at least one cubic, and the polynomials are continuous and differentiable everywhere.

Quote:

...you'll notice that in the image the tangent line from point 'a' is significantly longer than the tangent line from point 'b'.
I don't understand what determines the lengths of your tangent lines. Theoretically, tangent lines are infinitely long. By what criterion are you chopping them off into segments?

Quote:

(yes I know that line wouldn't work unless 140 degrees were flipped by 180.)
This sentence makes no sense.

Quote:

If I were to check the first point based on percentage,...
Percentage of what divided by what? What are you comparing to what?

Quote:

...the distance would not be the same as if I were to check the distance from point 'b' with the same percentage.
Distance from what to what?

Quote:

This was far easier to handle than doing all that extra processing.
What would be all "that extra processing"? An alternative algorithm?

Quote:

...and of course the list of tangent angles...
Of course? I have no idea why you're doing what you're doing.

A general comment: I accept your apology for not being able to communicate clearly, but don't you think you should work on improving your abilities? The way you write is incredibly confusing. In answering one of my questions, it almost seems like you raise two more questions just in your answers! I haven't the faintest idea what the original problem is (it might be good to state that!).

I work as an engineer, and I work in research and development. You can take it from me that the most important skills in the workplace are the communication skills. All the technical problem-solving abilities, as valuable as they can be, are no good to anyone if you can't talk with people in a way that they can understand. This is why it is so incredibly important for technical people to read good books and take humanities courses. As an example, the Challenger blew up partially as the result of bad communication on the part of the engineers. They knew there was a problem with the o-rings, and they wanted to delay the launch. However, they didn't realize they were up against political pressure not to delay yet again. In addition, the PowerPoint slide that contained the critical data was far too dense to convey the intended important piece of data. As a result, they didn't convince their superiors, and the launch went ahead. You know what happened.

So you see, good communication is essential. It's not enough to have the truth - you must be able to convince others of it.
• Sep 10th 2010, 04:37 PM
Cubic splines WILL NOT WORK for what I want. I tried that technique and I do use a cubic spline to help with collision detection, but nothing else.

Yes, 't' is on the line. The variable 't' on this cubic spline is based on a percentage from point 'A' to 'B'.
I don't want percentage from point 'A' to 'B', I want to lay a ruler along the curve and base the distance off of that.
If the distance along the curve between point 'A' and 'B' were 10 feet, and I had 9 points along this curve, the distance between points would be 1 foot.

I could draw a line from Point 'A' to 'B' and it would be straight, but I want to curve that line based on points 'a' and 'b'.
I have a tangent line 'A' to 'a'
I have a tangent line 'B' to 'b'
and as a result, the line curves from point 'A' to 'B' based on 'a' and 'b'
thus 'a' and 'b' are tangent points

My problem:
I have a series of points on this line whose (x,y) coordinates are UNKNOWN, but the tangents at these points IS KNOWN.

The program that I wrote makes adjustments to the coordinates of points 'A', 'B', 'a', 'b'.
The tangent angles of the new curve at specified points is checked along the given series of tangent angles for alignment.
If the new curve does not line up, make adjustments again.

I don't need a lecture about my communication skills. I'm aware of their importance. If the problem is not understood, I'll explain differently or find someone else.
Maybe it would be better in person, but I would lose the volume of people I could find on the internet.
In any case, I'm glad to have caught someone's interest in a unique puzzle.
• Sep 10th 2010, 05:52 PM
Ackbeet
Now we're getting somewhere. I think I understand a lot better what you're after now. Let me just restate the problem so that we're on the same page, and we both know we're on the same page.

You have four points A, B, a, and b. You draw the straight lines from A to a with slope $m_{a}$ , and from B to b with slope $m_{b}$. You are then given the number of points $x_{j}$ with corresponding slopes $m_{j}$ to place on a curve from A to B such that: the change in the angle $\tan^{-1}(m_{j})$ is the same from one point to the next point AND the arc length along the curve from one point to the next point is the same. I'm just trying to list all the givens in one place.

Is this correct? I'm a little unclear, still, as to the role your point t makes. Is that another given point through which the curve must go? Or are you merely mentioning t as an example of dividing the arc length into a certain number of pieces (in this case, 2)? I understand the percentage along the curve idea, but do you know in advance the distance from t to the straight line AB? If the distance from t to the straight line AB is equal to half of the length of AB, then it's pretty clear to me, I think, that the circle solves the problem. But if it's not, then you'd have to construct a different curve.

I can't help but think of two possible contexts for this problem: fonts and slur markings in music. Is this one of those?
• Sep 12th 2010, 10:16 PM
I know just enough math language to say, WOOHOO! :)
The only role that 't' played was finding x(subunit j) and y(subunit j)

slur markings in music? ya lost me on that one. Fonts I could see. Programming an autonomous car comes to mind (roads that curve). However, what I'm working on deals with glass and lenses.
I'd like to make some special lenses for cameras, not just the typical ones dealing with zoom, but things that would distort the original image.
This project is just one of many in mind, I don't plan to go into the photography field, I just like to engineer new things. Plus, considering that
three dimensional printers are starting to use more and more materials, I could design the lens I wanted virtually and "print" one out. Maybe I could make a lens that focused light into an image, that would be cool.

For the example presented, yes a circle could complete this puzzle, but was not capable of working for another variation. One of the variations is that the m(subunit j) slowly changes until it reached the center, the curve looks like an arrow head rather than a smooth arc. I can't use a circle for this, but rather a circle that has been deformed. Also, when I'm trying to combine some of these curves like line (A,B) which is connected to line (B,C) where B has the same (x,y), but has two independent tangent lines b1 and b2 when traveling to their respective A or C points.

I seem to have lost one of my variations, I'm gonna try to build it again. Shouldn't take long, all my data is in a spreadsheet with programmed variables.
I wish I only needed a cubic spline or just a circle, but if life were that easy puzzles wouldn't be fun.
• Sep 13th 2010, 03:57 AM
Ackbeet
I can see now why cubic splines won't work: there aren't enough arbitrary parameters (degrees of freedom) per curve segment to satisfy all the conditions. You're basically enforcing the function values at the endpoint of each subinterval (that's two conditions), plus the derivative at the endpoint of each subinterval (another two conditions), plus the arc length of the curve along the subinterval.

Possible solution: quartic splines. An arbitrary quartic polynomial has five constants to be chosen, which matches the number of conditions you have. Let's take a very simplified example, and see where a Gedankenexperiment leads us:

Fit a quartic polynomial between the two points $(0,0)$ and $(2,1)$ such that $y'(0) = 1$, and $y'(2) = 1/2$. Also, ensure that the arc length along the curve from one endpoint to the other is equal to $\sqrt{7}$. (I picked this value because it's greater than the obviously impossible straight-line distance of $\sqrt{5}.$)

So our candidate quartic is $y(x)=ax^{4}+bx^{3}+cx^{2}+dx+e.$ Now $y(0)=0$ implies $e=0,$ and hence
$y(x)=ax^{4}+bx^{3}+cx^{2}+dx.$ Applying $y(2)=1$ implies

$1=16a+8b+4c+2d.$

Now $y'(x)=4ax^{3}+3bx^{2}+2cx+d.$ Applying the boundary condition at the origin, $y'(0)=1$ implies $d=1.$ Applying the boundary condition for the derivative at $x=2$ implies $y'(2)=1/2=32a+12b+4c+1,$ where we have plugged in $d=1.$ Also, our previous condition with $d=1$ turns into $1=16a+8b+4c+2.$

Finally, we impose the arc length condition. This is an integral condition, and looks like this:

$\displaystyle{\sqrt{7}=\int_{0}^{2}\sqrt{1+(y'(x)) ^{2}}\,dx}.$

This condition is much harder to apply, because an elementary antiderivative of the integrand is most likely impossible to find. So let's leave this condition for now, and work a bit more on the other two conditions:

$16a+8b+4c=-1$
$32a+12b+4c=-1/2.$

That's two equations in three unknowns. We should be able to eliminate two parameters through normal row reduction techniques:

$8a+3b+c=-1/8$
$4a+2b+c=-1/4.$

Let's do the ERO $-2R_{2}+R_{1}\to R_{2}.$ This yields

$8a+3b+c=-1/8$
$0-b-c=-1/8+1/2=3/8.$ Hence,

$8a+3b+c=-1/8$
$0+b+c=-3/8.$

Solving the second equation for $b$ yields $b=-c-3/8.$ We plug this back into the first equation to solve for $a$:

$8a+3(-c-3/8)+c=-1/8,$ or

$8a-3c-9/8+c=-1/8,$ and hence

$8a=-1/8+2c+9/8=2c+1.$ Therefore,

$a=1/8+c/4.$ It follows, then, that

$y'(x)=4(1/8+c/4)x^{3}+3(-c-3/8)x^{2}+2cx+1.$

We now have a one-parameter family of curves that we must get to satisfy the arc-length condition. My suggestion: do a shooting algorithm. That is, pick values of $c$, compute the arc length integral numerically, and see how close to the desired value you get. Then adjust the $c$ value accordingly. Theoretically, you should be able to get the value of $c$ such that the arc length is arbitrarily close to the desired value. Practically, you're probably going to run into round-off error on your computer.

So, I think we can see that this algorithm will do what we want for this simple case. But your problem is more complex: you don't actually know the exact positions of your interior points - the problem is to find them. I'm going to have to do some more thinking in order to see how we can generalize this algorithm to solve your problem.
• Sep 15th 2010, 03:22 AM
Ackbeet
I'm not so sure you can guarantee that your problem has a solution in every case. For example, take the case that the perpendicular distance from $t$ to $AB$ is far greater than half the straight-line distance from $A$ to $B$. How can you possibly impose the constant-changing-of-tangent-angle condition without having a highly irregular series of curves, perhaps even with points of inflection in-between the points? It isn't going to be a nice even fit, as I see it. Are there any conditions about inflection points? Does the area enclosed by the constructed curve and the line AB have to be, say, convex? Because, if so, I'm thinking that the problem does not have a general solution.
• Sep 16th 2010, 10:40 PM