# Determine if 3 points form a right angle

1. Dec 29, 2007

### 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

2. Dec 29, 2007

### mgb_phys

3. Dec 29, 2007

### JonF

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

4. Dec 29, 2007

### HallsofIvy

Staff Emeritus
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.

5. Dec 29, 2007

### JonF

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!

6. Dec 29, 2007

### 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...

7. Dec 29, 2007

### 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.

Last edited: Dec 29, 2007
8. Dec 29, 2007

### Rainbow Child

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

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? )

9. Dec 29, 2007

### abeall

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.

Last edited: Dec 29, 2007
10. Dec 29, 2007

### 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?

11. Dec 29, 2007

### 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$$

12. Dec 29, 2007

### abeall

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;
}

13. Dec 30, 2007

### 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. :)

14. Dec 30, 2007

### Rainbow Child

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.

$$\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 sence until now?

Last edited: Dec 30, 2007
15. Dec 30, 2007

### 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.

16. Dec 30, 2007

### Rainbow Child

Sorry but that's exactly what

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

means!

17. Dec 30, 2007

### mda

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.

18. Dec 30, 2007

### 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.

Last edited: Dec 30, 2007
19. Dec 30, 2007

### 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?

20. Dec 30, 2007

### abeall

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.

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.

Last edited: Dec 30, 2007