Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In aviation, runways are named according to their magnetic orientation seen from the pilot's perspective. For example: a strip of asphalt oriented along the east-west axis will be named 9 for the pilot coming from west (east is at 90° from North) and 27 for a pilot coming from east (west is 270° from North).

enter image description here

When several runways have the same orientation, the naming convention uses letters L/C/R for distinguishing between the Left/Centre/Right ones (look at the 22 runways in the capture above).

In the game I'm coding, I chose to describe runways by the following three attributes:

  • Orientation (between 0° and 180°).
  • Position of their geometrical centre relative to the aeroport one.
  • Length

With this data I'm able to generate all the touchdown points and give them the correct number, but I can't find a straightforward method to assign the correct letter, as I could not think to a straightforward way to mathematically determine which one is "left/centre/right" from a "landing pilot's perspective".

So the question is:

Is there a simple, straightforward vector formula that - given two parallel vectors pointing in the same direction - will return the leftmost (or rightmost) one?

Please note that this question is really about the straightforwardness of the formula, as I already found a non-straightforward way to get the result, but I would like to find a more elegant way to solve the problem.

Many thanks in advance for your expertise and contributions!

share|improve this question
    
do you mean leftmost and rightmost in absolute terms (when looking at the map), or relative to each other (when standing on one of these runways and facing in the direction they point) ? –  TravisG Aug 12 '11 at 22:04
1  
As stated in the question: "from the pilot's perspective". :) –  mac Aug 12 '11 at 22:57
    
@heishe Note that this naming scheme has the effect that a runway named L in one end is named R in the other end. –  eBusiness Aug 12 '11 at 23:17
1  
I always wondered about the runway numbering scheme. –  Josh Petrie Aug 13 '11 at 5:01
add comment

2 Answers 2

up vote 7 down vote accepted

Of course there is. Compute the determinant of the orientation vector of the runways and the vector from one runway centre to another, the result will be positive or negative depending on which runway are to the right of the other.

Calculation of determinant for a pair of 2D vectors:

Det(A,B) = Ax*By - Ay*Bx

There is a load of other stuff one can learn about the use of determinants, but for this purpose it's all you need to know.

Edit, same thing in different words:
Compute the dot product of the orientation vector of the runways and the tværvector of the vector from one runway centre to another, the result will be positive or negative depending on which runway are to the right of the other.

DotProduct(A,B) = Ax*Bx + Ay*By

A tværvector is the rotation of a 2D vector 90 degrees counter-clockwise. The tværvector T of A is calculated as follow:

Tx = -Ay
Ty = Ax

Edit, I guess I should try to explain why this works.
The result of a dot product is equal to the product of the length of the two vectors, by the cosine of the angle between them. Since lengths are always positive and cosine is positive for angles in the range ]-90 deg; 90 deg[ the dot product is positive for acute angles, and negative for obtuse angles.

Imagine two parallel lines and a vector from any point on line 1 to any point on line 2, this vector may point in any direction within a 180 degrees arc, except from the two extremes. If we rotate this vector 90 degrees we also rotate the arc 90 degrees. This rotated arc is positioned exactly so that a vector parallel to the lines will either have an acute angle to all vectors within the arc, or an obtuse angle to all of them, depending on the position of the lines and the direction of the vector. Since the dot product works as an acute/obtuse test it can be used to tell whether a line is to the right of left of another, depending on which direction you look at them.

share|improve this answer
    
Thank you eBusiness, I will look into this more accurately tomorrow, but it seems exactly what I was looking for. :) It's the first time I hear about determinants, and I had a quick look at the wikipedia entry for that, however it seems quite broad in scope. If you happen to have some link that you think would help me understand better the theory behind the solution, I would be grateful if you would share them. :) –  mac Aug 12 '11 at 22:55
    
It's the terminology I learned in school, I do have a different terminological version, but it seems that the English language lacks a word. Screw that, I'll just add the Danish word to the English language. As for the two solutions being virtually the same, Lars Viklund uses a projection where I use a dot product. –  eBusiness Aug 13 '11 at 13:13
3  
In his book Real-Time Collision Detection, Christer Ericson uses notation of the vector name raised to _|_, which is pronounced "u-perp" for the tværvector to u. As for dot product versus (scalar projection)[en.wikipedia.org/wiki/Dot_product#Scalar_projection), I assumed that it was known that the common way to do such a projection was via the dot product. It's most excellent that you covered computing the perpendicular vector, as I forgot to mention the operation. –  Lars Viklund Aug 13 '11 at 14:18
    
@Lars - Thank you for this comment, that was very useful. Gratitude expressed in form of +1 to your answer! ;) –  mac Aug 13 '11 at 14:36
    
@eBusiness - Thank you for having taken the time to explain the method you suggested. Perfect answer. Accepted. –  mac Aug 13 '11 at 14:37
show 4 more comments

Compute a vector perpendicular to the runways that share an orientation, in such a fashion that it always points in a particular direction (right, for example) as seen from the runway's perspective. As you have the orientation, such a vector can be computed by rotating an unit vector like <0, 1> by the angle+90 to get a vector that points "rightward".

Then you can project the runway centers onto this right-vector, which will result in a scalar that denotes how far along the right-vector they are, which is what you want to order by to get them in local left-to-right.

An alternative and mathematically equivalent method is to rotate the center points by -angle and project them onto the X axis, ordering them by their position there.

share|improve this answer
    
Tack Lars for this. This is pretty much the method I already come up with. It works, but I find it overlay complex for my taste. –  mac Aug 12 '11 at 22:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.