[Math] Determining perpendicular angle...

[Guest]

It seemed like it should be trivially easy, however, the past several hours(!) have proven otherwise, at least for me.

I have a series of points with angles. I want to know which of these points is the "most perpendicular" to a target point. If I have to walk each point, that is fine.

So I have something like:

P1 = {x:25,y:15,angle:45}
P1 = {x:73,y:375,angle:180}
P1 = {x:35,y:135,angle:-56}
etc
targetP = {x:75,y:15,angle:15}

Which P is the most perpendicular to targetP?

I should note that in actually, these points fall along a bezier curve(the angle for each point is the tangent). So they aren't randomly placed.

I've gotten sorta close. I'm walking through the points, performing some basic math so that perpendicular is always 0, then when I "pass over" 0 I know I just passed perpendicular, so in between the two points is perpendicular:

currAngle = angle1-angle2;
if(currAngle>180) currAngle -= 180;
if(currAngle<-180) currAngle += 180;
currAngle = 90-Math.abs(currAngle);
if((currAngle>0 && prevAngle<0) || (currAngle<0 && prevAngle>0)){
// I have just passed perpendicular....?
}

The problem is it isn't always the case. Sometimes, it seems, that the angles go from positive, to 0, then back to positive again. Additionally, sometimes it goes from 90 to -90, thus triggering 'perpendicular' when it isn't actually. My math is just bad. I need a reliable way to determine which point/angle pair is most perpendicular with a given point, accounting for Flash's -180 to 180 angle measurement.

Thanks for any help!

[Newsgroup_User]

I'm not sure if I just understand, do you mean something like this?
Hope can help...

/* I suppose ang and target can vary from -180 to +180 and the two
angle are in the same space */
public function mostPerpIndex(angArray:Array,target:Number):uint {
var mostPerpIndex:uint =0;
var mostPerpAngle:Number=360;
if(target<0) {
target=(target+360)%360;
}
for(var i:uint=0;i<angArray.length;i++) {
var testAng:Number;
if(angArray <0){
testAng=(angArray+360)%360;
} else {
testAng=angArray ;
}
var temp:Number;
if(target>testAng) {
temp = target-testAng;
} else {
temp = testAng-target;
}
var diff:Number =
Math.min(Math.abs(90-temp),Math.abs(270-temp));
if(diff<mostPerpAngle) {
mostPerpAngle=diff;
mostPerpIndex=i;
}
}
return mostPerpIndex;
}

[kglad]

it makes no sense to talk about anything being perpendicular to a point. perpendicularity is a property of two lines.

you can ask which line determined by the data in P1, P2 etc is closest to A perpendicular to the line determined by the targetP data. ie, which line intersects the targetP line at an angle closest to 90 degrees. (note, there is no unique perpendicular to a line. there are many, one passing through each point of the line.)

or you can ask, given the targetP line, and its perpendicular passing through the point in targetP (a unique line), which point (in P1, P2 etc) is closest to that perpendicular.

or you might want something else. what is that you want?

[Guest]

> it makes no sense to talk about anything being perpendicular to a point. perpendicularity is a property of two lines.

I have two points: P along a curve, targetP. For each P I have an already determined tangent in the form of an angle, in degrees. I think what I really want to know is which P's tangent is closest to intersecting targetP. It's really hard to explain... take a look at this illustration:
http://abeall.com/files/temp/perpendicular.gif

The red lines represent my P tangents. targetP is fixed, and notice how Pn is clearly the only point which is "perpendicular" to the targetP, or whose tangent intersects targetP, or whatever that should be called. I can solve for as many P along the curve as I need, I need to know which of them is Pn.

The curve is a cubic bezier, incidentally. My curve function is attached.

Now, I don't want to dilute the issue, which at its core is finding what P is closest to having its tangent intersect targetP, but the added challenge is this: to begin with, I have no points, and I solve the bezier curve for one point at one end, 0.1 time(time ranges from 0-1), and see how "perpendicular" it is. Then, I solve at 0.2 time, and so forth, incrementing by 0.1 until I can see that I've overstepped the perpendicular point. So say I'm at 0.4 and it is almost perpendicular, and 0.5 is a little passed perpendicular -- perpendicular must be betweeon 0.4 and 0.5. Right now I'm relying on a negative-positive switch, ie a little before perpendicular is a small positive number, a little past perpendicular is a small negative number. Then I repeat the process between 0.4 and 0.5, incrementing by 0.01 this time. I repeat the process recursively several decimal points to achieve adaptive accuracy. Where I'm having a problem with the method I came up with is that I can't accurately tell when I've overstepped "perpendicularity" (because there isn't always a negative-to-positive or positive-to-negative switch when overstepping) and so I effectively can't find Pn at all.

Don't let it distract you too much, but I've also attached the [not-working] method I have to find Pn.

Thanks.

[kglad]

given a point (targetP) and a curve C, you want to find the point Pn on C that is closest to targetP. correct?

[Guest]

> given a point (targetP) and a curve C, you want to find the point Pn on C
> that is closest to targetP. correct?

Not necessarily the closest by proximity, but closest to intersecting the tangent... the illustration I've shown is a case where that is also the closest by proximity, but take a look at this one:
http://abeall.com/files/temp/perpendicular2.gif

[EDIT]Actually, the curve and point combination shown here is an impossible situation that would never occur... let me do a bit more testing to see if a similar scenario is even possible, or if indeed the shortest distance would represent the point I want[/EDIT]

In this case, because the tangents are going the other direction, or rather because the curve bends backwards, targetP is much closer in proximity to points on the opposite end than I need. However, there is still only one point, Pn, whose tangent intersects targetP.

[Guest]

By golly, I think you're right(not that I should be surprised): while the point I want is the point whose tangent intersects targetP, it seems that point is always the closest point to targetP as well. So I guess all I need is a good way to determine what point is closest!

Now, keep in mind that Pn may be the closest by only a very minute margin compared to nearby points, so close, in fact, that if I was doing a simple mathematical comparison of a set of points, I'd be worried(perhaps unnecessarily) about rounding errors...

Also, keep in mind that, while I have the cubic bezier function, I do not have an infinite number of points to compare, and I want the number of points calculated to be as minimal as possible (thus my recursive/adaptive approach described earlier). This means that if I were to walk through the curve points and simply measure distance to targetP, I would likely get something like this:

time => distance to targetP
0.1 => 25
0.2 => 15
0.3 => 5
0.4 => 5

Now, in reality the point I want is between 0.3 and 0.4. How would I be able to tell that, though since distance is the same in both cases?

[kglad]

i think you're being misled by your drawing.

you have a curve C consisting of points P. for each point P there is a tangent to C (through P). this tangent has a perpendicular line through P. let's call this line: P's perpendicular.

you want to find a point P whose perpendicular passes through targetP. correct?

if yes, that's the point P on C that's closest to targetP (if C is a cubic bezier).

[Guest]

quote:

---

Originally posted by: kglad
i think you're being misled by your drawing.

you have a curve C consisting of points P. for each point P there is a tangent to C (through P). this tangent has a perpendicular line through P. let's call this line: P's perpendicular.

you want to find a point P whose perpendicular passes through targetP. correct?

if yes, that's the point P on C that's closest to targetP (if C is a cubic bezier).

---

Yeah, I think you're right... the P on C closest to targetP appears to be the point I'm looking for.

[Guest]

kglad,

It works! I can simply compare a series of points distance(as measured by p1^2 + p2^2 without taking the square root) and the closest point on C is also the point who's tanget is "perpendicular" to targetP. Thanks!

Here's another one for you, if you are up for it: given two angles on Flash's -180 to 180 measurement, how do I find the average angle between? That's another one I thought would be easy, but I'm getting all sorts of strange behavior...

[kglad]

are these vectors? are you trying to find the resultant vector?

[Guest]

It's two angles, and I want to find the angle between them. However, the angle between is not necessarily the average... for instance, an angle of -175 and 175 would have an average of 0, but I would actually want the angle 180 or -180 because it's more "between" them. After some dumb experimentation, I came up with this:

var a1_2 = getAngle(d1,d2);
var a1_3 = getAngle(d1,d3);
var avg = (a1_2+a1_3)/2;
if(Math.abs(a1_2-a1_3)>180)
avg -= 180;
d1.rotation = avg;

I think it works. The challenge was that there's sort of a "loop" at -180 to 180 that I wanted to intelligently cross over.

[kglad]

you might find it helpful to standardize all your angle measurements to numbers between 0 and 360. you can then take averages (and more) and get expected results:

[Guest]

Cool. Thanks!

And is it just me, or does auto-format in CS3 really unreliable? I used to use it a lot, but it seems to cause errors more often than not in AS3.

[kglad]

it's usually ok, but not always.