Difference between revisions of "Computational geometry"
(added chapter on line segments) |
(h = t*sqrt(A^2 + B^2), how come t = h/(A^2 + B^2), should not it be t = h/sqrt(A^2 + B^2)) |
||
(18 intermediate revisions by one other user not shown) | |||
Line 13: | Line 13: | ||
been exposed, countless times, in mathematics class, perhaps without being told that other geometries exist. | been exposed, countless times, in mathematics class, perhaps without being told that other geometries exist. | ||
So in all that follows, the universe is two-dimensional, parallel lines never meet, the area of a circle with | So in all that follows, the universe is two-dimensional, parallel lines never meet, the area of a circle with | ||
− | radius <math>r</math> is <math>\pi r^2</math>, and so on. | + | radius <math>r</math> is <math>\pi r^2</math>, and so on. This article discusses basic two-dimensional computational geometry; more advanced topics, such as computation of [[Convex hull|convex hulls]], are discussed in separate articles. |
=Points= | =Points= | ||
− | ==Introduction== | + | ==Introduction to points== |
Many would claim that the point is the fundamental unit of geometry. Lines, circles, and polygons are all | Many would claim that the point is the fundamental unit of geometry. Lines, circles, and polygons are all | ||
merely (infinite) collections of points and in fact we will initially consider them as such in order to derive | merely (infinite) collections of points and in fact we will initially consider them as such in order to derive | ||
Line 62: | Line 62: | ||
==The equation of a line== | ==The equation of a line== | ||
In computational geometry, we have to treat all aspects of geometry algebraically. Computers are excellent at dealing with numbers but have no mechanism for dealing with geometrical constructions; rather we must reduce | In computational geometry, we have to treat all aspects of geometry algebraically. Computers are excellent at dealing with numbers but have no mechanism for dealing with geometrical constructions; rather we must reduce | ||
− | them to algebra if we wish to accomplish anything. | + | them to algebra if we wish to accomplish anything. |
− | In Ontario high schools, the ''equation of a line'' is taught in the ninth grade. For example, the line which passes through the points (0,1) and (1,0) has the equation <math> x + y = 1 </math>. Precisely, this means that for a given point <math>(x,y)</math>, the statement <math>x + y = 1</math> is equivalent to, or sufficient and necessary for, the point to be on the line. | + | |
+ | In Ontario high schools, the ''equation of a line'' is taught in the ninth grade. For example, the line which passes through the points (0,1) and (1,0) has the equation <math> x + y = 1 </math>. Precisely, this means that for a given point <math>(x,y)</math>, the statement <math>x + y = 1</math> is equivalent to, or sufficient and necessary for, the point to be on the line. | ||
+ | |||
The form of the equation of the line which is first introduced is generally the <math> y = mx + b </math>, in which <math> m </math> is the slope of the line and <math> b </math> is the y-intercept. For example, the line discussed above has the equation <math> y = -x + 1 </math>, that is, <math> m = -1 </math> and <math> b = 1 </math>. By substituting different values for <math> m </math> and <math> b </math>, we can obtain various (different) lines. But there's a problem here: if your line is vertical, then it is not | The form of the equation of the line which is first introduced is generally the <math> y = mx + b </math>, in which <math> m </math> is the slope of the line and <math> b </math> is the y-intercept. For example, the line discussed above has the equation <math> y = -x + 1 </math>, that is, <math> m = -1 </math> and <math> b = 1 </math>. By substituting different values for <math> m </math> and <math> b </math>, we can obtain various (different) lines. But there's a problem here: if your line is vertical, then it is not | ||
− | possible to choose values of <math> m </math> and <math> b </math> for the line. (Try it!) This is because the y-coordinate is no longer a function of the x-coordinate. | + | possible to choose values of <math> m </math> and <math> b </math> for the line. (Try it!) This is because the y-coordinate is no longer a function of the x-coordinate. |
+ | |||
Thus, when dealing with lines computationally, it seems we would need to have | Thus, when dealing with lines computationally, it seems we would need to have | ||
a special case: check if the line is vertical; if so, then do something, | a special case: check if the line is vertical; if so, then do something, | ||
Line 73: | Line 76: | ||
==Standard Form of the equation of a line== | ==Standard Form of the equation of a line== | ||
Even though the slope-intercept form cannot describe a vertical line, there ''is'' an equation that describes a vertical line. For example, the line passing through (3,1) and (3,8) is <math> x = 3 </math>. In fact, almost any line can be described by an equation of the form <math> x = my + b </math>. (Try it if you don't believe me. I have merely switched around <math>x</math> and <math>y</math> from the slope-intercept form.) Except... ''horizontal'' lines. So we have two forms of the equation of a line: one which fails on vertical lines and one which fails on horizontal lines. Can we combine them to give an equation of the line which is valid for ''any'' | Even though the slope-intercept form cannot describe a vertical line, there ''is'' an equation that describes a vertical line. For example, the line passing through (3,1) and (3,8) is <math> x = 3 </math>. In fact, almost any line can be described by an equation of the form <math> x = my + b </math>. (Try it if you don't believe me. I have merely switched around <math>x</math> and <math>y</math> from the slope-intercept form.) Except... ''horizontal'' lines. So we have two forms of the equation of a line: one which fails on vertical lines and one which fails on horizontal lines. Can we combine them to give an equation of the line which is valid for ''any'' | ||
− | line? | + | line? |
− | As it turns out, it is indeed possible. | + | |
+ | As it turns out, it is indeed possible. | ||
+ | |||
That equation, the ''standard form of the equation of the line'' is: | That equation, the ''standard form of the equation of the line'' is: | ||
:<math> \displaystyle Ax + By + C = 0 </math> | :<math> \displaystyle Ax + By + C = 0 </math> | ||
By substituting appropriate values of <math> A </math>, <math> B </math>, and <math> C </math>, one can | By substituting appropriate values of <math> A </math>, <math> B </math>, and <math> C </math>, one can | ||
describe any line with this equation. And by storing values of <math> A </math>, <math> B </math>, and <math> C </math>, one can represent a line in the computer's memory. | describe any line with this equation. And by storing values of <math> A </math>, <math> B </math>, and <math> C </math>, one can represent a line in the computer's memory. | ||
− | Here are some pairs of points and possible equations for each: | + | Here are some pairs of points and possible equations for each: |
:<math> | :<math> | ||
\begin{array}{llll} | \begin{array}{llll} | ||
Line 89: | Line 94: | ||
</math> | </math> | ||
As you can see, it handles vertical and horizontal lines properly, as well | As you can see, it handles vertical and horizontal lines properly, as well | ||
− | as lines which are neither. | + | as lines which are neither. |
+ | |||
Note that the standard form is not unique: for example, the equation of the | Note that the standard form is not unique: for example, the equation of the | ||
first line could have just as well been <math> -x - y + 1 = 0 </math> or perhaps | first line could have just as well been <math> -x - y + 1 = 0 </math> or perhaps | ||
<math> 5x + 5y - 5 = 0 </math>. Any given line has infinitely many representations | <math> 5x + 5y - 5 = 0 </math>. Any given line has infinitely many representations | ||
in the standard form. However, each standard form representation describes | in the standard form. However, each standard form representation describes | ||
− | at most one line. | + | at most one line. |
+ | |||
If <math> A </math> and <math> B </math> are both zero, the standard form describes no line | If <math> A </math> and <math> B </math> are both zero, the standard form describes no line | ||
at all. | at all. | ||
Line 125: | Line 132: | ||
==Construction of the line through two given points== | ==Construction of the line through two given points== | ||
− | A good question is: ''how'' do we determine that fourth equation above, the equation of the line through (6,6) and (4,9)? It's not immediately obvious from the two points given, whereas the other three are pretty easy. | + | A good question is: ''how'' do we determine that fourth equation above, the equation of the line through (6,6) and (4,9)? It's not immediately obvious from the two points given, whereas the other three are pretty easy. |
+ | |||
For the slope-y-intercept form <math> y = mx + b </math>, you first determined the slope | For the slope-y-intercept form <math> y = mx + b </math>, you first determined the slope | ||
<math> m </math>, and then solved for <math> b </math>. A similar procedure can be used for | <math> m </math>, and then solved for <math> b </math>. A similar procedure can be used for | ||
Line 173: | Line 181: | ||
If two lines are coincident, every point on either line is an intersection | If two lines are coincident, every point on either line is an intersection | ||
point. If they are parallel, then no intersection points exist. We consider the | point. If they are parallel, then no intersection points exist. We consider the | ||
− | general case in which neither is true. | + | general case in which neither is true. |
+ | |||
In general, two lines intersect at a single point. That is, the intersection | In general, two lines intersect at a single point. That is, the intersection | ||
point is the single point that lies on both lines. Since it lies on both lines, | point is the single point that lies on both lines. Since it lies on both lines, | ||
Line 218: | Line 227: | ||
\begin{array}{rl} | \begin{array}{rl} | ||
1. & det \gets A_1 B_2 - A_2 B_1 \\ | 1. & det \gets A_1 B_2 - A_2 B_1 \\ | ||
− | 2. & \mathrm{if}\ det = 0 | + | 2. & \mathrm{if}\ det = 0 \\ |
3. & \ \ \ \ \ \mathrm{fail} \\ | 3. & \ \ \ \ \ \mathrm{fail} \\ | ||
− | 4. & \mathrm{else} | + | 4. & \mathrm{else} \\ |
5. & \ \ \ \ \ x \gets (B_1 C_2 - B_2 C_1)/det \\ | 5. & \ \ \ \ \ x \gets (B_1 C_2 - B_2 C_1)/det \\ | ||
6. & \ \ \ \ \ y \gets (A_2 C_1 - A_1 C_2)/det | 6. & \ \ \ \ \ y \gets (A_2 C_1 - A_1 C_2)/det | ||
Line 231: | Line 240: | ||
==Direction numbers for a line== | ==Direction numbers for a line== | ||
This in itself is not very useful, but it will become important in the | This in itself is not very useful, but it will become important in the | ||
− | following sections as a simplifying concept. | + | following sections as a simplifying concept. |
+ | |||
Lines are straight; effectively they always point in the same direction. One | Lines are straight; effectively they always point in the same direction. One | ||
way to express that direction has been slope, which unfortunately is undefined | way to express that direction has been slope, which unfortunately is undefined | ||
Line 243: | Line 253: | ||
<math> (2,2m) </math> is also a set of direction numbers for that line, or, indeed, any | <math> (2,2m) </math> is also a set of direction numbers for that line, or, indeed, any | ||
multiple of <math> (1,m) </math> other than <math> (0,0) </math>. (<math> (0,0) </math> | multiple of <math> (1,m) </math> other than <math> (0,0) </math>. (<math> (0,0) </math> | ||
− | clearly tells you nothing about the line.) | + | clearly tells you nothing about the line.) |
+ | |||
We can define something similar for the line in standard form. Choose some | We can define something similar for the line in standard form. Choose some | ||
starting point <math> (x_0,y_0) </math> on line <math> l </math>. Now, move to a new point | starting point <math> (x_0,y_0) </math> on line <math> l </math>. Now, move to a new point | ||
Line 271: | Line 282: | ||
is an "if-and-only-if" relationship. If <math> \Delta x </math> and <math> \Delta y </math> are | is an "if-and-only-if" relationship. If <math> \Delta x </math> and <math> \Delta y </math> are | ||
in the ratio <math> -B:A </math>, then we can "shift" by <math> (\Delta x,\Delta y) </math>, | in the ratio <math> -B:A </math>, then we can "shift" by <math> (\Delta x,\Delta y) </math>, | ||
− | and ''vice versa''. | + | and ''vice versa''. |
+ | |||
Any line perpendicular to <math> l </math> will have the direction numbers <math> (A,B) </math>, | Any line perpendicular to <math> l </math> will have the direction numbers <math> (A,B) </math>, | ||
and thus a possible equation starts <math> -Bx + Ay + \ldots = 0 </math>. | and thus a possible equation starts <math> -Bx + Ay + \ldots = 0 </math>. | ||
Line 280: | Line 292: | ||
perpendicularity: given two lines with direction numbers <math> (A,B) </math> and | perpendicularity: given two lines with direction numbers <math> (A,B) </math> and | ||
<math> (C,D) </math>, they are perpendicular [http://en.wikipedia.org/wiki/If_and_only_if if and only if] | <math> (C,D) </math>, they are perpendicular [http://en.wikipedia.org/wiki/If_and_only_if if and only if] | ||
− | <math> AC + BD = 0 </math>. | + | <math> AC + BD = 0 </math>. |
+ | |||
Given some line, all lines parallel to that one have the same direction numbers. That is, the direction | Given some line, all lines parallel to that one have the same direction numbers. That is, the direction | ||
numbers, while providing information about a line's direction, provide no | numbers, while providing information about a line's direction, provide no | ||
information about its position. However, sometimes all that is needed is the direction, and here the | information about its position. However, sometimes all that is needed is the direction, and here the | ||
direction numbers are very useful. | direction numbers are very useful. | ||
+ | |||
+ | ==Parametric equation of a line== | ||
+ | Given some line <math>Ax + By + C = 0</math> and a point <math>(x_0, y_0)</math> known to be on the line, we can use the direction numbers to write the parametric equation of the line. Since <math>(-B,A)</math> is a set of direction numbers for the line, we see that <math>(x_0 - Bt, y_0 + At)</math> will be on the line for any <math>t</math>, and furthermore each point on the line corresponds to exactly one value of <math>t</math> in this way. | ||
+ | |||
+ | ==Translation along a line== | ||
+ | Given some line <math>Ax + By + C = 0</math> and a point <math>(x_0, y_0)</math> known to be on the line, we wish to locate another point on the line that is distance <math>h</math> away from <math>(x_0, y_0)</math>. We can do this by observing that the general point is given by <math>(x_0 - Bt, y_0 + At)</math>, which is distance <math>\sqrt{(Bt)^2 + (At)^2} = t \sqrt{A^2+B^2} = h</math> away from <math>(x_0, y_0)</math>. Therefore, we want <math>t = \frac{h}{\sqrt{A^2+B^2}}</math>, and finally obtain <math>\left(x_0 - \frac{Bh}{\sqrt{A^2+B^2}}, y_0 + \frac{Ah}{\sqrt{A^2+B^2}}\right)</math>. Note that unless <math>h=0</math>, there is another possible answer, which is simply "on the other side": <math>\left(x_0 + \frac{Bh}{\sqrt{A^2+B^2}}, y_0 - \frac{Ah}{\sqrt{A^2+B^2}}\right)</math>. | ||
==Dropping a perpendicular== | ==Dropping a perpendicular== | ||
Line 298: | Line 317: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
− | where <math> A'x+B'y+C'=0 </math> is the perpendicular line desired. | + | where <math> A'x+B'y+C'=0 </math> is the perpendicular line desired. |
+ | |||
There is nothing difficult to memorize here: we already noted in the previous | There is nothing difficult to memorize here: we already noted in the previous | ||
section how to find the values of <math> A' </math> and <math> B' </math>, and finding the value | section how to find the values of <math> A' </math> and <math> B' </math>, and finding the value | ||
of <math> C' </math> is merely setting <math> A'x_0+B'y_0+C' </math> equal to zero (so that the | of <math> C' </math> is merely setting <math> A'x_0+B'y_0+C' </math> equal to zero (so that the | ||
− | point <math> (x_0,y_0) </math> will be on the resulting line). | + | point <math> (x_0,y_0) </math> will be on the resulting line). |
+ | |||
The ''foot'' of the perpendicular is the point at which it intersects the | The ''foot'' of the perpendicular is the point at which it intersects the | ||
line <math> l </math>. It is guaranteed to exist since two lines cannot, of course, be | line <math> l </math>. It is guaranteed to exist since two lines cannot, of course, be | ||
Line 325: | Line 346: | ||
from <math> P </math> to <math> l </math>. That is, we choose a point <math> Q </math> such that | from <math> P </math> to <math> l </math>. That is, we choose a point <math> Q </math> such that | ||
<math> PQ \perp l </math>, and the distance from <math> P </math> to <math> l </math> is then the length | <math> PQ \perp l </math>, and the distance from <math> P </math> to <math> l </math> is then the length | ||
− | of line segment <math> \overline{PQ} </math>, denoted <math> |PQ| </math>. | + | of line segment <math> \overline{PQ} </math>, denoted <math> |PQ| </math>. |
− | + | ||
The reason why this is the shortest distance possible is this: Choose any other | The reason why this is the shortest distance possible is this: Choose any other | ||
point <math> R </math> on <math> l </math>. Now, <math> \triangle PQR </math> is right-angled at <math> Q </math>. | point <math> R </math> on <math> l </math>. Now, <math> \triangle PQR </math> is right-angled at <math> Q </math>. | ||
The longest side of a right triangle is the hypotenuse, so that | The longest side of a right triangle is the hypotenuse, so that | ||
− | <math> |PR| > |PQ| </math>. Thus <math> |PQ| </math> is truly the shortest possible distance. | + | <math> |PR| > |PQ| </math>. Thus <math> |PQ| </math> is truly the shortest possible distance. |
− | + | ||
Now, as noted earlier, the line <math> PQ </math>, being perpendicular to <math> l </math>, has the direction numbers <math> (A,B) </math>. Thus, for any <math> t </math>, the point <math> (x_0+At,y_0+Bt) </math> is on | Now, as noted earlier, the line <math> PQ </math>, being perpendicular to <math> l </math>, has the direction numbers <math> (A,B) </math>. Thus, for any <math> t </math>, the point <math> (x_0+At,y_0+Bt) </math> is on | ||
<math> PQ </math>. For some choice of <math> t </math>, this point must coincide with <math> Q </math>. | <math> PQ </math>. For some choice of <math> t </math>, this point must coincide with <math> Q </math>. | ||
Line 344: | Line 365: | ||
</math> | </math> | ||
This instantly gives the formula for the foot of the perpendicular given in | This instantly gives the formula for the foot of the perpendicular given in | ||
− | the previous section. | + | the previous section. |
+ | |||
Now, the distance <math> |PQ| </math> is found with the Euclidean formula: | Now, the distance <math> |PQ| </math> is found with the Euclidean formula: | ||
:<math>\displaystyle | :<math>\displaystyle | ||
Line 369: | Line 391: | ||
when a point <math> P </math> <math> (x_0,y_0) </math> does not satisfy the equation of a line | when a point <math> P </math> <math> (x_0,y_0) </math> does not satisfy the equation of a line | ||
<math> l </math> <math> (Ax+By+C=0) </math>, can we determine on which side of the line it lies? | <math> l </math> <math> (Ax+By+C=0) </math>, can we determine on which side of the line it lies? | ||
− | + | ||
Yes we can, with a certain restriction. If <math> Ax_0 + By_0 + C > 0 </math>, then the | Yes we can, with a certain restriction. If <math> Ax_0 + By_0 + C > 0 </math>, then the | ||
point lies on one side of the line; if <math> Ax_0 + By_0 + C < 0 </math>, then it lies | point lies on one side of the line; if <math> Ax_0 + By_0 + C < 0 </math>, then it lies | ||
Line 407: | Line 429: | ||
1. & d_1 \gets C_1/\sqrt{A_1^2+B_1^2} \\ | 1. & d_1 \gets C_1/\sqrt{A_1^2+B_1^2} \\ | ||
2. & d_2 \gets C_2/\sqrt{A_2^2+B_2^2} \\ | 2. & d_2 \gets C_2/\sqrt{A_2^2+B_2^2} \\ | ||
− | 3. & \mathrm{if} A_1 \neq 0 | + | 3. & \mathrm{if} A_1 \neq 0 \\ |
− | 4. & \ \ \ \ \ \mathrm{if} A_1 \mathrm{\,and\,} A_2 \mathrm{\,have\ the\ same\ sign | + | 4. & \ \ \ \ \ \mathrm{if} A_1 \mathrm{\,and\,} A_2 \mathrm{\,have\ the\ same\ sign} \\ |
5. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 - d_2| \\ | 5. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 - d_2| \\ | ||
− | 6. & \ \ \ \ \ \mathrm{else | + | 6. & \ \ \ \ \ \mathrm{else} \\ |
7. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 + d_2| \\ | 7. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 + d_2| \\ | ||
8. & \mathrm{else:} \\ | 8. & \mathrm{else:} \\ | ||
− | 9. & \ \ \ \ \ \mathrm{if} B_1 \mathrm{\,and\,} B_2 \mathrm{\,have\ the\ same\ sign | + | 9. & \ \ \ \ \ \mathrm{if} B_1 \mathrm{\,and\,} B_2 \mathrm{\,have\ the\ same\ sign} \\ |
10. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 - d_2| \\ | 10. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 - d_2| \\ | ||
− | 11. & \ \ \ \ \ \mathrm{else | + | 11. & \ \ \ \ \ \mathrm{else} \\ |
12. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 + d_2| | 12. & \ \ \ \ \ \ \ \ \ \ dist \gets |d_1 + d_2| | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
+ | |||
+ | ==Translating a line== | ||
+ | Suppose we are given a line <math>Ax + By + C = 0</math> and we wish to find a line parallel to it such that the distance between these two lines is <math>h</math>. To do this, we suppose that the new line has equation <math>Ax + By + D = 0</math>. Since the two lines have the same <math>A</math> and <math>B</math> value, they must be parallel (or coincident of <math>C = D</math> also). Then, the distance between them will be given by <math>\frac{|C-D|}{\sqrt{A^2+B^2}}</math>, as the previous section suggests. To obtain a value of <math>h</math> for this expression, it is not hard to see that we should choose <math>D = C \pm h\sqrt{A^2+B^2}</math>. | ||
=Line segments= | =Line segments= | ||
− | ==Introduction== | + | ==Introduction to line segments== |
A line segment is the part of a line located "between" two points on that | A line segment is the part of a line located "between" two points on that | ||
line, called ''endpoints''. Any pair of points defines a unique line | line, called ''endpoints''. Any pair of points defines a unique line | ||
Line 460: | Line 485: | ||
==Determining if a point lies on a line segment== | ==Determining if a point lies on a line segment== | ||
Here is one interesting idea: if a point <math> R </math> lies on segment <math> \overline{PQ} </math>, then the relation | Here is one interesting idea: if a point <math> R </math> lies on segment <math> \overline{PQ} </math>, then the relation | ||
− | <math> |PR| + |RQ| = |PQ| </math> will hold. If it is on the | + | <math> |PR| + |RQ| = |PQ| </math> will hold. If it is on the ''line'' <math> PQ </math> but |
− | not on the | + | not on the ''segment'' <math> \overline{PQ} </math>, then it is the ''difference'' |
between <math> |PR| </math> and <math> |RQ| </math> that will equal <math> |PQ| </math>, not the sum. If | between <math> |PR| </math> and <math> |RQ| </math> that will equal <math> |PQ| </math>, not the sum. If | ||
it is not on this line, then the points <math> P </math>, <math> Q </math>, and <math> R </math> form a | it is not on this line, then the points <math> P </math>, <math> Q </math>, and <math> R </math> form a | ||
Line 546: | Line 571: | ||
certainly slower as division by two is a very fast operation. | certainly slower as division by two is a very fast operation. | ||
− | ==Conclusion== | + | ==Conclusion - lines and line segments== |
The techniques of the two preceding chapters should provide inspiration on how to achieve | The techniques of the two preceding chapters should provide inspiration on how to achieve | ||
tasks that are "somewhere in-between". For example, we have not discussed the | tasks that are "somewhere in-between". For example, we have not discussed the | ||
Line 557: | Line 582: | ||
add these sections to this article; the exclusion of any material from the current draft | add these sections to this article; the exclusion of any material from the current draft | ||
is not an indication that such material does not belong in this article. | is not an indication that such material does not belong in this article. | ||
+ | |||
+ | =Angles= | ||
+ | |||
+ | ==Introduction to angles== | ||
+ | In trigonometry, one proves the Law of Cosines. In a purely algebraic approach to geometry, however the concept of angle is ''defined'' using the Law of Cosines, and the Law itself requires no proof. Still, we will not use that definition directly, because deriving everything from it would be unnecessarily complicated. Instead, we will assume that we already know some properties of angles. Storing angles in memory is very easy: just store the angle's radian measure. Why not degree measure? Degree measure is convenient for mental calculation, but radian measure is more mathematically convenient and, as such, trigonometric functions of most standard language libraries, such as those of Pascal and C/C++, expect their arguments in radians. (Inverse trigonometric functions return results in radians.) We will use radian measure throughout this chapter, without stating "radians", because radian measure is assumed when no units are given.<br/> | ||
+ | <br/> | ||
+ | Straightforward applications of basic trigonometry, such as finding the angles in a triangle whose vertices are known (Law of Cosines), are not discussed here. | ||
+ | |||
+ | ==Directed angle and the atan2 function== | ||
+ | Suppose a ray with its endpoint at the origin initially points along the | ||
+ | positive x-axis and is rotated counterclockwise around the origin by an angle | ||
+ | of <math> \theta </math>. From elementary trigonometry, the ray now consists of points | ||
+ | <math> \displaystyle (k \cos \theta,k \sin \theta) </math>, where <math> k > 0 </math>. This angle <math> \theta </math> | ||
+ | is a ''directed'' angle. Notice there is another ray with its endpoint at | ||
+ | the origin that makes an angle of <math> \theta </math> with the positive x-axis: | ||
+ | obtained by rotating clockwise rather than counterclockwise. But the directed | ||
+ | angle in this case would be <math> -\theta </math>. Thus, by specifying a directed angle | ||
+ | from the positive x-axis | ||
+ | we can uniquely specify one particular ray.<br/> | ||
+ | Can we reverse this process? Can we find the directed angle from the positive | ||
+ | x-axis to the ray <math> \overrightarrow{OP} </math>, where <math> P = (x,y) </math>? Notice that | ||
+ | when <math> x \neq 0 </math>, <math> \displaystyle y/x = \tan \theta </math>, so taking the inverse tangent | ||
+ | should give back <math> \theta </math>. There are just two problems with this: one is | ||
+ | that <math> x </math> might be zero (but the angle will still be defined, either <math>\pi/2</math> or <math>3\pi/2</math>), the other is that the point <math> (-x,-y) </math> will give | ||
+ | the same tangent even though it lies on the other side (and hence its directed | ||
+ | angle should differ from that of <math> \overrightarrow{OP} </math> by <math> \pi </math>. | ||
+ | However, because this is such a useful application, the Intel FPU has a | ||
+ | built-in instruction to compute the directed angle from the positive x-axis to | ||
+ | ray <math> \overrightarrow{OP} </math>, and the libraries of both C and Free Pascal | ||
+ | contain functions for this purpose. C's is called <code>atan2</code>, and it takes | ||
+ | two arguments, <math> y </math> and <math> x </math>, in that order, returning an angle in | ||
+ | radians, the desired directed angle, a real number <math>\theta</math> satisfying | ||
+ | <math> -\pi < \theta \leq \pi </math>. (Notice that as with undirected angles, adding | ||
+ | <math> 2\pi </math> to a directed angle leaves it unchanged). Remember that <math> y </math> | ||
+ | comes first and not <math> x </math>; the reason for this has to do with the design of | ||
+ | the Intel FPU and the calling convention of C. Free Pascal's math library aims | ||
+ | to largely emulate that of C, so it provides the <code>arctan2</code> function | ||
+ | which takes the same arguments and produces the same return value. | ||
+ | |||
+ | ==The angle between a line and the x-axis== | ||
+ | When two lines intersect, two pairs of angles are formed (the two angles in | ||
+ | each pair are equal). They are supplementary. To find one of these angles, let | ||
+ | us shift the line until it passes through the x-axis. Then, adding the | ||
+ | direction numbers <math> (-B,A) </math> to the origin gives another point. We now apply | ||
+ | the <code>atan2</code> function: <code>atan2</code>(<math> A,-B </math>). (Notice that we have | ||
+ | reversed the order of <math> x </math> and <math> y </math>, as required.) The result may be | ||
+ | negative; we can add <math> \pi </math> to it to make it non-negative. | ||
+ | |||
+ | ==The angle between two lines== | ||
+ | To find one of the two angles between two lines, we find the angle between each | ||
+ | line and the x-axis, then subtract. (Draw a diagram to convince yourself that | ||
+ | this works.) If the result is negative, add <math> \pi </math> degrees, once or | ||
+ | twice as necessary. The other angle is obtained by subtracting from <math> \pi </math>. | ||
+ | |||
+ | ==The angle bisector of a pair of intersecting lines== | ||
+ | Using the result of the previous section and a great deal of algebra and trigonometry, | ||
+ | together with the line intersection algorithm, gives the following algorithm for finding one of the | ||
+ | two angle bisectors of a pair of (intersecting) lines <math> l_1 </math> | ||
+ | <math> (A_1x+B_1y+C_1=0) </math> and <math> l_2 </math> <math> (A_2x+B_2y+C_2=0) </math> (the bisector | ||
+ | is represented as <math> A'x+B'y+C'=0 </math>): | ||
+ | :<math> | ||
+ | \begin{array}{rl} | ||
+ | 1. & h_1 \gets \sqrt{A_1^2+B_1^2} \\ | ||
+ | 2. & h_2 \gets \sqrt{A_2^2+B_2^2} \\ | ||
+ | 3. & A' \gets A_1 h_2 + A_2 h_1 \\ | ||
+ | 4. & B' \gets B_1 h_2 + B_2 h_1 \\ | ||
+ | 5. & (x,y) \gets \mathrm{\ intersection\ of\ } l_1 \mathrm{\ and\ } l_2 \\ | ||
+ | 6. & C' \gets -A'x-B'y | ||
+ | \end{array} | ||
+ | </math> | ||
+ | The other angle bisector, of course, is perpendicular to this line and also | ||
+ | passes through that intersection point. | ||
+ | |||
+ | =Vectors= | ||
+ | ==Introduction to vectors== | ||
+ | Although the word ''vector'' has a formal definition, we will not find it useful. It is better, in the context of computational geometry, to think of a vector as an idealized object which represents a given translation. Visually, a vector may be represented as an arrow with a fixed length pointing in a fixed direction, but without a fixed location. For example, on the Cartesian plane, consider the translation "3 units down and 4 units right". If you start at the point (8,10) and apply this translation, (12,7) is obtained. This can also be represented as an arrow with length 5 units and direction approximately 37 degrees south of east. Placing the tail of this arrow at (8,10) results in the head resting upon the point (12,7). The vector from (0,0) to (4,-3) is the same vector, as it also represents a translation 3 units down and 4 units right, and has the same length and direction. However, the vector from (12,7) to (8,10) and the vector from (0,0) to (-3,4) are different from the one from (8,10) to (12,7); they have the same lengths, but their directions are different, and so they are different vectors. The vector from (0,0) to (8,-6) is also different; it has the same direction, but a different length. In both cases, these are simply different translations, and hence different vectors. The word ''vector'' is from the Latin, meaning ''carrier'', appropriate as it ''carries'' from one location (a point) to another. | ||
+ | |||
+ | ==Representation== | ||
+ | We could represent a vector by its magnitude and direction, but it is usually not convenient to do so. Even still, it might be useful occasionally to find the magnitude and direction of a vector; refer to the sections on [[#Length of a line segment|length of a line segment]] and [[#Directed angle and the atan2 function|directed angle and the atan2 function]] for the necessary mathematics. Instead, we will use the Cartesian representation. If we place the tail of a vector on the origin, the head rests upon a certain point; the Cartesian ''coordinates'' of this point are the Cartesian ''components'' of the vector. We thus represent a vector as we do a point, as an ordered pair of real numbers, but we shall enclose these in brackets instead of parentheses. The vector discussed above is then [4,-3], as when the tail is placed on (0,0), the head rests upon (4,-3). Two vectors are equal when both of their corresponding components are equal. | ||
+ | |||
+ | ==Standard vector notation== | ||
+ | In writing, vectors are represented as letters with small rightward-pointing arrows over them, ''e.g.'', <math>\vec{v}</math>. Vectors are usually ''typeset'' in bold, ''e.g.'', <math>\mathbf{v}</math>. We shall denote the components of <math>\mathbf{v}</math> as <math>v_x</math> and <math>v_y</math>. The magnitude of <math>\mathbf{v}</math> may be denoted simply <math>v</math>, or, to avoid confusion with an unrelated scalar variable, <math>\|\mathbf{v}\|</math>. There is a special vector known as the ''zero vector'', the identity translation; it leaves one's position unchanged and has the Cartesian representation [0,0]. We shall represent it as <math>\mathbf{0}</math>. | ||
+ | |||
+ | ==Basic operations== | ||
+ | The order of operations is the same with vectors as with real numbers. | ||
+ | ===Addition=== | ||
+ | Addition of vectors shares many properties with addition of real numbers. It is represented by the plus sign, and is associative and commutative. | ||
+ | ====Of a vector to a point==== | ||
+ | ''Adding'' a vector to a point is another name for the operation in which a point is simply translated by a given vector. It is not hard to see that <math>(x,y) + [u,v] = (x+u,y+v)</math>. We could also write the same sum as <math>[u,v] + (x,y)</math>, since addition is supposed to be commutative. As one can easily see, adding a point and a vector results in another point. The zero vector is the additive identity; adding it to any point leaves the point unchanged. Geometrically, adding a point and a vector entails placing the vector's tail at the point; the vector's head then rests upon the sum. | ||
+ | ====Of two vectors==== | ||
+ | If we want addition to be associative too, then the sum <math>(P+\mathbf{u})+\mathbf{v}</math> must be the same point as <math>P+(\mathbf{u}+\mathbf{v})</math>. The first sum represents the point arrived at when the translations representing <math>\mathbf{u}</math> and <math>\mathbf{v}</math> are taken in succession. Therefore, in the second sum, we should define <math>\mathbf{u}+\mathbf{v}</math> in such a way so that it gives a vector representing the translation obtained by taking those of <math>\mathbf{u}</math> and <math>\mathbf{v}</math> in succession. It is not too hard to see that <math>[u_x,u_y] + [v_x,v_y] = [u_x+v_x,u_y+v_y]</math>. Geometrically, if the tail of <math>\mathbf{v}</math> is placed at the head of <math>\mathbf{u}</math>, the arrow drawn from the tail of <math>\mathbf{u}</math> to the head of <math>\mathbf{v}</math> is the sum. Again, the zero vector is the additive identity. | ||
+ | ===Negation=== | ||
+ | For every vector <math>\mathbf{v}</math> we can identify a corresponding vector, denoted <math>-\mathbf{v}</math>, such that the translations represented by <math>\mathbf{v}</math> and <math>-\mathbf{v}</math> are inverse transformations. Another way of stating this is that <math>\mathbf{v}+(-\mathbf{v}) = \mathbf{0}</math>, or that <math>\mathbf{v}</math> and <math>-\mathbf{v}</math> have the same length but opposite directions. If <math>\mathbf{v} = [v_x,v_y]</math>, then <math>-\mathbf{v} = [-v_x,-v_y]</math>. | ||
+ | ===Subtraction=== | ||
+ | ====Of a vector from a point==== | ||
+ | We define subtraction to be the inverse operation of addition. That is, for any point <math>P</math> and vector <math>\mathbf{v}</math>, we should have that <math>P+\mathbf{v}-\mathbf{v} = P-\mathbf{v}+\mathbf{v} = P</math>. Since the vector <math>-\mathbf{v}</math> represents the inverse translation to <math>\mathbf{v}</math>, we can simply '''add''' <math>-\mathbf{v}</math> to <math>P</math> to obtain <math>P-\mathbf{v}</math>. (Note that the expression <math>\mathbf{v}-P</math> is not meaningful.) Geometrically, this is equivalent to placing the head of the arrow at <math>P</math> and then following the arrow backward to the tail. Subtracting the zero vector leaves a point unchanged. | ||
+ | ====Of a vector from a vector==== | ||
+ | To subtract one vector from another, we add its negative. Again, we find that this definition leads to subtraction being the inverse operation of addition. It is not too hard to see that <math>[u_x,u_y] - [v_x,v_y] = [u_x-v_x,u_y-v_y]</math>. Geometrically, if the vectors <math>\mathbf{u}</math> and <math>\mathbf{v}</math> are placed tail-to-tail, then the vector from the head of <math>\mathbf{u}</math> to the head of <math>\mathbf{v}</math> is <math>\mathbf{v}-\mathbf{u}</math>, and ''vice versa''. Note that <math>\mathbf{u}-\mathbf{v} = -(\mathbf{v}-\mathbf{u})</math>. | ||
+ | ====Of a point from a point==== | ||
+ | A vector can be considered the difference between two points, or the translation required to take one point onto the other. Given the two points <math>P\ (P_x,P_y)</math> and <math>Q\ (Q_x,Q_y)</math>, the vector from <math>P</math> to <math>Q</math> is <math>[Q_x-P_x,Q_y-P_y]</math>, and ''vice versa''. Note that <math>P-Q = -(Q-P)</math>. | ||
+ | ===Multiplication=== | ||
+ | A vector can be ''scaled'' by a scalar (real number). This operation is known as ''scalar multiplication''. The product <math>\alpha[v_x,v_y]</math> denotes the vector <math>[\alpha v_x,\alpha v_y]</math>. This could also be notated <math>[v_x,v_y]\alpha</math>, though placing the scalar after the vector is more rare. Scalar multiplication takes precedence over addition and subtraction. The geometric interpretation is a bit tricky. If <math>\alpha > 0</math>, then the direction of the vector is left unchanged and the length is scaled by the factor <math>\alpha</math>. If <math>\alpha = 0</math>, then the result is the zero vector; and if <math>\alpha < 0</math>, then the vector is scaled by the factor <math>|\alpha|</math> and its direction is reversed. The scalar 1 is the multiplicative identity. Multiplying by the scalar -1 yields the negative of the original vector. Scalar multiplication is distributive. | ||
+ | |||
+ | The zero vector is a scalar multiple of any other vector. However, if two non-zero vectors are multiples of each other, then either they are ''parallel'', that is, in the same direction (<math>\alpha > 0</math>), or they are ''antiparallel'', that is, in opposite directions (<math>\alpha < 0</math>). | ||
+ | ===Division=== | ||
+ | A vector can be divided by a scalar <math>\alpha</math> by multiplying it by <math>\alpha^{-1}</math>. This is notated in the same way as division with real numbers. Hence, <math>\frac{[x,y]}{\alpha} = \left[\frac{x}{\alpha},\frac{y}{\alpha}\right]</math>. Division by 0 is illegal. | ||
+ | ==The unit vector== | ||
+ | To every vector except <math>\mathbf{v}</math> (except <math>\mathbf{v} = \mathbf{0}</math>), we can assign a vector <math>\hat{\mathbf{v}}</math> that has the same direction but a length of exactly 1. This is called a ''unit vector''. The unit vector can be calculated as follows: | ||
+ | :<math>\hat{\mathbf{v}} = \frac{\mathbf{v}}{\|\mathbf{v}\|}</math> | ||
+ | There are two ''elementary unit vectors'': [1,0], denoted <math>\hat{\boldsymbol{\imath}}</math>, and [0,1], denoted <math>\hat{\boldsymbol{\jmath}}</math>. That is, the unit vectors pointing along the positive x- and y-axes. Note that we can write a vector <math>\mathbf{v}</math> as <math>v_x\hat{\boldsymbol{\imath}} + v_y\hat{\boldsymbol{\jmath}}</math>. | ||
+ | |||
+ | ==Obtaining a vector of a given length in the same direction as a given vector== | ||
+ | Suppose we want a vector of length <math>l</math> pointing in the same direction as <math>\mathbf{v}</math>. Then, all we need to do is scale <math>\mathbf{v}</math> by the factor <math>\frac{l}{\|\mathbf{v}\|}</math>. Thus our new vector is | ||
+ | <math>\frac{l}{\|\mathbf{v}\|}\mathbf{v}</math>, which can also be written <math>l\frac{\mathbf{v}}{\|\mathbf{v}\|}</math> = <math>l\hat{\mathbf{v}}</math>. Hence the unit vector is a "prototype" for vectors of a given direction. | ||
+ | ==Rotation== | ||
+ | Given a vector <math>\mathbf{v}\ [x,y]</math> and an angle <math>\theta</math>, we can rotate <math>\mathbf{v}</math> counterclockwise through the angle <math>\theta</math> to obtain a new vector <math>[x',y']</math> using the following formulae: | ||
+ | :<math>x' = x\cos\theta - y\sin\theta</math> | ||
+ | :<math>y' = x\sin\theta + y\cos\theta</math> | ||
+ | The same formula can be used to rotate points, when they are considered as the endpoints of vectors with their tails at the origin. | ||
+ | ==Dot product== | ||
+ | The ''dot product'' or ''scalar product'' is notated and defined as follows: | ||
+ | :<math>[a_x,a_y]\cdot[b_x,b_y] = a_x b_x + a_y b_y</math> | ||
+ | It is commutative, but not associative (since expressions like <math>\mathbf{a}\cdot\mathbf{b}\cdot\mathbf{c}</math> are meaningless). However, the dot product does associate with scalar multiplication; that is, <math>\alpha(\mathbf{a}\cdot\mathbf{b}) = (\alpha\mathbf{a})\cdot\mathbf{b}</math>. It is distributive over addition, so that <math>\mathbf{a}\cdot(\mathbf{b}+\mathbf{c}) = \mathbf{a}\cdot\mathbf{b} + \mathbf{a}\cdot\mathbf{c}</math>. (This is actually left-distributivity, but right-distributivity follows from the commutative property.) These properties can easily be proven using the Cartesian components. The dot product has two useful properties. | ||
+ | |||
+ | First, the dot product satisfies the relation | ||
+ | :<math>\mathbf{a}\cdot\mathbf{b} = \|\mathbf{a}\| \|\mathbf{b}\| \cos\theta</math> | ||
+ | where <math>\theta</math> is the angle between <math>\mathbf{a}</math> and <math>\mathbf{b}</math>. This allows us to find '''the angle between two vectors''' as follows: | ||
+ | :<math>\theta = \cos^{-1}\frac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{a}\|\|\mathbf{b}\|}</math> | ||
+ | This formula breaks down if one of the vectors is the zero vector (in which case no meaningful angle can be defined anyway). The dot product gives a quick test for perpendicularity: two nonzero vectors are perpendicular if and only if their dot product is zero. The dot product is maximal when the two vectors are parallel, and minimal (maximally negative) when the two vectors are antiparallel. | ||
+ | |||
+ | Second, the dot product can be used to compute ''projections''. | ||
+ | ===The vector projection=== | ||
+ | The vector projection of <math>\mathbf{a}</math> onto <math>\mathbf{b}</math> is, intuitively, the "shadow" cast by <math>\mathbf{a}</math> onto <math>\mathbf{b}</math> by a light source delivering rays perpendicular to <math>\mathbf{b}</math>. We imagine <math>\mathbf{b}</math> to be a screen and <math>\mathbf{a}</math> to be an arrow; we are ''projecting'' the arrow onto the screen. (It is okay for parts of the projection to lie outside the "screen".) Geometrically, the tail of the projection of <math>\mathbf{a}</math> onto <math>\mathbf{b}</math> is the foot of the perpendicular from the tail of <math>\mathbf{a}</math> to <math>\mathbf{b}</math>, and the head of the projection is likewise the foot of the perpendicular from the head of <math>\mathbf{a}</math>. The vector projection is a vector pointing in the same direction as <math>\mathbf{b}</math>. There is no standard notation for vector projection; one notation is <math>\operatorname{proj}_\mathbf{b}\,\mathbf{a}</math> for the projection of <math>\mathbf{a}</math> onto <math>\mathbf{b}</math>, and ''vice versa''. | ||
+ | ===The scalar projection=== | ||
+ | The scalar projection is the directed length of the vector projection. That is, if the angle between <math>\mathbf{a}</math> and <math>\mathbf{b}</math> is acute, then <math>\operatorname{proj}_\mathbf{b}\,\mathbf{a}</math> points in the same direction as <math>\mathbf{b}</math>, and it has a positive directed length; here the scalar projection simply equals the length of the vector projection. If that angle is obtuse, on the other hand, then <math>\operatorname{proj}_\mathbf{b}\,\mathbf{a}</math> and <math>\mathbf{b}</math> point in opposite directions, and the scalar projection is the negative of the length of the vector projection. (If the two vectors are perpendicular, the scalar projection is zero.) There is also no standard notation for the scalar projection; one possibility is <math>|\operatorname{proj}_\mathbf{b}\,\mathbf{a}|</math>. (Note the single vertical bars, instead of the double vertical bars that denote length.) You have already encountered scalar projections: in the unit circle, the sine of an angle is the scalar projection of a ray making that directed angle with the positive x-axis onto the y-axis, and likewise the cosine is a scalar projection onto the x-axis. | ||
+ | ===Computing projections=== | ||
+ | Why have we left discussion of the computation of the scalar and vector projections out of their respective sections? The answer is that the scalar projection is easier to compute, but harder to explain. Place the vectors <math>\mathbf{a}</math> and <math>\mathbf{b}</math> tail-to-tail at the origin. Now rotate both vectors so that <math>\mathbf{b}</math> points to the right. (Rotation actually changes the vectors, of course, but does not change the scalar projection.) Now, the cosine of the angle <math>\theta</math> between <math>\mathbf{a}</math> and <math>\mathbf{b}</math> is the scalar projection of <math>\hat{\mathbf{a}}</math> onto <math>\mathbf{b}</math>, from the definition of the cosine function. By similar triangles, <math>|\operatorname{proj}_\mathbf{b}\,\mathbf{a}|</math> is <math>\|\mathbf{a}\|</math> times this. Therefore we find: | ||
+ | :<math>|\operatorname{proj}_\mathbf{b}\,\mathbf{a}| = \|\mathbf{a}\| \cos \theta = \|\mathbf{a}\| \frac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{a}\|\|\mathbf{b}\|} = \frac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{b}\|}</math> | ||
+ | and ''vice versa''. We could also write this as | ||
+ | :<math>|\operatorname{proj}_\mathbf{b}\,\mathbf{a}| = \mathbf{a}\cdot\hat{\mathbf{b}}</math> | ||
+ | because the dot product associates with scalar multiplication. | ||
+ | To compute a vector projection, we notice that we need a vector with the directed length <math>|\operatorname{proj}_\mathbf{b}\,\mathbf{a}|</math> along <math>\mathbf{b}</math>. This is accomplished by scaling the unit vector <math>\hat{\mathbf{b}}</math> by the value of the scalar projection: | ||
+ | :<math>\operatorname{proj}_\mathbf{b}\,\mathbf{a} = \frac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{b}\|}\hat{\mathbf{b}}</math> | ||
+ | We could also write this as | ||
+ | :<math>\operatorname{proj}_\mathbf{b}\,\mathbf{a} = (\mathbf{a}\cdot\hat{\mathbf{b}})\hat{\mathbf{b}}</math> | ||
+ | Two notes: first, projecting onto the zero vector is meaningless since it has no direction, and second, neither scalar nor vector projection is commutative. | ||
+ | ==Determinant== | ||
+ | The ''determinant'' of two vectors <math>\mathbf{a}</math> and <math>\mathbf{b}</math>, denoted <math>\det(\mathbf{a},\mathbf{b})</math>, is the determinant of the matrix having <math>\mathbf{a}</math> and <math>\mathbf{b}</math> as rows (or, equivalently, columns), that is: | ||
+ | :<math>\left[\begin{matrix} a_x & a_y \\ b_x & b_y \end{matrix}\right]</math> | ||
+ | and is therefore equal to <math>a_x b_y - a_y b_x</math>. | ||
+ | The size-2 determinant is often mistakenly referred to as the ''cross product''. (This usage is nearly universal in casual programming parlance and less reputable websites.) This is because there exists a product of two three-dimensional vectors known as the cross product, and the cross-product of two vectors lying in the xy-plane is a vector pointing along the z-axis with z-component equal to the determinant of the two plane vectors. However, no background with three-dimensional vectors, cross-products, or matrices is required for this section. In two dimensions, all that is needed is the formula: <math>\det(\mathbf{a},\mathbf{b}) = a_x b_y - a_y b_x</math>. However, for the sake of convenience, we shall denote the size-2 determinant by the same symbol as the cross product, the cross: hence <math>\mathbf{a}\times\mathbf{b} = a_x b_y - a_y b_x</math>. (This also avoids confusion with the larger matrices in advanced linear algebra and higher dimensions.) It is anticommutative, meaning that <math>\mathbf{a} \times \mathbf{b} = -(\mathbf{b} \times \mathbf{a})</math>. It satisfies the properties <math>\alpha(\mathbf{a}\times\mathbf{b}) = (\alpha\mathbf{a}) \times \mathbf{b} = \mathbf{a} \times (\alpha \mathbf{b})</math>, and with addition it is both left-distributive, so that <math>\mathbf{a} \times (\mathbf{b}+\mathbf{c}) = \mathbf{a} \times \mathbf{b} + \mathbf{a} \times \mathbf{c}</math>, and right-distributive, so that <math>(\mathbf{a}+\mathbf{b})\times\mathbf{c} = \mathbf{a} \times \mathbf{c} + \mathbf{b} \times \mathbf{c}</math>. There are two primary uses for the size-2 determinant in two-dimensional computational geometry. | ||
+ | |||
+ | The determinant is useful in several algorithms for computing the [[convex hull]] because it allows us to determine the ''directed angle'' from one vector to another. (Note that the dot product allows us to determine the undirected angle; it makes sense because the dot product commutes whereas the size-2 determinant anticommutes.) The following relation holds: | ||
+ | :<math>\mathbf{a} \times \mathbf{b} = \|\mathbf{a}\| \|\mathbf{b}\| \sin \theta</math> | ||
+ | where <math>\theta</math> is the ''directed'' angle from <math>\mathbf{a}</math> to <math>\mathbf{b}</math>. That is, the counterclockwise angle from <math>\mathbf{a}</math> to <math>\mathbf{b}</math> when they are both anchored at the same point. Rearranging allows us to compute the angle directly: | ||
+ | :<math>\theta = \sin^{-1} \frac{\mathbf{a} \times \mathbf{b}}{\|\mathbf{a}\| \|\mathbf{b}\|}</math> | ||
+ | (Note that the sine function is odd, so that when <math>\mathbf{a}</math> and <math>\mathbf{b}</math> are interchanged in the above, the right side is negated, and so is the left.) | ||
+ | Often, however, we do not need the directed angle itself. In the [[Convex hull#Monotone chains algorithm|monotone chains algorithm]] for convex hull computation, for example, all we need to know is whether there is a clockwise or a counterclockwise turn from <math>\mathbf{a}</math> to <math>\mathbf{b}</math>. (That is, if one wishes to rotate <math>\mathbf{a}</math> through no more than 180 degrees either clockwise or counterclockwise so that its direction coincides with that of <math>\mathbf{b}</math>, which direction should one choose?) It turns out that if <math>\mathbf{a} \times \mathbf{b}</math> is positive, the answer is counterclockwise; if it is negative, clockwise, and if it is zero, the vectors are either parallel or antiparallel. (Indeed, the closer <math>\theta</math> is to a right angle, the larger the cross product in magnitude; in some sense then it measures "how far away" the vectors are from each other.) | ||
+ | |||
+ | The determinant is also useful in computing areas of parallelograms and triangles. If the two vectors <math>\mathbf{a}</math> and <math>\mathbf{b}</math> are placed tail-to-tail, a parallelogram can be formed using these vectors as adjacent sides; its area is <math>|\mathbf{a}\times\mathbf{b}|</math>. A triangle can also be formed using these vectors as adjacent sides; its area is half that of the parallelogram, or <math>\frac{1}{2}|\mathbf{a}\times\mathbf{b}|</math>. (This echoes the formula <math>A = \frac{1}{2}ab\sin\theta</math> taught in high-school math classes.) In fact, the area of a general quadrilateral <math>ABCD</math> can be computed with a determinant as well; it equals <math>\frac{1}{2}|(C-A)\times(D-B)|</math>. | ||
+ | |||
+ | =Circles= | ||
+ | |||
+ | ==Introduction to circles== | ||
+ | A circle is ''the locus of points in the plane equidistant from a given point''. That is, we choose some point <math> O </math>, the ''centre'', and some distance <math> r > 0 </math>, the ''radius'', and the circle consists exactly of those points whose Euclidean distance from <math> O </math> is exactly <math> r </math>. When storing a circle in memory, we store merely the centre and the radius. | ||
+ | |||
+ | ==Equation of a circle== | ||
+ | Suppose the circle has centre <math> O (h,k) </math> and radius <math>r</math>. Then, from the definition, we know that any point <math>(x,y)</math> on the circle must satisfy <math>\operatorname{dist}((x,y),(h,k)) = r</math>. This means <math>\sqrt{(x-h)^2+(y-k)^2} = r</math>, or <math>(x-h)^2+(y-k)^2 = r^2</math>. | ||
+ | |||
+ | ==Inside, outside, or on the circle== | ||
+ | The equation of a circle is a sufficient and necessary condition for a point to be on the circle. If it is not on the circle, it must be either inside the circle or outside the circle. It will be inside the circle when its distance from the centre is less than <math>r</math>, or <math>(x-h)^2+(y-k)^2 < r^2</math>, and similarly it will be outside the circle when <math>(x-h)^2+(y-k)^2 > r^2</math>. | ||
+ | |||
+ | ==Intersection of a circle with a line== | ||
+ | To determine points of intersection of a circle with another figure (it might also be a circle), solve the simultaneous equations obtained in <math>x</math> and <math>y</math>. For example, given a circle centered at (2,3) with radius 2, and the line <math>x+y-4=0</math>, we would solve the simultaneous equations <math>(x-2)^2+(y-3)^2 = 2^2</math> and <math>x+y-4=0</math>. If there are multiple solutions, each is a different point of intersection; if there are no solutions then the two figures do not intersect. Here then are general results. Note that if you do not check the "no intersection" condition beforehand and plunge straight into the quadratic formula (after reducing the two simultaneous equations to one equation), you will try to extract the square root of a negative number, which will crash some languages (such as Pascal). | ||
+ | |||
+ | ===No points of intersection=== | ||
+ | When the closest distance from the centre of the circle to the line is greater than the radius of the circle, the circle and line do not intersect. (The formula for the distance from a point to a line can be found in the Lines section of this article.) | ||
+ | |||
+ | ===One point of intersection=== | ||
+ | When the closest distance from the centre of the circle to the line is exactly the circle's radius, the line is tangent to the circle. One way of finding this point of tangency, the single point of intersection, is to drop a perpendicular from the centre of the circle to the line. (The technique for doing so is found in the Lines section.) This will, of course, yield the same answer as solving the simultaneous equations. | ||
+ | |||
+ | ===Two points of intersection=== | ||
+ | When the closest distance from the centre of the circle to the line is less than the circle's radius, the line intersects the circle twice. | ||
+ | |||
+ | To find the two points of intersection, first drop a perpendicular from the centre of the circle to the line. Call the foot of the perpendicular <math>P</math> and denote the distance <math>|OP|</math> by <math>d</math>. Now, let the two points of intersection be <math>Q_1</math> and <math>Q_2</math>. Then, the triangles <math>\triangle OPQ_1</math> and <math>\triangle OPQ_2</math> are right-angled, and hence we see that <math>|OP|^2 + |Q_1P|^2 = |OQ_1|^2 = r^2</math> and <math>|OP|^2 + |Q_2P|^2 = |OQ_2|^2 = r^2</math>. So we compute the value <math>h = \sqrt{r^2 - |OP|^2}</math>; now, if we move <math>h</math> units in either direction along the line from <math>P</math>, we will reach either <math>Q_1</math> or <math>Q_2</math>. (The technique to do so is given in section [[#Translation along a line|Translation along a line]].) | ||
+ | |||
+ | ==Intersection of a circle with a circle== | ||
+ | Finding the points of intersection of two circles follows the same basic idea as the circle-line intersection. Here's how to determine the nature of the intersection beforehand, to avoid accidentally trying to take the square root of a negative number: | ||
+ | |||
+ | ===No points of intersection=== | ||
+ | When the distance between the centres of the circles is less than the difference between their radii, the circle with smaller radius will be contained completely within the circle of larger radius. When the distance between the centres of the circles is greater than the sum of their radii, neither circle will be inside the other, but still the two will not intersect. | ||
+ | |||
+ | ===One point of intersection=== | ||
+ | Let the two circles have centres <math>O_1</math> and <math>O_2</math> and radii <math>r_1</math> and <math>r_2</math>. | ||
+ | * When the distance between the centres of the circles is exactly the difference between their radii, the two circles will be internally tangent. Suppose that the first circle is larger. Then the point of intersection lies on the line between <math>O_1</math> and <math>O_2</math>. The intersection point and <math>O_1</math> are on opposite sides of <math>O_2</math>, and its distances from <math>O_1</math> and <math>O_2</math> are <math>r_1</math> and <math>r_2</math>, respectively. This gives <math>P = \frac{O_2 r_1 - O_1 r_2}{r_1 - r_2}</math>. (It turns out that if we swap the 1's and 2's in this formula, we get the same value; hence we can use this formula without regard to which circle is labelled 1 and which one is 2.) | ||
+ | * When the distance between the centres of the circles is exactly the sum of their radii, they will be externally tangent; they will have one point of intersection located between <math>O_1</math> and <math>O_2</math>; it will be <math>r_1</math> units away from the former and <math>r_2</math> units away from the latter, giving the formula <math>P = \frac{O_2 r_1 + O_1 r_2}{r_1 + r_2}</math>. | ||
+ | |||
+ | ===Two points of intersection=== | ||
+ | In all other cases, there will be two points of intersection. | ||
+ | |||
+ | To find them, it will be helpful to draw a diagram. Denote the centres of the circles <math>O_1, O_2</math>, their radii <math>r_1, r_2</math>, and the two points of intersection <math>P_1, P_2</math>. First draw the ''radical axis'', the line that passes through <math>P_1</math> and <math>P_2</math>. This passes through the midpoint <math>M</math> between <math>P_1</math> and <math>P_2</math>, and here it intersects perpendicularly the line between <math>O_1</math> and <math>O_2</math>. Denote <math>|O_1M|</math> and <math>|O_2M|</math> by <math>d_1, d_2</math>, respectively. Clearly | ||
+ | :<math>d_1 + d_2 = |O_1O_2|</math>. (1) | ||
+ | Also, from the Pythagorean theorem, <math>|MP_1|^2 = |O_1P_1|^2 - |O_1M|^2 = |O_2P_1|^2 - |O_2M|^2</math>, or <math>r_1^2 - d_1^2 = r_2^2 - d_2^2</math>. Rearranging this gives | ||
+ | :<math>d_1^2 - d_2^2 = r_1^2 - r_2^2</math>. (2) | ||
+ | |||
+ | Now we solve for <math>d_1</math> and <math>d_2</math>. To do this, we factor the left side of (2), giving <math>(d_1 - d_2)(d_1 + d_2) = r_1^2 - r_2^2</math>, which allows us to divide through by (1), thus obtaining | ||
+ | :<math>d_1 - d_2 = \frac{r_1^2 - r_2^2}{|O_1O_2|}</math>. (3) | ||
+ | Equations (1) and (3) are linear and may be used to solve for <math>d_1, d_2</math> in a straightforward fashion. | ||
+ | |||
+ | Now we can compute the coordinates of <math>M</math> as <math>M = \frac{O_2 d_1 + O_1 d_2}{d_1 + d_2}</math>, using the argument from the previous section. Then construct the line perpendicular to <math>O_1O_2</math> that passes through <math>M</math> (the radical axis). Finally, we can find the distance <math>|MP_1| = |MP_2| = \sqrt{r_1^2 - d_1^2} = \sqrt{r_2^2 - d_2^2}</math>, and move this distance in either direction along the radical axis (see [[#Translation along a line|Translation along a line]]) to obtain <math>P_1</math> and <math>P_2</math>. | ||
+ | |||
+ | It should be noted that two circles that intersect at two points cut each other into two arcs each: one arc that lies within the other circle, and one that lies outside it. It is not immediately obvious which is which. However, you should be able to convince yourself from drawing a diagram that if <math>(P_1-O_1) \times (O_2-O_1) > 0</math>, then the arc of the first circle that is inside the second circle is counterclockwise from <math>P_1</math> to <math>P_2</math>, but if that determinant is negative, then the inside arc is counterclockwise from <math>P_2</math> to <math>P_1</math>. (For an example of where this is important, see {{Problem|detectors|Detectors}}.) | ||
+ | |||
+ | ==Tangents== | ||
+ | A line is said to be ''tangent'' to a circle if it intersects the circle at exactly one point. | ||
+ | |||
+ | The tangent has an important property: if a circle with centre <math>O</math> has a tangent line <math>l</math> that touches it at <math>P</math>, then <math>l \perp OP</math>. The proof of this fact is simple: we assume that the two lines are not perpendicular, then drop a perpendicular from <math>O</math> to <math>l</math> at <math>Q</math>. We observe that <math>\triangle OPQ</math> is right-angled at <math>Q</math>, and that therefore <math>|OP| > |OQ|</math>. But this implies that <math>Q</math> is inside the circle, a contradiction. | ||
+ | |||
+ | To actually find the tangent line to one circle at a given point on its circumference is easy; it is simply the line passing through that point that is perpendicular to the radius. | ||
+ | |||
+ | ===From point to circle=== | ||
+ | Sometimes we may also be given a circle with centre and radius <math>(O, r)</math> plus a point <math>P</math> and asked to find a tangent to the circle that passes through the point. There may be either zero, one, or two such tangents. | ||
+ | |||
+ | ====Point is inside circle==== | ||
+ | When the point is inside the circle, there are no tangents to the circle through that point, because any line through the point must intersect the circle twice. | ||
+ | |||
+ | ====Point is on circle==== | ||
+ | When the point is on the circumference of the circle, the line passing through <math>P</math> that is perpendicular to <math>OP</math> is the unique tangent to the circle passing through that point. | ||
+ | |||
+ | ====Point is outside circle==== | ||
+ | When the point is outside the circle, there are two tangents to the circle passing through the point. To construct one such tangent, we use a trick called ''inversion''. We let one of the points of tangency be denoted <math>Q</math>. Now <math>\triangle OQP</math> is right-angled at <math>Q</math>. If we now drop a perpendicular from <math>Q</math> to <math>OP</math> at <math>R</math>, we obtain triangle <math>\triangle OQR</math> which is similar to <math>\triangle OPQ</math>. This means that <math>\frac{|OP|}{|OQ|} = \frac{|OQ|}{|OR|}</math>, so <math>|OR| = \frac{r^2}{|OP|}</math>. Note that <math>R</math> is ''inside'' the circle, unlike <math>P</math> which is ''outside'' (hence the name ''inversion''.) This allows us to locate point <math>R</math> on the line segment <math>OP</math>. Then, we see that the line segment <math>RQ</math> is perpendicular to <math>OP</math> and has length <math>\sqrt{r^2 - |OR|^2}</math> from the Pythagorean theorem in <math>\triangle OQR</math>. This gives us enough information to compute the coordinates of <math>Q</math>. There will be two possibilities, since we can draw two rays through <math>R</math> that are perpendicular to <math>OP</math>. | ||
+ | |||
+ | ===Circle-circle tangents=== | ||
+ | A pair of circles may have either zero, one, two, three, or four mutual tangents. | ||
+ | |||
+ | ====Zero mutual tangents==== | ||
+ | If one circle lies within the other (that is, the difference between their radii is greater than the distance between their centres), then they have no mutual tangents, since every tangent to the outer circle lies outside it, and hence cannot touch the inner circle. | ||
+ | |||
+ | ====One mutual tangent==== | ||
+ | Two circles will have one mutual tangent if they are internally tangent (that is, the difference between their radii equals the distance between their centres). This tangent can easily be found after constructing the point <math>P</math> of internal tangency (see section [[#One point of intersection|One point of intersection]] above). | ||
+ | |||
+ | ====Two mutual tangents==== | ||
+ | A pair of circles that intersect at two points has two mutual tangents, one on either "side". We will consider the problem of how to determine one of them. | ||
+ | |||
+ | Assume the circles have centres <math>O_1, O_2</math> and radii <math>r_1, r_2</math>. Assume further that they have some mutual tangent <math>l</math> and that <math>l</math> is tangent to the circles at <math>P_1, P_2</math>, respectively. We see that <math>O_1P_1 \perp l</math> and <math>O_2P_2 \perp l</math>. Now, assume without loss of generality that <math>r_2 \geq r_1</math>. Then drop the perpendicular from <math>O_1</math> to <math>O_2P_2</math> at <math>Q</math>, and obtain <math>|O_2Q| = r_2 - r_1</math>. Then <math>\theta = \angle O_1O_2Q = \cos^{-1} \frac{r_2-r_1}{|O_1O_2|}</math>. Also, we can solve for <math>h = |O_1Q|</math> using the Pythagorean theorem, obtaining <math>h = \sqrt{|O_1O_2|^2 - (r_2-r_1)^2}</math>. Notice that because <math>O_1QP_2P_1</math> is a rectangle, <math>h = |P_1P_2|</math>. | ||
+ | |||
+ | There are two possibilities for the location of <math>P_2</math>. One of them is obtained by rotating the ray <math>O_1 - O_2</math> clockwise through angle <math>\theta</math>, the other obtained by rotating it counterclockwise, and in either case determining where the ray cuts the second circle. (So it doesn't actually matter which circle is bigger; the formula <math>\cos^{-1} \frac{r_2-r_1}{|O_1O_2|}</math> will give the same result up to sign.) | ||
+ | |||
+ | We can then argue that the coordinates of one of the possible <math>P_2</math>'s is given by <math>O_2 + r_2 [\cos (\operatorname{atan2}(O_1-O_2) + \theta), \sin (\operatorname{atan2}(O_1-O_2) + \theta)]</math>, because <math>\operatorname{atan2}(O_1-O_2)</math> represents the directed angle from the positive x-axis to the ray from <math>O_2</math> to <math>O_1</math>, and we are adding onto this directed angle the value <math>\theta</math> to get our final position. The other possible <math>P_2</math> will be given by subtracting <math>\theta</math> instead of adding. | ||
+ | |||
+ | This formula as written is slow, since it involves trigonometric functions, which have a higher [[invisible constant factor]] than algebraic operations and square roots. Therefore, we will rewrite it in terms of only algebraic operations. Define <math>\Delta x = O_{1_x} - O_{2_x}</math> and <math>\Delta y</math> analogously. | ||
+ | |||
+ | Verify the identities <math>\cos \operatorname{atan2} \frac{y}{x} = \frac{x}{x^2 + y^2}</math> and <math>\sin \operatorname{atan2} \frac{y}{x} = \frac{y}{x^2 + y^2}</math>. (These are actually obvious from the definition of <code>atan2</code>). Then: | ||
+ | :<math>\cos( \operatorname{atan2}(O_1 - O_2) + \theta)</math> | ||
+ | :<math> = \cos \operatorname{atan2}(O_1 - O_2) \cos \theta - \sin \operatorname{atan2}(O_1 - O_2) \sin \theta</math> | ||
+ | :<math> = \frac{\Delta x}{\Delta x^2 + \Delta y^2} \frac{r_2-r_1}{|O_1O_2|} - \frac{\Delta y}{\Delta x^2 + \Delta y^2} \frac{h}{|O_1O_2|}</math> | ||
+ | :<math> = \frac{(r_2-r_1)\Delta x - h\Delta y}{|O_1O_2|^2}</math> | ||
+ | And likewise | ||
+ | :<math>\sin( \operatorname{atan2}(O_1 - O_2) + \theta)</math> | ||
+ | :<math> = \sin \operatorname{atan2}(O_1 - O_2) \cos \theta + \cos \operatorname{atan2}(O_1 - O_2) \sin \theta</math> | ||
+ | :<math> = \frac{\Delta y}{\Delta x^2 + \Delta y^2} \frac{r_2-r_1}{|O_1O_2|} + \frac{\Delta x}{\Delta x^2 + \Delta y^2} \frac{h}{|O_1O_2|}</math> | ||
+ | :<math> = \frac{h\Delta x + (r_2-r_1)\Delta y}{|O_1O_2|^2}</math> | ||
+ | After locating <math>P_2</math>, we just construct the line passing through <math>P_2</math> that is perpendicular to <math>O_2P_2</math> and this will also be tangent to the first circle at <math>P_1</math>. | ||
+ | |||
+ | ====Three mutual tangents==== | ||
+ | The case of three mutual tangents occurs when the two circles are externally tangent that is, when the sum of their radii equals the distance between their centres. In this case two of the three tangents (the "outer" ones) can be found using the formula in the previous section, and the third, which passes "between" the circles, may easily be found by first finding the point of mutual tangency (see section [[#One point of intersection|One point of intersection]] above). | ||
+ | |||
+ | ====Four mutual tangents==== | ||
+ | If two circles do not intersect or overlap at all, that is, the distance between their centres is greater than the sum of their radii, they will have four mutual tangents. Two of the mutual tangents can be found using the formulas two sections above. These are the two "outer" tangents, with the property that both circles lie on the same side of an outer tangent. There are also two "inner" tangents that "separate" the two circles from each other. | ||
+ | |||
+ | The procedure for computing these "inner" tangents is similar to the procedure for computing the "outer" tangents. We begin by letting <math>l</math> be one of these tangents, that touches the first circle at <math>P_1</math> and the second at <math>P_2</math>. Let the point of intersection of <math>l</math> with <math>O_1O_2</math> be denoted <math>Q</math>. Then, right-angled <math>\triangle O_1P_1Q</math> is similar to right-angled <math>\triangle O_2P_2Q</math>. Let <math>d_1 = |O_1Q|</math> and <math>d_2 = |O_2Q|</math>. Then, by similarity, we see that <math>\frac{d_1}{r_1} = \frac{d_2}{r_2}</math>. Along with the equation <math>d_1 + d_2 = |O_1O_2|</math>, we can solve: <math>d_1 = \frac{r_1}{r_1+r_2}|O_1O_2|, d_2 = \frac{r_2}{r_1+r_2}|O_1O_2|</math>. Then, letting <math>\theta = \angle P_2O_2Q</math>, we have <math>\cos \theta = \frac{r_2}{d_2} = \frac{r_1+r_2}{|O_1O_2|}</math>. Let <math>k = |P_1P_2|</math>, and see that <math>k = |QP_1| + |QP_2| = \sqrt{d_1^2 - r_1^2} + \sqrt{d_2^2 - r_2^2}</math>, which, after some messy algebra, will turn out to be <math>\sqrt{|O_1O_2|^2 - (r_1+r_2)^2}</math>. Also observe that <math>\sin \theta = \frac{|P_2Q|}{|O_2Q|} = \frac{|P_1Q|}{|O_1Q|} = \frac{|P_1Q|+|P_2Q|}{|O_1Q|+|O_2Q|} = \frac{k}{|O_1O_2|}</math>. | ||
+ | |||
+ | Moving along, we have <math>P_2 = O_2 + r_2 [\cos (\operatorname{atan2}(O_1-O_2) + \theta), \sin (\operatorname{atan2}(O_1-O_2) + \theta)]</math> as before. Defining <math>\Delta x = O_{1_x}-O_{2_x}</math> and <math>\Delta y</math> analogously, we obtain: | ||
+ | :<math>\cos( \operatorname{atan2}(O_1 - O_2) + \theta)</math> | ||
+ | :<math> = \cos \operatorname{atan2}(O_1 - O_2) \cos \theta - \sin \operatorname{atan2}(O_1 - O_2) \sin \theta</math> | ||
+ | :<math> = \frac{\Delta x}{\Delta x^2 + \Delta y^2} \frac{r_1+r_2}{|O_1O_2|} - \frac{\Delta y}{\Delta x^2 + \Delta y^2} \frac{k}{|O_1O_2|}</math> | ||
+ | :<math> = \frac{(r_1+r_2)\Delta x - k\Delta y}{|O_1O_2|^2}</math> | ||
+ | and likewise | ||
+ | :<math>\sin( \operatorname{atan2}(O_1 - O_2) + \theta)</math> | ||
+ | :<math> = \sin \operatorname{atan2}(O_1 - O_2) \cos \theta + \cos \operatorname{atan2}(O_1 - O_2) \sin \theta</math> | ||
+ | :<math> = \frac{\Delta y}{\Delta x^2 + \Delta y^2} \frac{r_1+r_2}{|O_1O_2|} + \frac{\Delta x}{\Delta x^2 + \Delta y^2} \frac{k}{|O_1O_2|}</math> | ||
+ | :<math> = \frac{k\Delta x + (r_1+r_2)\Delta y}{|O_1O_2|^2}</math> | ||
+ | |||
+ | Careful! The value of <math>h</math> in this case is not the same as the value of <math>h</math> for the outer tangents. | ||
+ | |||
+ | ====Summary and discussion==== | ||
+ | We will summarize the results below. (Note that we have exchanged the two circles.) We define <math>h = \sqrt{|O_1O_2|^2 - (r_1-r_2)^2}</math> and <math>k = \sqrt{|O_1O_2|^2 - (r_1+r_2)^2}</math>, and then the points of tangency of the two outer tangents with the first circle are given by: | ||
+ | :<math>P_1 = O_1 + \frac{r_1}{|O_1O_2|^2} [(r_1-r_2)\Delta x - h\Delta y, h\Delta x + (r_1-r_2)\Delta y]</math> | ||
+ | :<math>P_2 = O_1 + \frac{r_1}{|O_1O_2|^2} [(r_1-r_2)\Delta x + h\Delta y, -h\Delta x + (r_1-r_2)\Delta y]</math> | ||
+ | and likewise for the two inner tangents: | ||
+ | :<math>P_3 = O_1 + \frac{r_1}{|O_1O_2|^2} [(r_1+r_2)\Delta x - k\Delta y, k\Delta x + (r_1+r_2)\Delta y]</math> | ||
+ | :<math>P_4 = O_1 + \frac{r_1}{|O_1O_2|^2} [(r_1+r_2)\Delta x + k\Delta y, -k\Delta x + (r_1+r_2)\Delta y]</math> | ||
+ | |||
+ | The first pair of formulas will be invalid when <math>|r_1 - r_2| > |O_1O_2|</math>, because <math>h</math> will be undefined. Obviously, in this case, <math>r_1 + r_2 > |O_1O_2|</math> also, so <math>k</math> will also be undefined, and the second pair of formulas will be invalid. | ||
+ | |||
+ | When <math>|r_1 - r_2| = |O_1O_2|</math>, we will obtain <math>h = 0</math>, so <math>P_1</math> and <math>P_2</math> will coincide. The second pair of formulas will still be invalid, so we will obtain a total of one point of tangency. | ||
+ | |||
+ | When <math>|r_1 - r_2| < |O_1O_2| < r_1 + r_2</math>, we will obtain <math>h > 0</math>, so <math>P_1</math> and <math>P_2</math> will be distinct, but <math>k</math> will still be undefined, so we obtain a total of two points of tangency. | ||
+ | |||
+ | When <math>|O_1O_2| = r_1 + r_2</math>, we will obtain <math>h > 0, k = 0</math> giving two distinct points <math>P_1, P_2</math>, but <math>P_3 = P_4</math>, a total of three points of tangency. | ||
+ | |||
+ | Finally, when <math>|O_1O_2| > r_1 + r_2</math>, then <math>h, k \geq 0</math> and all four points <math>P_1, P_2, P_3, P_4</math> will be distinct, as expected. | ||
+ | |||
+ | [[Category:Algorithms]] | ||
+ | [[Category:Geometry]] | ||
+ | [[Category:Pages needing diagrams]] |
Latest revision as of 06:14, 11 April 2014
Contents
- 1 Introduction and Scope
- 2 Points
- 3 Lines
- 3.1 What is a line?
- 3.2 The equation of a line
- 3.3 Standard Form of the equation of a line
- 3.4 Slope and intercepts of the line in standard form
- 3.5 Determining if a point is on a line
- 3.6 Construction of the line through two given points
- 3.7 Parallel and coincident lines
- 3.8 Finding the point of intersection of two lines
- 3.9 Direction numbers for a line
- 3.10 Parametric equation of a line
- 3.11 Translation along a line
- 3.12 Dropping a perpendicular
- 3.13 The distance from a point to a line
- 3.14 On which side of a line does a point lie?
- 3.15 The distance between two lines
- 3.16 Translating a line
- 4 Line segments
- 4.1 Introduction to line segments
- 4.2 Coincidence (equivalence) of line segments
- 4.3 Length of a line segment
- 4.4 Partitioning by length
- 4.5 Containing line
- 4.6 Determining if a point lies on a line segment
- 4.7 Intersection of line segments
- 4.8 Do two line segments cross?
- 4.9 Direction numbers for the containing line
- 4.10 Perpendicular bisector of a line segment
- 4.11 Conclusion - lines and line segments
- 5 Angles
- 6 Vectors
- 7 Circles
Introduction and Scope[edit]
Definition[edit]
Computational geometry, as one can easily guess from the name, is the branch of computer science encompassing geometrical problems and how their solutions may be implemented (efficiently, one would hope) on a computer.
Scope[edit]
Essentially all of the computational geometry you will encounter in high-school level competitions, even
competitions such as the IOI, is plane Euclidean geometry, the noble subject on which Euclid wrote his
Elements and a favorite of mathematical competitions. You would be hard-pressed to find contests containing geometry problems in three dimensions or higher. You also do not need to worry about non-Euclidean
geometries in which the angles of a triangle don't quite add to 180 degrees, and that sort of thing. In short,
the type of geometry that shows up in computer science contests is the type of geometry to which you have
been exposed, countless times, in mathematics class, perhaps without being told that other geometries exist.
So in all that follows, the universe is two-dimensional, parallel lines never meet, the area of a circle with
radius is
, and so on. This article discusses basic two-dimensional computational geometry; more advanced topics, such as computation of convex hulls, are discussed in separate articles.
Points[edit]
Introduction to points[edit]
Many would claim that the point is the fundamental unit of geometry. Lines, circles, and polygons are all merely (infinite) collections of points and in fact we will initially consider them as such in order to derive several important results. A point is an exact location in space. Operations on points are very easy to perform computationally, simply because points themselves are such simple objects.
Representation: Cartesian coordinates[edit]
In our case, "space" is actually a plane, two-dimensional. That means that we need two real numbers to
describe any point in our space. Most of the time, we will be using the Cartesian (rectangular) coordinate
system. In fact, when points are given in the input of a programming problem, they are almost always
given in Cartesian coordinates. The Cartesian coordinate system is easy to understand and every pair of
real numbers corresponds to exactly one point in the plane (and vice versa), making it an ideal choice for
computational geometry.
Thus, a point will be represented in the computer's memory by an ordered pair of real numbers. Due to the
nature of geometry, it is usually inappropriate to use integers, as points generally do not fit neatly into the
integer lattice! Even if the input consists only of points with integer coordinates, calculations with these
coordinates will often yield points with non-integral coordinates, which can often cause counter-intuitive
behavior that will have you scratching your head! For example, in C++, when one integer is divided by
another, the result is always truncated to fit into an integer, and this is usually not desirable.
Determining whether two points coincide[edit]
Using the useful property of the Cartesian coordinate system discussed above, we can determine whether
or not two given points coincide. Denote the two points by and
, with coordinates
and
, respectively, and then:
Read: The statement that and
are the same point is equivalent to the statement that their corresponding coordinates are equal. That is,
and
having both the same x-coordinates and also the same y-coordinates is both sufficient and necessary for the two to be the same point.
The distance between two points[edit]
To find the distance between two points, we use the Euclidean formula. Given two points and
, the distance between them is given by:
(Note that when we write , we mean that
is a point with x-coordinate
and y-coordinate
.)
The midpoint of the line segment joining two points[edit]
Given two points, how may we find the midpoint of the line segment joining two points? (Intuitively, it is the point that is "right in the middle" of two given points. One might think that we require some knowledge about line segments in order to answer this, but it is for precisely the reason that, in a certain sense, no such knowledge is required to understand the answer, that this operation is found in the Points section. So, given two points and
, this midpoint is given by
Lines[edit]
What is a line?[edit]
In axiomatic geometry, some terms such as point and line are left undefined, because an infinite regression of definitions is clearly absurd. In the algebraic approach we are taking, the line is defined in terms of the points which lie on it; that will be discussed in the following section. It will just be pointed out here that the word line is being used in the modern mathematical sense. Lines are straight; the terms line and straight line shall have identical meaning. Lines extend indefinitely in both directions, unlike rays and line segments.
The equation of a line[edit]
In computational geometry, we have to treat all aspects of geometry algebraically. Computers are excellent at dealing with numbers but have no mechanism for dealing with geometrical constructions; rather we must reduce them to algebra if we wish to accomplish anything.
In Ontario high schools, the equation of a line is taught in the ninth grade. For example, the line which passes through the points (0,1) and (1,0) has the equation . Precisely, this means that for a given point
, the statement
is equivalent to, or sufficient and necessary for, the point to be on the line.
The form of the equation of the line which is first introduced is generally the , in which
is the slope of the line and
is the y-intercept. For example, the line discussed above has the equation
, that is,
and
. By substituting different values for
and
, we can obtain various (different) lines. But there's a problem here: if your line is vertical, then it is not
possible to choose values of
and
for the line. (Try it!) This is because the y-coordinate is no longer a function of the x-coordinate.
Thus, when dealing with lines computationally, it seems we would need to have a special case: check if the line is vertical; if so, then do something, otherwise do something else. This is a time-consuming and error-prone way of coding.
Standard Form of the equation of a line[edit]
Even though the slope-intercept form cannot describe a vertical line, there is an equation that describes a vertical line. For example, the line passing through (3,1) and (3,8) is . In fact, almost any line can be described by an equation of the form
. (Try it if you don't believe me. I have merely switched around
and
from the slope-intercept form.) Except... horizontal lines. So we have two forms of the equation of a line: one which fails on vertical lines and one which fails on horizontal lines. Can we combine them to give an equation of the line which is valid for any
line?
As it turns out, it is indeed possible.
That equation, the standard form of the equation of the line is:
By substituting appropriate values of ,
, and
, one can
describe any line with this equation. And by storing values of
,
, and
, one can represent a line in the computer's memory.
Here are some pairs of points and possible equations for each:
As you can see, it handles vertical and horizontal lines properly, as well as lines which are neither.
Note that the standard form is not unique: for example, the equation of the
first line could have just as well been or perhaps
. Any given line has infinitely many representations
in the standard form. However, each standard form representation describes
at most one line.
If and
are both zero, the standard form describes no line
at all.
Slope and intercepts of the line in standard form[edit]
By isolating from the standard form, we obtain the slope and y-intercept
form for line
(
) when
(that is, when
the line is not vertical):
The y-intercept is obtained by letting and then:
Similarly, the x-intercept is given by:
In order for the x-intercept to exist, the line must not be horizontal, that
is, .
Determining if a point is on a line[edit]
Using the definition of the equation of a line, it becomes evident that
to determine whether or not a point lies on a line, we simply substitute its
coordinates into the equation of the line, and check if the LHS is, indeed,
equal to zero. This allows us to determine, for example, that
is on the last line given in the table above, whereas
is not
on that line.
Construction of the line through two given points[edit]
A good question is: how do we determine that fourth equation above, the equation of the line through (6,6) and (4,9)? It's not immediately obvious from the two points given, whereas the other three are pretty easy.
For the slope-y-intercept form , you first determined the slope
, and then solved for
. A similar procedure can be used for
standard form.
We state here the following pseudocode for determining the
coefficients
,
,
of the equation of the line through
points
and
in standard form:
(It is one thing to derive a formula or algorithm and quite another thing to prove it. The derivation of this formula is not shown, but proving it is as easy as substituting to determine that the line really does pass through the two given points.)
Parallel and coincident lines[edit]
In the slope and y-intercept form, two lines are either parallel or coincident if they
have the same slope. So given two lines
(
) and
(
),
we obtain, for
:
Cross-multiplying gives a result that is valid even if either or both lines are vertical, that is, it is valid for any pair of lines in standard form:
Now, in the slope-y-intercept form, two lines coincide if their slopes and y-intercepts both coincide. In a manner similar to that of the previous section, we obtain:
or, if x-intercepts are used instead:
Two lines coincide if and either of the two
equations above holds. (As a matter of fact, if the two lines are coincident,
they will both hold, but only one of them needs to be checked.) If
but the lines are not coincident, they are parallel.
Finding the point of intersection of two lines[edit]
If two lines are coincident, every point on either line is an intersection point. If they are parallel, then no intersection points exist. We consider the general case in which neither is true.
In general, two lines intersect at a single point. That is, the intersection
point is the single point that lies on both lines. Since it lies on both lines,
it must satisfy the equations of both lines simultaneously. So to find the
intersection point of
and
, we seek the ordered pair
which satisfies:
This is a system of two linear equations in two unknowns and is solved by
Gaussian elimination. Multiply the first by and the second by
, giving:
Subtracting the former from the latter gives, with cancellation of the term:
Instead of redoing this to obtain the value of , we take advantage of
symmetry and simply swap all the
's with the
's. (If you don't
believe that this works, do the derivation the long way.)
or:
Notice the quantity , and how it forms the denominator
of the expressions for both
and
. When solving for the
intersection point on the computer, you only need to calculate this quantity
once. (This quantity, called a determinant, will resurface later on.)
Here is pseudocode for finding the intersection point:
When , the lines are either parallel or coincident. We now see
algebraically that the division by zero prevents us from finding a unique
intersection point for such pairs of lines.
Direction numbers for a line[edit]
This in itself is not very useful, but it will become important in the following sections as a simplifying concept.
Lines are straight; effectively they always point in the same direction. One
way to express that direction has been slope, which unfortunately is undefined
for vertical lines. The slope for a line told us that you could
start at any point on the line, move
units to the right, then
move
units up, and you would again be located on the line.
Thus we can say that
is a pair of direction numbers for that line.
This means that if
is on a line, and
and
are in the ratio
, for that line, then
is on the same line. This means that
is also a set of direction numbers for that line, or, indeed, any
multiple of
other than
. (
clearly tells you nothing about the line.)
We can define something similar for the line in standard form. Choose some
starting point on line
. Now, move to a new point
. In order for this point to be on the line
, we must have
Expanding and rearranging gives
We know that since
is on line
.
Therefore,
Convince yourself, by examining the equation above, that is a set
of direction numbers for line
. Similarly, if we have a pair of
direction numbers
, although this does not define a
unique line, we can obtain possible values of
and
as
and
, respectively.
The relationship between direction numbers and points on the corresponding line
is an "if-and-only-if" relationship. If and
are
in the ratio
, then we can "shift" by
,
and vice versa.
Any line perpendicular to will have the direction numbers
,
and thus a possible equation starts
.
(This is the same as saying, for non-vertical lines, that the product of slopes
of perpendicular lines is -1. Examine the equation for the slope of a line
given in standard form and you'll see why.) In fact, in an algebraic treatment of geometry
such as this, we do not prove this claim, but instead proclaim it the definition of
perpendicularity: given two lines with direction numbers
and
, they are perpendicular if and only if
.
Given some line, all lines parallel to that one have the same direction numbers. That is, the direction numbers, while providing information about a line's direction, provide no information about its position. However, sometimes all that is needed is the direction, and here the direction numbers are very useful.
Parametric equation of a line[edit]
Given some line and a point
known to be on the line, we can use the direction numbers to write the parametric equation of the line. Since
is a set of direction numbers for the line, we see that
will be on the line for any
, and furthermore each point on the line corresponds to exactly one value of
in this way.
Translation along a line[edit]
Given some line and a point
known to be on the line, we wish to locate another point on the line that is distance
away from
. We can do this by observing that the general point is given by
, which is distance
away from
. Therefore, we want
, and finally obtain
. Note that unless
, there is another possible answer, which is simply "on the other side":
.
Dropping a perpendicular[edit]
Given a line
and a point
which may or may not be on
, can we find the line perpendicular to
passing through
? By Euclid's Fifth Postulate, there exists
exactly one such line. The algorithm to find it is given below:
where is the perpendicular line desired.
There is nothing difficult to memorize here: we already noted in the previous
section how to find the values of and
, and finding the value
of
is merely setting
equal to zero (so that the
point
will be on the resulting line).
The foot of the perpendicular is the point at which it intersects the
line . It is guaranteed to exist since two lines cannot, of course, be
both perpendicular and parallel. Combining the above algorithm with the line intersection algorithm
explained earlier gives a solution for the location of the point. A bit of algebra gives
this optimized algorithm:
where are the coordinates of the foot of the perpendicular from
to
.
The distance from a point to a line[edit]
By the distance from a point
to a line
what is meant is the closest possible distance from
to any point on
. What point on
is closest to
?
It is intuitive perhaps that it is obtained by dropping a perpendicular
from
to
. That is, we choose a point
such that
, and the distance from
to
is then the length
of line segment
, denoted
.
The reason why this is the shortest distance possible is this: Choose any other
point on
. Now,
is right-angled at
.
The longest side of a right triangle is the hypotenuse, so that
. Thus
is truly the shortest possible distance.
Now, as noted earlier, the line , being perpendicular to
, has the direction numbers
. Thus, for any
, the point
is on
. For some choice of
, this point must coincide with
.
Since that point lies on
, we have
This instantly gives the formula for the foot of the perpendicular given in the previous section.
Now, the distance is found with the Euclidean formula:
The last line is the formula to remember. To restate,
(It was noted earlier that if and
are both zero, then
we don't actually have a line. Therefore, the denominator above can never be
zero, which is a good thing.)
On which side of a line does a point lie?[edit]
A line partitions the plane into two regions. For example, a vertical line
divides the plane into a region on the left and a region on the right. Now,
when a point
does not satisfy the equation of a line
, can we determine on which side of the line it lies?
Yes we can, with a certain restriction. If , then the
point lies on one side of the line; if
, then it lies
on the other side. However, it's a bit pointless to say which side it
lies on: does it lie on the left or the right? If the line is horizontal, then
this question becomes meaningless. Also, notice that if we flip the signs of
,
, and
, then the value of
is
negated also, but that changes neither the point or the line. It is enough,
however, to tell if two points are on the same side of the line or on opposite
sides; simply determine whether
has the same sign for both,
or different signs.
The distance between two lines[edit]
If two lines intersect, the closest distance between them is zero, namely at
their intersection point. If they are coincident, then the distance is
similarly zero. If two lines are parallel, however, there is a nonzero distance
between them, and it is defined similarly to the distance between a point and a
line. To find this distance, we notice that the lines
and
are coincident, where
is the origin,
is
the foot of the perpendicular from
to
, and
is the
foot of the perpendicular from
to
. We know, by substituting
for both
(
) and
(
) that:
Now here we come up against a complication. If is on the line
segment
, then we have to add
and
to get the desired
. That is, if
is on the same
side of both lines. Otherwise, we have to take the difference. Here's some
code that takes care of these details:
Translating a line[edit]
Suppose we are given a line and we wish to find a line parallel to it such that the distance between these two lines is
. To do this, we suppose that the new line has equation
. Since the two lines have the same
and
value, they must be parallel (or coincident of
also). Then, the distance between them will be given by
, as the previous section suggests. To obtain a value of
for this expression, it is not hard to see that we should choose
.
Line segments[edit]
Introduction to line segments[edit]
A line segment is the part of a line located "between" two points on that
line, called endpoints. Any pair of points defines a unique line
segment. Most definitions of "line segment" allow the endpoints to coincide,
giving a single point, but this case will often not arise in programming
problems and it is trivial to handle when it does arise, so we will not discuss
it here; we assume the endpoints must be distinct. Thus, every line segment
defines exactly one line.
We may represent a line segment in memory as a pair of points: that is, four
numbers in total.
Coincidence (equivalence) of line segments[edit]
Two line segments coincide if they have the same endpoints. However, they may have them in any order, hence we have:
(The parentheses are unnecessary and are added only for the sake of clarity.)
Length of a line segment[edit]
The length of a line segment is nothing more than the distance between its endpoints.
Partitioning by length[edit]
Suppose we wish to partition a line segment by introducing
a point
on
such that
. That
is, we wish to partition it into two line segments with their lengths in the
ratio
. We may do so as follows:
In the special case that , we have the midpoint, as discussed in the Points section.
Containing line[edit]
All we have to do is find the line passing through both endpoints; the algorithm to do this is discussed in the section "Construction of the line through two given points".
Determining if a point lies on a line segment[edit]
Here is one interesting idea: if a point lies on segment
, then the relation
will hold. If it is on the line
but
not on the segment
, then it is the difference
between
and
that will equal
, not the sum. If
it is not on this line, then the points
,
, and
form a
triangle, and by the Triangle Inequality,
. Thus:
Although this test is mathematically ingenious, it should not be used in
practice, since the extraction of a square root is a slow operation. (Think about how much work it takes by hand, for example, to compute a square root, relative to carrying out multiplication or division by hand.)
A faster method is to obtain the line containing the line segment (see
previous section); if multiple queries are to be made on the same line segment
then it is advisable to store the values of ,
, and
rather than computing them over and over again; and we first check if the point
to test is on the line; if it is, then we must check if it is on the
segment by checking if each coordinate of the point is between the
corresponding coordinates of the endpoints of the segment.
For a one-time query (when we do not expect to see the line again), the use of
the properties of similar triangles yields the following test: the point is on
the line segment if and only if
and
is between
and
. When this test is used several
times with different segments, the number of multiplications required is only
half of the number required for the test via the containing line, but
if the line is reused, then the test via the containing line ends up
using fewer additions/subtractions in the long run.
Intersection of line segments[edit]
Given two line segments and
, how do we
determine whether they intersect?
First, if the containing lines are coincident, then the line segments intersect
if and only if at least one of the endpoints of one of the segments is on the
other segment. In general, when the containing lines do not coincide,
the segments intersect if and only if and
are not on the same side of
and
and
are
not on the same side of
. That is, extend each segment to a line and
then determine on which sides of the line lie the endpoints of the other segment. (If one point is on the line and the other is not, then they are not considered to be on the same side, since two
line segments can intersect even if the endpoint of one lies on the other.)
If the segments intersect, their intersection point can be determined by finding the intersection
point of the containing lines.
Another method for determining whether two line segments intersect is finding
the intersection point (if it exists) of the containing lines and checking if
it lies on both line segments (as in the end of the previous section). After
finding the containing lines, this method requires six multiplications and two
divisions, whereas the one above requires eight multiplications. Since
multiplications are generally faster, we prefer the method above to this one.
Do two line segments cross?[edit]
The word cross is used here in a stronger sense than intersect.
Two line segments cross if they intersect and no point of intersection is
an endpoint of either line segment. Intuitively, the two line segments form
a (possibly distorted) X shape. Here, we can ignore the degenerate cases for line segment
intersection: we simply test that and
are on different sides of
(this time the test fails if either of them is actually
on it), and that
and
are on different sides of
.
The second method described in the previous section can again be applied, although again
it is expected to be slower.
Direction numbers for the containing line[edit]
By the definition of the direction numbers, a set of direction numbers for the
line segment is
. This gives
an instant proof for the "magic formula" for the line through two given points: we convert
these direction numbers to values for
and
and then solve for
using one of the points.
Perpendicular bisector of a line segment[edit]
The perpendicular bisector of a line segment is the line perpendicular to the
line segment which also passes through the line segment's midpoint. Notice that
the direction numbers obtained in the previous section can be used to obtain the
direction numbers for a perpendicular line, and that these can in turn be used
to reconstruct the values of and
for that line. Given that the
line must also pass through the midpoint:
This technique requires a total of two multiplications and two divisions. If we
substitute the values of and
into the last line and expand, we
can change this to four multiplications and one division, which is almost
certainly slower as division by two is a very fast operation.
Conclusion - lines and line segments[edit]
The techniques of the two preceding chapters should provide inspiration on how to achieve tasks that are "somewhere in-between". For example, we have not discussed the intersection of a line and a line segment. However, it is fairly clear that all that is required is to test on which sides of the line lie the endpoints of the segment: half of the test for two line segments. We also have not discussed the distance from a point to a line segment. We have omitted any discussion of rays altogether. If you thoroughly understand how these techniques work, though, extending them to problems not explicitly mentioned should not be difficult. Feel free to add these sections to this article; the exclusion of any material from the current draft is not an indication that such material does not belong in this article.
Angles[edit]
Introduction to angles[edit]
In trigonometry, one proves the Law of Cosines. In a purely algebraic approach to geometry, however the concept of angle is defined using the Law of Cosines, and the Law itself requires no proof. Still, we will not use that definition directly, because deriving everything from it would be unnecessarily complicated. Instead, we will assume that we already know some properties of angles. Storing angles in memory is very easy: just store the angle's radian measure. Why not degree measure? Degree measure is convenient for mental calculation, but radian measure is more mathematically convenient and, as such, trigonometric functions of most standard language libraries, such as those of Pascal and C/C++, expect their arguments in radians. (Inverse trigonometric functions return results in radians.) We will use radian measure throughout this chapter, without stating "radians", because radian measure is assumed when no units are given.
Straightforward applications of basic trigonometry, such as finding the angles in a triangle whose vertices are known (Law of Cosines), are not discussed here.
Directed angle and the atan2 function[edit]
Suppose a ray with its endpoint at the origin initially points along the
positive x-axis and is rotated counterclockwise around the origin by an angle
of . From elementary trigonometry, the ray now consists of points
, where
. This angle
is a directed angle. Notice there is another ray with its endpoint at
the origin that makes an angle of
with the positive x-axis:
obtained by rotating clockwise rather than counterclockwise. But the directed
angle in this case would be
. Thus, by specifying a directed angle
from the positive x-axis
we can uniquely specify one particular ray.
Can we reverse this process? Can we find the directed angle from the positive
x-axis to the ray , where
? Notice that
when
,
, so taking the inverse tangent
should give back
. There are just two problems with this: one is
that
might be zero (but the angle will still be defined, either
or
), the other is that the point
will give
the same tangent even though it lies on the other side (and hence its directed
angle should differ from that of
by
.
However, because this is such a useful application, the Intel FPU has a
built-in instruction to compute the directed angle from the positive x-axis to
ray
, and the libraries of both C and Free Pascal
contain functions for this purpose. C's is called
atan2
, and it takes
two arguments, and
, in that order, returning an angle in
radians, the desired directed angle, a real number
satisfying
. (Notice that as with undirected angles, adding
to a directed angle leaves it unchanged). Remember that
comes first and not
; the reason for this has to do with the design of
the Intel FPU and the calling convention of C. Free Pascal's math library aims
to largely emulate that of C, so it provides the
arctan2
function
which takes the same arguments and produces the same return value.
The angle between a line and the x-axis[edit]
When two lines intersect, two pairs of angles are formed (the two angles in
each pair are equal). They are supplementary. To find one of these angles, let
us shift the line until it passes through the x-axis. Then, adding the
direction numbers to the origin gives another point. We now apply
the
atan2
function: atan2
(). (Notice that we have
reversed the order of
and
, as required.) The result may be
negative; we can add
to it to make it non-negative.
The angle between two lines[edit]
To find one of the two angles between two lines, we find the angle between each
line and the x-axis, then subtract. (Draw a diagram to convince yourself that
this works.) If the result is negative, add degrees, once or
twice as necessary. The other angle is obtained by subtracting from
.
The angle bisector of a pair of intersecting lines[edit]
Using the result of the previous section and a great deal of algebra and trigonometry,
together with the line intersection algorithm, gives the following algorithm for finding one of the
two angle bisectors of a pair of (intersecting) lines
and
(the bisector
is represented as
):
The other angle bisector, of course, is perpendicular to this line and also passes through that intersection point.
Vectors[edit]
Introduction to vectors[edit]
Although the word vector has a formal definition, we will not find it useful. It is better, in the context of computational geometry, to think of a vector as an idealized object which represents a given translation. Visually, a vector may be represented as an arrow with a fixed length pointing in a fixed direction, but without a fixed location. For example, on the Cartesian plane, consider the translation "3 units down and 4 units right". If you start at the point (8,10) and apply this translation, (12,7) is obtained. This can also be represented as an arrow with length 5 units and direction approximately 37 degrees south of east. Placing the tail of this arrow at (8,10) results in the head resting upon the point (12,7). The vector from (0,0) to (4,-3) is the same vector, as it also represents a translation 3 units down and 4 units right, and has the same length and direction. However, the vector from (12,7) to (8,10) and the vector from (0,0) to (-3,4) are different from the one from (8,10) to (12,7); they have the same lengths, but their directions are different, and so they are different vectors. The vector from (0,0) to (8,-6) is also different; it has the same direction, but a different length. In both cases, these are simply different translations, and hence different vectors. The word vector is from the Latin, meaning carrier, appropriate as it carries from one location (a point) to another.
Representation[edit]
We could represent a vector by its magnitude and direction, but it is usually not convenient to do so. Even still, it might be useful occasionally to find the magnitude and direction of a vector; refer to the sections on length of a line segment and directed angle and the atan2 function for the necessary mathematics. Instead, we will use the Cartesian representation. If we place the tail of a vector on the origin, the head rests upon a certain point; the Cartesian coordinates of this point are the Cartesian components of the vector. We thus represent a vector as we do a point, as an ordered pair of real numbers, but we shall enclose these in brackets instead of parentheses. The vector discussed above is then [4,-3], as when the tail is placed on (0,0), the head rests upon (4,-3). Two vectors are equal when both of their corresponding components are equal.
Standard vector notation[edit]
In writing, vectors are represented as letters with small rightward-pointing arrows over them, e.g., . Vectors are usually typeset in bold, e.g.,
. We shall denote the components of
as
and
. The magnitude of
may be denoted simply
, or, to avoid confusion with an unrelated scalar variable,
. There is a special vector known as the zero vector, the identity translation; it leaves one's position unchanged and has the Cartesian representation [0,0]. We shall represent it as
.
Basic operations[edit]
The order of operations is the same with vectors as with real numbers.
Addition[edit]
Addition of vectors shares many properties with addition of real numbers. It is represented by the plus sign, and is associative and commutative.
Of a vector to a point[edit]
Adding a vector to a point is another name for the operation in which a point is simply translated by a given vector. It is not hard to see that . We could also write the same sum as
, since addition is supposed to be commutative. As one can easily see, adding a point and a vector results in another point. The zero vector is the additive identity; adding it to any point leaves the point unchanged. Geometrically, adding a point and a vector entails placing the vector's tail at the point; the vector's head then rests upon the sum.
Of two vectors[edit]
If we want addition to be associative too, then the sum must be the same point as
. The first sum represents the point arrived at when the translations representing
and
are taken in succession. Therefore, in the second sum, we should define
in such a way so that it gives a vector representing the translation obtained by taking those of
and
in succession. It is not too hard to see that
. Geometrically, if the tail of
is placed at the head of
, the arrow drawn from the tail of
to the head of
is the sum. Again, the zero vector is the additive identity.
Negation[edit]
For every vector we can identify a corresponding vector, denoted
, such that the translations represented by
and
are inverse transformations. Another way of stating this is that
, or that
and
have the same length but opposite directions. If
, then
.
Subtraction[edit]
Of a vector from a point[edit]
We define subtraction to be the inverse operation of addition. That is, for any point and vector
, we should have that
. Since the vector
represents the inverse translation to
, we can simply add
to
to obtain
. (Note that the expression
is not meaningful.) Geometrically, this is equivalent to placing the head of the arrow at
and then following the arrow backward to the tail. Subtracting the zero vector leaves a point unchanged.
Of a vector from a vector[edit]
To subtract one vector from another, we add its negative. Again, we find that this definition leads to subtraction being the inverse operation of addition. It is not too hard to see that . Geometrically, if the vectors
and
are placed tail-to-tail, then the vector from the head of
to the head of
is
, and vice versa. Note that
.
Of a point from a point[edit]
A vector can be considered the difference between two points, or the translation required to take one point onto the other. Given the two points and
, the vector from
to
is
, and vice versa. Note that
.
Multiplication[edit]
A vector can be scaled by a scalar (real number). This operation is known as scalar multiplication. The product denotes the vector
. This could also be notated
, though placing the scalar after the vector is more rare. Scalar multiplication takes precedence over addition and subtraction. The geometric interpretation is a bit tricky. If
, then the direction of the vector is left unchanged and the length is scaled by the factor
. If
, then the result is the zero vector; and if
, then the vector is scaled by the factor
and its direction is reversed. The scalar 1 is the multiplicative identity. Multiplying by the scalar -1 yields the negative of the original vector. Scalar multiplication is distributive.
The zero vector is a scalar multiple of any other vector. However, if two non-zero vectors are multiples of each other, then either they are parallel, that is, in the same direction (), or they are antiparallel, that is, in opposite directions (
).
Division[edit]
A vector can be divided by a scalar by multiplying it by
. This is notated in the same way as division with real numbers. Hence,
. Division by 0 is illegal.
The unit vector[edit]
To every vector except (except
), we can assign a vector
that has the same direction but a length of exactly 1. This is called a unit vector. The unit vector can be calculated as follows:
There are two elementary unit vectors: [1,0], denoted , and [0,1], denoted
. That is, the unit vectors pointing along the positive x- and y-axes. Note that we can write a vector
as
.
Obtaining a vector of a given length in the same direction as a given vector[edit]
Suppose we want a vector of length pointing in the same direction as
. Then, all we need to do is scale
by the factor
. Thus our new vector is
, which can also be written
=
. Hence the unit vector is a "prototype" for vectors of a given direction.
Rotation[edit]
Given a vector and an angle
, we can rotate
counterclockwise through the angle
to obtain a new vector
using the following formulae:
The same formula can be used to rotate points, when they are considered as the endpoints of vectors with their tails at the origin.
Dot product[edit]
The dot product or scalar product is notated and defined as follows:
It is commutative, but not associative (since expressions like are meaningless). However, the dot product does associate with scalar multiplication; that is,
. It is distributive over addition, so that
. (This is actually left-distributivity, but right-distributivity follows from the commutative property.) These properties can easily be proven using the Cartesian components. The dot product has two useful properties.
First, the dot product satisfies the relation
where is the angle between
and
. This allows us to find the angle between two vectors as follows:
This formula breaks down if one of the vectors is the zero vector (in which case no meaningful angle can be defined anyway). The dot product gives a quick test for perpendicularity: two nonzero vectors are perpendicular if and only if their dot product is zero. The dot product is maximal when the two vectors are parallel, and minimal (maximally negative) when the two vectors are antiparallel.
Second, the dot product can be used to compute projections.
The vector projection[edit]
The vector projection of onto
is, intuitively, the "shadow" cast by
onto
by a light source delivering rays perpendicular to
. We imagine
to be a screen and
to be an arrow; we are projecting the arrow onto the screen. (It is okay for parts of the projection to lie outside the "screen".) Geometrically, the tail of the projection of
onto
is the foot of the perpendicular from the tail of
to
, and the head of the projection is likewise the foot of the perpendicular from the head of
. The vector projection is a vector pointing in the same direction as
. There is no standard notation for vector projection; one notation is
for the projection of
onto
, and vice versa.
The scalar projection[edit]
The scalar projection is the directed length of the vector projection. That is, if the angle between and
is acute, then
points in the same direction as
, and it has a positive directed length; here the scalar projection simply equals the length of the vector projection. If that angle is obtuse, on the other hand, then
and
point in opposite directions, and the scalar projection is the negative of the length of the vector projection. (If the two vectors are perpendicular, the scalar projection is zero.) There is also no standard notation for the scalar projection; one possibility is
. (Note the single vertical bars, instead of the double vertical bars that denote length.) You have already encountered scalar projections: in the unit circle, the sine of an angle is the scalar projection of a ray making that directed angle with the positive x-axis onto the y-axis, and likewise the cosine is a scalar projection onto the x-axis.
Computing projections[edit]
Why have we left discussion of the computation of the scalar and vector projections out of their respective sections? The answer is that the scalar projection is easier to compute, but harder to explain. Place the vectors and
tail-to-tail at the origin. Now rotate both vectors so that
points to the right. (Rotation actually changes the vectors, of course, but does not change the scalar projection.) Now, the cosine of the angle
between
and
is the scalar projection of
onto
, from the definition of the cosine function. By similar triangles,
is
times this. Therefore we find:
and vice versa. We could also write this as
because the dot product associates with scalar multiplication.
To compute a vector projection, we notice that we need a vector with the directed length along
. This is accomplished by scaling the unit vector
by the value of the scalar projection:
We could also write this as
Two notes: first, projecting onto the zero vector is meaningless since it has no direction, and second, neither scalar nor vector projection is commutative.
Determinant[edit]
The determinant of two vectors and
, denoted
, is the determinant of the matrix having
and
as rows (or, equivalently, columns), that is:
and is therefore equal to .
The size-2 determinant is often mistakenly referred to as the cross product. (This usage is nearly universal in casual programming parlance and less reputable websites.) This is because there exists a product of two three-dimensional vectors known as the cross product, and the cross-product of two vectors lying in the xy-plane is a vector pointing along the z-axis with z-component equal to the determinant of the two plane vectors. However, no background with three-dimensional vectors, cross-products, or matrices is required for this section. In two dimensions, all that is needed is the formula:
. However, for the sake of convenience, we shall denote the size-2 determinant by the same symbol as the cross product, the cross: hence
. (This also avoids confusion with the larger matrices in advanced linear algebra and higher dimensions.) It is anticommutative, meaning that
. It satisfies the properties
, and with addition it is both left-distributive, so that
, and right-distributive, so that
. There are two primary uses for the size-2 determinant in two-dimensional computational geometry.
The determinant is useful in several algorithms for computing the convex hull because it allows us to determine the directed angle from one vector to another. (Note that the dot product allows us to determine the undirected angle; it makes sense because the dot product commutes whereas the size-2 determinant anticommutes.) The following relation holds:
where is the directed angle from
to
. That is, the counterclockwise angle from
to
when they are both anchored at the same point. Rearranging allows us to compute the angle directly:
(Note that the sine function is odd, so that when and
are interchanged in the above, the right side is negated, and so is the left.)
Often, however, we do not need the directed angle itself. In the monotone chains algorithm for convex hull computation, for example, all we need to know is whether there is a clockwise or a counterclockwise turn from
to
. (That is, if one wishes to rotate
through no more than 180 degrees either clockwise or counterclockwise so that its direction coincides with that of
, which direction should one choose?) It turns out that if
is positive, the answer is counterclockwise; if it is negative, clockwise, and if it is zero, the vectors are either parallel or antiparallel. (Indeed, the closer
is to a right angle, the larger the cross product in magnitude; in some sense then it measures "how far away" the vectors are from each other.)
The determinant is also useful in computing areas of parallelograms and triangles. If the two vectors and
are placed tail-to-tail, a parallelogram can be formed using these vectors as adjacent sides; its area is
. A triangle can also be formed using these vectors as adjacent sides; its area is half that of the parallelogram, or
. (This echoes the formula
taught in high-school math classes.) In fact, the area of a general quadrilateral
can be computed with a determinant as well; it equals
.
Circles[edit]
Introduction to circles[edit]
A circle is the locus of points in the plane equidistant from a given point. That is, we choose some point , the centre, and some distance
, the radius, and the circle consists exactly of those points whose Euclidean distance from
is exactly
. When storing a circle in memory, we store merely the centre and the radius.
Equation of a circle[edit]
Suppose the circle has centre and radius
. Then, from the definition, we know that any point
on the circle must satisfy
. This means
, or
.
Inside, outside, or on the circle[edit]
The equation of a circle is a sufficient and necessary condition for a point to be on the circle. If it is not on the circle, it must be either inside the circle or outside the circle. It will be inside the circle when its distance from the centre is less than , or
, and similarly it will be outside the circle when
.
Intersection of a circle with a line[edit]
To determine points of intersection of a circle with another figure (it might also be a circle), solve the simultaneous equations obtained in and
. For example, given a circle centered at (2,3) with radius 2, and the line
, we would solve the simultaneous equations
and
. If there are multiple solutions, each is a different point of intersection; if there are no solutions then the two figures do not intersect. Here then are general results. Note that if you do not check the "no intersection" condition beforehand and plunge straight into the quadratic formula (after reducing the two simultaneous equations to one equation), you will try to extract the square root of a negative number, which will crash some languages (such as Pascal).
No points of intersection[edit]
When the closest distance from the centre of the circle to the line is greater than the radius of the circle, the circle and line do not intersect. (The formula for the distance from a point to a line can be found in the Lines section of this article.)
One point of intersection[edit]
When the closest distance from the centre of the circle to the line is exactly the circle's radius, the line is tangent to the circle. One way of finding this point of tangency, the single point of intersection, is to drop a perpendicular from the centre of the circle to the line. (The technique for doing so is found in the Lines section.) This will, of course, yield the same answer as solving the simultaneous equations.
Two points of intersection[edit]
When the closest distance from the centre of the circle to the line is less than the circle's radius, the line intersects the circle twice.
To find the two points of intersection, first drop a perpendicular from the centre of the circle to the line. Call the foot of the perpendicular and denote the distance
by
. Now, let the two points of intersection be
and
. Then, the triangles
and
are right-angled, and hence we see that
and
. So we compute the value
; now, if we move
units in either direction along the line from
, we will reach either
or
. (The technique to do so is given in section Translation along a line.)
Intersection of a circle with a circle[edit]
Finding the points of intersection of two circles follows the same basic idea as the circle-line intersection. Here's how to determine the nature of the intersection beforehand, to avoid accidentally trying to take the square root of a negative number:
No points of intersection[edit]
When the distance between the centres of the circles is less than the difference between their radii, the circle with smaller radius will be contained completely within the circle of larger radius. When the distance between the centres of the circles is greater than the sum of their radii, neither circle will be inside the other, but still the two will not intersect.
One point of intersection[edit]
Let the two circles have centres and
and radii
and
.
- When the distance between the centres of the circles is exactly the difference between their radii, the two circles will be internally tangent. Suppose that the first circle is larger. Then the point of intersection lies on the line between
and
. The intersection point and
are on opposite sides of
, and its distances from
and
are
and
, respectively. This gives
. (It turns out that if we swap the 1's and 2's in this formula, we get the same value; hence we can use this formula without regard to which circle is labelled 1 and which one is 2.)
- When the distance between the centres of the circles is exactly the sum of their radii, they will be externally tangent; they will have one point of intersection located between
and
; it will be
units away from the former and
units away from the latter, giving the formula
.
Two points of intersection[edit]
In all other cases, there will be two points of intersection.
To find them, it will be helpful to draw a diagram. Denote the centres of the circles , their radii
, and the two points of intersection
. First draw the radical axis, the line that passes through
and
. This passes through the midpoint
between
and
, and here it intersects perpendicularly the line between
and
. Denote
and
by
, respectively. Clearly
. (1)
Also, from the Pythagorean theorem, , or
. Rearranging this gives
. (2)
Now we solve for and
. To do this, we factor the left side of (2), giving
, which allows us to divide through by (1), thus obtaining
. (3)
Equations (1) and (3) are linear and may be used to solve for in a straightforward fashion.
Now we can compute the coordinates of as
, using the argument from the previous section. Then construct the line perpendicular to
that passes through
(the radical axis). Finally, we can find the distance
, and move this distance in either direction along the radical axis (see Translation along a line) to obtain
and
.
It should be noted that two circles that intersect at two points cut each other into two arcs each: one arc that lies within the other circle, and one that lies outside it. It is not immediately obvious which is which. However, you should be able to convince yourself from drawing a diagram that if , then the arc of the first circle that is inside the second circle is counterclockwise from
to
, but if that determinant is negative, then the inside arc is counterclockwise from
to
. (For an example of where this is important, see Detectors.)
Tangents[edit]
A line is said to be tangent to a circle if it intersects the circle at exactly one point.
The tangent has an important property: if a circle with centre has a tangent line
that touches it at
, then
. The proof of this fact is simple: we assume that the two lines are not perpendicular, then drop a perpendicular from
to
at
. We observe that
is right-angled at
, and that therefore
. But this implies that
is inside the circle, a contradiction.
To actually find the tangent line to one circle at a given point on its circumference is easy; it is simply the line passing through that point that is perpendicular to the radius.
From point to circle[edit]
Sometimes we may also be given a circle with centre and radius plus a point
and asked to find a tangent to the circle that passes through the point. There may be either zero, one, or two such tangents.
Point is inside circle[edit]
When the point is inside the circle, there are no tangents to the circle through that point, because any line through the point must intersect the circle twice.
Point is on circle[edit]
When the point is on the circumference of the circle, the line passing through that is perpendicular to
is the unique tangent to the circle passing through that point.
Point is outside circle[edit]
When the point is outside the circle, there are two tangents to the circle passing through the point. To construct one such tangent, we use a trick called inversion. We let one of the points of tangency be denoted . Now
is right-angled at
. If we now drop a perpendicular from
to
at
, we obtain triangle
which is similar to
. This means that
, so
. Note that
is inside the circle, unlike
which is outside (hence the name inversion.) This allows us to locate point
on the line segment
. Then, we see that the line segment
is perpendicular to
and has length
from the Pythagorean theorem in
. This gives us enough information to compute the coordinates of
. There will be two possibilities, since we can draw two rays through
that are perpendicular to
.
Circle-circle tangents[edit]
A pair of circles may have either zero, one, two, three, or four mutual tangents.
Zero mutual tangents[edit]
If one circle lies within the other (that is, the difference between their radii is greater than the distance between their centres), then they have no mutual tangents, since every tangent to the outer circle lies outside it, and hence cannot touch the inner circle.
One mutual tangent[edit]
Two circles will have one mutual tangent if they are internally tangent (that is, the difference between their radii equals the distance between their centres). This tangent can easily be found after constructing the point of internal tangency (see section One point of intersection above).
Two mutual tangents[edit]
A pair of circles that intersect at two points has two mutual tangents, one on either "side". We will consider the problem of how to determine one of them.
Assume the circles have centres and radii
. Assume further that they have some mutual tangent
and that
is tangent to the circles at
, respectively. We see that
and
. Now, assume without loss of generality that
. Then drop the perpendicular from
to
at
, and obtain
. Then
. Also, we can solve for
using the Pythagorean theorem, obtaining
. Notice that because
is a rectangle,
.
There are two possibilities for the location of . One of them is obtained by rotating the ray
clockwise through angle
, the other obtained by rotating it counterclockwise, and in either case determining where the ray cuts the second circle. (So it doesn't actually matter which circle is bigger; the formula
will give the same result up to sign.)
We can then argue that the coordinates of one of the possible 's is given by
, because
represents the directed angle from the positive x-axis to the ray from
to
, and we are adding onto this directed angle the value
to get our final position. The other possible
will be given by subtracting
instead of adding.
This formula as written is slow, since it involves trigonometric functions, which have a higher invisible constant factor than algebraic operations and square roots. Therefore, we will rewrite it in terms of only algebraic operations. Define and
analogously.
Verify the identities and
. (These are actually obvious from the definition of
atan2
). Then:
And likewise
After locating , we just construct the line passing through
that is perpendicular to
and this will also be tangent to the first circle at
.
Three mutual tangents[edit]
The case of three mutual tangents occurs when the two circles are externally tangent that is, when the sum of their radii equals the distance between their centres. In this case two of the three tangents (the "outer" ones) can be found using the formula in the previous section, and the third, which passes "between" the circles, may easily be found by first finding the point of mutual tangency (see section One point of intersection above).
Four mutual tangents[edit]
If two circles do not intersect or overlap at all, that is, the distance between their centres is greater than the sum of their radii, they will have four mutual tangents. Two of the mutual tangents can be found using the formulas two sections above. These are the two "outer" tangents, with the property that both circles lie on the same side of an outer tangent. There are also two "inner" tangents that "separate" the two circles from each other.
The procedure for computing these "inner" tangents is similar to the procedure for computing the "outer" tangents. We begin by letting be one of these tangents, that touches the first circle at
and the second at
. Let the point of intersection of
with
be denoted
. Then, right-angled
is similar to right-angled
. Let
and
. Then, by similarity, we see that
. Along with the equation
, we can solve:
. Then, letting
, we have
. Let
, and see that
, which, after some messy algebra, will turn out to be
. Also observe that
.
Moving along, we have as before. Defining
and
analogously, we obtain:
and likewise
Careful! The value of in this case is not the same as the value of
for the outer tangents.
Summary and discussion[edit]
We will summarize the results below. (Note that we have exchanged the two circles.) We define and
, and then the points of tangency of the two outer tangents with the first circle are given by:
and likewise for the two inner tangents:
The first pair of formulas will be invalid when , because
will be undefined. Obviously, in this case,
also, so
will also be undefined, and the second pair of formulas will be invalid.
When , we will obtain
, so
and
will coincide. The second pair of formulas will still be invalid, so we will obtain a total of one point of tangency.
When , we will obtain
, so
and
will be distinct, but
will still be undefined, so we obtain a total of two points of tangency.
When , we will obtain
giving two distinct points
, but
, a total of three points of tangency.
Finally, when , then
and all four points
will be distinct, as expected.