# Asking about Bezier Spline in Win32 using c++ • ### Question

• Hello Guys,

The question i am asking is , i have a set of 2d points but large number of them ( about 600 points) i extracted them from a text file to c++ vector<point> where point is a structure i defined... now the problem is i want the following:

1) get the value of x on the spline knowing  y
2) get the value of y knowing x
3) get the intersection between the spline & a line i have its equation & note that the line boundary in x direction lies between the spline , i.e i am sure that the line x_coordinates of starting point & end point lies between X_values boundaries of spline

so , any help? & if it isn't possible to do so with spline & i might with the function Polygon(); how can i do the same above??

I read Charlez Petzold's book / chapter 5 "Drawing Basics" & he mentioned the parametric function of Bezier line , so if someone could tell how to substitute in it & use it well , i might figure out the answer , i.e "How can i use these eqn with a pencil & paper to draw the spline with my hands on a set of paper "

The functions as mentioned in petzold's book :

x(t)=(1-t)^3*xo+3t(1-t)^2 x_1+3t^2 (1-t) * x_2+t^3 * x_3
y(t)=(1-t)^3*yo+3t(1-t)^2 y_1+3t^2 (1-t) * y_2+t^3 * y_3

where x_1 means: x sub 1

(xo,yo) ----> start point , (x3,y3)--->end point
(x1,y1) & (x2,y2) --> control points

Sunday, April 28, 2013 4:36 PM

• On 4/30/2013 10:56 PM, Brian Muth [MVP] wrote:

That doesn't make any sense. You cannot fit a spline through all 600 points. At best you can strive for a best fit.

Can too:

http://en.wikipedia.org/wiki/Spline_interpolation

This is what the OP is most likely talking about. The problem reduces easily to solving a linear system with a tridiagonal matrix, for which a fast algorithm is available:

http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm

Igor Tandetnik

Wednesday, May 1, 2013 4:40 AM

### All replies

• You need to explain your problem more clearly. What line are you talking about? What spline are you talking about? For example, a Bezier spline requires a start and end point, and two control points. How do you determine these four points? What does the line and spline have to do with the 600 points defined in the text file?

Perhaps you are trying to determine the best polynomial to fit the 600 points. If so, what degree polynomial do you want to use?

Sunday, April 28, 2013 9:53 PM
• Well , i should have mentioned that so i am sorry

The spline should link between the 600 points ( poly bezier of course ) , the line is any line but i have the line equation of course , say x=5 or y=3x+2 i will give the program the line eqn , but i searched more about the bezier yesterday after i wrote the question & the problem is i don't know the control points.

you suggested using polynomial , but for 600 points Interpolation is bad , Newton Backward , Newton Forward & others i have tried them but there is always a bad part of the resulting eqn

Thanks alot for your help, & i will try to find a different method & ask again if i need any help
Monday, April 29, 2013 3:46 PM
• thanks alot , but i will try something different than Bezier spline
Monday, April 29, 2013 3:48 PM
• best bet is to stock up on university math books

focus on calculus and analytic geometry, along with linear algebra

Windows MVP, XP, Vista, 7 and 8. More people have climbed Everest than having 3 MVP's on the wall.

Hardcore Games, Legendary is the only Way to Play

Monday, April 29, 2013 6:26 PM
• The spline should link between the 600 points ( poly bezier of course ) , the line is any line but i have the line equation of course , say x=5 or y=3x+2 i will give the program the line eqn , but i searched more about the bezier yesterday after i wrote the question & the problem is i don't know the control points.

That doesn't make any sense. You cannot fit a spline through all 600 points. At best you can strive for a best fit.

you suggested using polynomial , but for 600 points Interpolation is bad , Newton Backward , Newton Forward & others i have tried them but there is always a bad part of the resulting eqn

That is incorrect. This is what polynomial regression is all about. Note in particular that for a polynomial of degree one (that is, a straight line) then this is actually a "least squares" fit, which is a very common computational technique. But rather than fitting the best line, you can generalize the algorithm to create a best fit for any polynomial of a specified degree. I'm pretty sure this is really what you are after.

Google/Bing for "polynomial regression", and this will take you to a lot of reading material.

Wednesday, May 1, 2013 2:56 AM
• On 4/30/2013 10:56 PM, Brian Muth [MVP] wrote:

That doesn't make any sense. You cannot fit a spline through all 600 points. At best you can strive for a best fit.

Can too:

http://en.wikipedia.org/wiki/Spline_interpolation

This is what the OP is most likely talking about. The problem reduces easily to solving a linear system with a tridiagonal matrix, for which a fast algorithm is available:

http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm

Igor Tandetnik

Wednesday, May 1, 2013 4:40 AM