Determine if 3 points form a right angle

[abeall]

Greetings, all!

This is really basic, but I'm a humble programmer, not a mathematician, and while working on a small script in which I need to determine a right angle, I realized that I don't really know what the best approach is.

Here's the abstract: I have 3 points, A,B,C, I want to determine if B forms a right angle between A and C. My only thought is to find the angle between A,B and B,C, arbitrarily subtract one from the other, and if the absolute value is 90 then we have a right angle.

Here's the full context: What I'm actually trying to do is, given a bezier curve defined as p1,cp1,cp2,p2 and another random point, pt, I want to find what point along the bezier curve is exactly perpendicular to the the target point(pt). Scary, huh? I have a function which I can use to walk the bezier curve at really small increments, finding points along the way, so eventually I'll find one point on the curve whose angle from previous point on the curve and angle to target point should form a right angle, or at least very close. The closest will be close enough, I hope.

Any help on the right angle is really what I need. Any better ideas on finding a perpendicular point along a bezier curve to a target point would be welcome, too.

Thanks!
- aaron

 

[mgb_phys]

I have found this site to be the best for geometry algorithms
http://local.wasp.uwa.edu.au/~pbourke/geometry/

 

[JonF]

Why not just convert them to vectors and take the cross product?

 

[HallsofIvy]

I would think the dot product would be better. You can determine whether or not two vectors are perpendicular with the cross product but that requires calculating the lengths of the vectors also. Two vectors are perpendicular if and only if the dot product is 0. Of course, since you don't know which two lines are supposed to be perpendicular, you would have check all three possible pairs of lines.

A more fundamental check would be to calculate squares of the three distances between pairs of points and see if they satisfy the Pythagorean theorem.

 

[JonF]

I would think the dot product would be better. You can determine whether or not two vectors are perpendicular with the cross product but that requires calculating the lengths of the vectors also. Two vectors are perpendicular if and only if the dot product is 0. Of course, since you don't know which two lines are supposed to be perpendicular, you would have check all three possible pairs of lines.

A more fundamental check would be to calculate squares of the three distances between pairs of points and see if they satisfy the Pythagorean theorem.

I suggested the vector approach so if they weren’t right and he wanted them to be he could find a new point that would satisfy easily. Yup go with the dot product – don’t know what I was thinking!

 

[abeall]

Thanks all.

These are in 2D. So, how would I determine the dot product of two 2D vectors, AB and BC?

I just looked up dot product and I'm having a hard time how I would convert it to programming language, I get quite lost in all the notation...

 

[abeall]

Well, I don't know about the dot product or what it might have to offer, but it turns out this works:

90 - ( Math.abs(angle1) - Math.abs(angle2) )

The two angles I think are perpendicular if the sum of the above equation is 0.

I'm also looking for speed, though, and to obtain the two angles above requires the following function to be run twice:
function angle(p1,p2){
return -Math.atan2((p1.x-p2.x), (p1.y-p2.y))/(Math.PI/180);
}

This is a notable resource drain. If there was a more efficient way that avoided this, it would be better.

 

[Rainbow Child]

...Here's the full context: What I'm actually trying to do is, given a bezier curve defined as p1,cp1,cp2,p2 and another random point, ...

What do you mean by that? How is the curve defined exactly?

... Any better ideas on finding a perpendicular point along a bezier curve to a target point would be welcome, too. ...

As long I can understand you have two points. One on the curve and the target point. Where is the 3rd point?

Do you mean that the line joining these two points is perpendicular to the tangent of the curve at the first point? (or I am lossing something? )

 

[abeall]

Do you mean that the line joining these two points is perpendicular to the tangent of the curve at the first point?

Ah, yes, I'm pretty sure that's what I mean. The 3rd point to define the angle doesn't really exist...

At any rate, after further testing, the solution I posted above does not work. It breaks down in some situations.

An added challenge is that, since I'm walking the bezier curve and comparing the current tangent to the target point compared the previous, I also need to know when I've overstepped the curve. This way I can back up the previous point, and continue to walk at a smaller increment to refine the accuracy a few iterations.

 

[mda]

just so we're all on the same page, perhaps you clarify your bezier notation a bit.
are cp1 & cp2 the two non colocated points of a cubic curve as per wikipedia?

 

[Rainbow Child]

Ok then!

Your curve must be something like that

$$\vec{r}(t)=(1-t)^3\,\vec{p}_o+3\,t\,(1-t)^2\,\vec{p}_1+3\,t^2\,(1-t)\,\vec{p}_2+t^3\,\vec{p}_3$$

where $$\vec{p}_o,\,\vec{p}_1,\,\vec{p}_2,\,\vec{p}_3$$ are fixed.

Now the tangent to the curve is $$\dot{\vec{r}}(t)$$
If the second point is $$\vec{p}=(x_o,y_o)$$ the vector joining the two poins (on the curve and the one off it) is

$$\vec{R}(t)=\vec{r}(t)-\vec{p}$$

In order to find the point on the curve you have to solve the equation

$$\dot{\vec{r}}(t) \cdot \vec{R}(t)=0$$

 

[abeall]

just so we're all on the same page, perhaps you clarify your bezier notation a bit.
are cp1 & cp2 the two non colocated points of a cubic curve as per wikipedia?

This is the function I'm using to find a point on a cubic bezier, given a time/precent(0-1):
function getBezier(percent,p1,cp1,cp2,p2) {
function b1(t) { return t*t*t }
function b2(t) { return 3*t*t*(1-t) }
function b3(t) { return 3*t*(1-t)*(1-t) }
function b4(t) { return (1-t)*(1-t)*(1-t) }
var pos = {x:0,y:0};
pos.x = p1.x*b1(percent) + cp1.x*b2(percent) + cp2.x*b3(percent) + p2.x*b4(percent);
pos.y = p1.y*b1(percent) + cp1.y*b2(percent) + cp2.y*b3(percent) + p2.y*b4(percent);
return pos;
}

 

[abeall]

Rainbow Child,

That looks good, I think... unfortunately, I really don't understand what it is doing. To give you a sense of my mathematical ignorance, I don't understand the following:

1) What does 'r' represent?
2) What does 't' represent?
3) What does the arrow above certain things mean?

Beyond that, I really don't know how I would solve anything you presented and translate it into computer code(in this case it is syntax being executed in a JavaScript interpreter, though not actually browser JavaScript...). For instance, how would I solve the last equation that you have = 0?

Sorry for my ignorance, but thanks for trying to help me out -- that's why I came here. :)

 

[Rainbow Child]

This is the function I'm using to find a point on a cubic bezier, given a time/precent(0-1):
function getBezier(percent,p1,cp1,cp2,p2) {
function b1(t) { return t*t*t }
function b2(t) { return 3*t*t*(1-t) }
function b3(t) { return 3*t*(1-t)*(1-t) }
function b4(t) { return (1-t)*(1-t)*(1-t) }
var pos = {x:0,y:0};
pos.x = p1.x*b1(percent) + cp1.x*b2(percent) + cp2.x*b3(percent) + p2.x*b4(percent);
pos.y = p1.y*b1(percent) + cp1.y*b2(percent) + cp2.y*b3(percent) + p2.y*b4(percent);
return pos;
}

Ok! I will try to explain.

First of all $$\vec{r}(t)$$ represents your Bezier curve and it has an arrow above it because it stands for a vector , i.e. a point $$(x,y)$$. The $$t$$ is the variable belonging to the interval (0,1). In your code "time/precent(0-1)", right?

By ...programming skills have a maximum value of zero, but I will try to help.
As I can read your curve is

$$\vec{r}(t)=(1-t)^3\,\vec{p}_2+3\,t\,(1-t)^2\,\vec{cp}_2+3\,t^2\,(1-t)\,\vec{cp}_1+t^3\,\vec{p}_1$$

(forget the arrows, I have a problem with the correct formalism! )

Now the idea is to construct another "curve"

$$\dot{\vec{r}}(t)=-3\,t^2\,\vec{p}_2+(3-12\,t+9\,t^2)\,\vec{cp}_2+3\,t(2-3\,t)\,\vec{cp}_1+3\,t^2\,\vec{p}_1$$

exactly as you did for the Bezier curve.
Does it makes any sense until now?

 

[mda]

ok, another way to do this is to minimize the distance between pt and r, with respect to t.

You have to solve:
dx/dt (x-ptx) + dy/dt (y-pty) = 0.

This is a 6 term polynomial, so I would solve the entire problem using a linear algebra representation. That should be more efficient than testing the entire curve. The hardest part is finding the roots... the rest is straightforward.

 

[Rainbow Child]

ok, another way to do this is to minimize the distance between pt and r, with respect to t.

You have to solve:
dx/dt (x-ptx) + dy/dt (y-pty) = 0.

This is a 6 term polynomial, so I would solve the entire problem using a linear algebra representation. That should be more efficient than testing the entire curve. The hardest part is finding the roots... the rest is straightforward.

Sorry but that's exactly what

$$\dot{\vec{r}}(t) \cdot \vec{R}(t)=0$$

means!

 

[mda]

Sorry but that's exactly what

$$\dot{\vec{r}}(t) \cdot \vec{R}(t)=0$$

means!

sorry, didn't see your first post.
My main point was that linear algebra may be a convenient framework since the quintic is a bit messy and not that easy to solve.

 

[abeall]

Thanks Rainbow Child and mda,

I think I might understand it a little better... I might be able to translate that last curve, the one you said "Now the idea is to construct another "curve"" about. However, what does that curve represent? What I'm really looking for is one point.

Here, take a look at this:
http://abeall.com/files/temp/perpendicular.gif

targetP is a fixed point. The red lines are my P tangents(if that's a proper use of the term tangent) in the form of an angle, in degrees(ie not a vector), which I can calculate already. I'm trying to find what point along the curve is "perpendicular" to that point -- ie its tangent most closely intersects targetP.

Now, not to dilute the issue, which at its core is determine "how perpendicular" Pn is to targetP, but there is an added challenge: what I'm doing is stepping through the curve at a small increment, and when I overstep the perpendicular point, I back up and step through at a smaller increment, and repeat the process several iterations to achieve adaptive accuracy. This means I need to not only know "how perpendicular" a point is to targetP, but I also need to know if I overstep.

 

[Ben Niehoff]

The red lines in your image are not tangents. Are they meant to be normals? What is it you're trying to find, anyway?

 

[abeall]

The red lines in your image are not tangents. Are they meant to be normals?

Yeah, I guess they are normals, I don't know. Though in actuality, what I have is tangents/direction along line(technically, I'm finding the angle between a point and a previous point), and what is shown is 90 degrees from that to illustrate what I'm trying to find. I guess I need a layman's definition of tangent and normal in this context. But whatever they are called, that illustration shows them.

What is it you're trying to find, anyway?

In the illustration shown, I am trying to find Pn. The point which is "perpendicular" to targetP, I don't know any other way to say it.

 

[mda]

Thanks Rainbow Child and mda,
Now, not to dilute the issue, which at its core is determine "how perpendicular" Pn is to targetP, but there is an added challenge: what I'm doing is stepping through the curve at a small increment, and when I overstep the perpendicular point, I back up and step through at a smaller increment, and repeat the process several iterations to achieve adaptive accuracy. This means I need to not only know "how perpendicular" a point is to targetP, but I also need to know if I overstep.

abeall, there's a number of different 'root-finding algorithm' of varying complexity to do what you want. Try searching on wiki... the classic ones are bisection, secant and Newton. There's a tradeoff between accuracy and complexity, so I would suggest starting with the simplest one (bisection).

A lot of them essentially require that you keep track of the last function evaluation (your last value of R.r') which provides the info you need. If the sign has changed, you have overshot so you know you have 'bracketed' the root between your last value of t and the new one. The more complex methods take advantage of the slope (and higher order derivates) to guess the best place to check next, but that means more function evaluations so the speedup is limited.

 

[abeall]

After some research and experimentation, it appears that I can determine the point on the curve whose normal intersects the targetP quite easily: by finding the closest point! It's pretty obvious from looking at my illustration, but it also proved true in every other curve form I could come up with. The closest point on the curve to the targetP was also "perpendicular" as I wanted it.

So I'm now walking down the curve, comparing distance from current P to targetP(determined as p1^2 + p2^2 without taking the square root, because that's a slow operation in computing and unnecessary for comparison) compared to previous distance. When the distance begins to rise, I know I've overstepped, I back up and refine. Seems to be working.

 

[abeall]

Thanks mda, that's interesting. I'm looking into the bisection method...

 

[mda]

Also, in case you haven't realized, since the equation is quintic there's as many as five points on the line that satisfy the equation. (They aren't all equally close however; R will tell you that.) This means that if you use bisection you may run into problems where the sign changes an even number of times. But try it and find out

 

[mda]

After some research and experimentation, it appears that I can determine the point on the curve whose normal intersects the targetP quite easily: by finding the closest point!

Yes that will work too... now you are minimising |R| which is essentially the same as root-finding on its derivative. The connection between these two is that R'=r' since pt is fixed. You are determining the sign of the derivative by keeping track of the last function evaluation.

The root-finding algorithms can of course be adapted to minimisation... by taking the derivative (which can also be done numerically for smooth curves).