Editing Computational geometry
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
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.<br/> |
− | + | 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.<br/> | |
− | 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.<br/> |
− | + | ||
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 76: | Line 73: | ||
==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?<br/> |
− | + | As it turns out, it is indeed possible.<br/> | |
− | 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:<br/> |
:<math> | :<math> | ||
\begin{array}{llll} | \begin{array}{llll} | ||
Line 94: | Line 89: | ||
</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.<br/> |
− | + | ||
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.<br/> |
− | + | ||
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 132: | Line 125: | ||
==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.<br/> |
− | + | ||
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 181: | Line 173: | ||
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.<br/> |
− | + | ||
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 240: | Line 231: | ||
==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.<br/> |
− | + | ||
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 253: | Line 243: | ||
<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.) <br/> |
− | + | ||
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 282: | Line 271: | ||
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''.<br/> |
− | + | ||
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 292: | Line 280: | ||
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>.<br/> |
− | + | ||
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. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Dropping a perpendicular== | ==Dropping a perpendicular== | ||
Line 317: | Line 298: | ||
\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.<br/> |
− | + | ||
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).<br/> |
− | + | ||
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 346: | Line 325: | ||
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>.<br/> |
− | + | <br/> | |
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.<br/> |
− | + | <br/> | |
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 365: | Line 344: | ||
</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.<br/> |
− | + | ||
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 391: | Line 369: | ||
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? | ||
− | + | <br/> | |
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 441: | Line 419: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
− | |||
− | |||
− | |||
=Line segments= | =Line segments= | ||
Line 663: | Line 638: | ||
==Standard vector notation== | ==Standard vector notation== | ||
− | In | + | In text, vectors are represented as letters with small rightward-pointing arrows over them, ''e.g.'', <math>\vec{v}</math>. We shall denote the components of <math>\vec{v}</math> as <math>v_x</math> and <math>v_y</math>. The magnitude of <math>\vec{v}</math> may be denoted simply <math>v</math>, or, to avoid confusion with an unrelated scalar variable, <math>\|\vec{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>\vec{0}</math>. |
==Basic operations== | ==Basic operations== | ||
Line 672: | Line 647: | ||
''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. | ''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==== | ====Of two vectors==== | ||
− | If we want addition to be associative too, then the sum <math>(P+\ | + | If we want addition to be associative too, then the sum <math>(P+\vec{u})+\vec{v}</math> must be the same point as <math>P+(\vec{u}+\vec{v})</math>. The first sum represents the point arrived at when the translations representing <math>\vec{u}</math> and <math>\vec{v}</math> are taken in succession. Therefore, in the second sum, we should define <math>\vec{u}+\vec{v}</math> in such a way so that it gives a vector representing the translation obtained by taking those of <math>\vec{u}</math> and <math>\vec{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>\vec{v}</math> is placed at the head of <math>\vec{u}</math>, the arrow drawn from the tail of <math>\vec{u}</math> to the head of <math>\vec{v}</math> is the sum. Again, the zero vector is the additive identity. |
===Negation=== | ===Negation=== | ||
− | For every vector <math>\ | + | For every vector <math>\vec{v}</math> we can identify a corresponding vector, denoted <math>-\vec{v}</math>, such that the translations represented by <math>\vec{v}</math> and <math>-\vec{v}</math> are inverse transformations. Another way of stating this is that <math>\vec{v}+(-\vec{v}) = \vec{0}</math>, or that <math>\vec{v}</math> and <math>-\vec{v}</math> have the same length but opposite directions. If <math>\vec{v} = [v_x,v_y]</math>, then <math>-\vec{v} = [-v_x,-v_y]</math>. |
===Subtraction=== | ===Subtraction=== | ||
====Of a vector from a point==== | ====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>\ | + | We define subtraction to be the inverse operation of addition. That is, for any point <math>P</math> and vector <math>\vec{v}</math>, we should have that <math>P+\vec{v}-\vec{v} = P-\vec{v}+\vec{v} = P</math>. Since the vector <math>-\vec{v}</math> represents the inverse translation to <math>\vec{v}</math>, we can simply '''add''' <math>-\vec{v}</math> to <math>P</math> to obtain <math>P-\vec{v}</math>. (Note that the expression <math>\vec{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==== | ====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>\ | + | 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>\vec{u}</math> and <math>\vec{v}</math> are placed tail-to-tail, then the vector from the head of <math>\vec{u}</math> to the head of <math>\vec{v}</math> is <math>\vec{v}-\vec{u}</math>, and ''vice versa''. Note that <math>\vec{u}-\vec{v} = -(\vec{v}-\vec{u})</math>. |
====Of a point from a point==== | ====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>. | 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=== | ===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. | 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. | ||
− | |||
− | |||
===Division=== | ===Division=== | ||
− | A vector can be divided by a scalar <math>\alpha</math> by multiplying it by <math>\alpha^{-1}</math>. This is | + | A vector can be divided by a scalar <math>\alpha</math> by multiplying it by <math>\alpha^{-1}</math>. This is denoted 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== | ==The unit vector== | ||
− | To every vector except <math>\ | + | To every vector except <math>\vec{v}</math> (except <math>\vec{v} = \vec{0}</math>), we can assign a vector <math>\hat{v}</math> that has the same direction but a length of one. This is called a ''unit vector''. The unit vector can be calculated as follows:<br/> |
− | + | <math>\hat{v} = \frac{\vec{v}}{\|\vec{v}\|}</math><br/> | |
− | + | ||
− | + | ||
==Obtaining a vector of a given length in the same direction as a given vector== | ==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>\ | + | Suppose we want a vector of length <math>l</math> pointing in the same direction as <math>\vec{v}</math>. Then, all we need to do is scale <math>\vec{v}</math> by the factor <math>\frac{l}{\|\vec{v}\|}</math>. Thus our new vector is<br/> |
− | <math>\frac{l}{\|\ | + | <math>\frac{l}{\|\vec{v}\|}\vec{v}</math>, which can also be written <math>l\frac{\vec{v}}{\|\vec{v}\|}</math> = <math>l\hat{v}</math>. Hence the unit vector is a "prototype" for vectors of a given direction. |
==Rotation== | ==Rotation== | ||
− | Given a vector <math>\ | + | Given a vector <math>\vec{v}\ [x,y]</math> and an angle <math>\theta</math>, we can rotate <math>\vec{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><br/> | |
− | + | <math>y' = x\sin\theta + y\cos\theta</math><br/> | |
The same formula can be used to rotate points, when they are considered as the endpoints of vectors with their tails at the origin. | 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== | ==Dot product== | ||
− | The ''dot product'' or ''scalar product'' is | + | The ''dot product'' or ''scalar product'' is defined as follows:<br/> |
− | + | <math>[a_x,a_y]\cdot[b_x,b_y] = a_x b_x + a_y b_y</math><br/> | |
− | + | The dot product has two useful properties. | |
First, the dot product satisfies the relation | First, the dot product satisfies the relation | ||
− | + | <math>\vec{a}\cdot\vec{b} = \|\vec{a}\| \|\vec{b}\| \cos\theta</math> | |
− | where <math>\theta</math> is the angle between <math>\ | + | where <math>\theta</math> is the angle between <math>\vec{a}</math> and <math>\vec{b}</math>. This allows us to find '''the angle between two vectors''' as follows:<br/> |
− | + | <math>\theta = \cos^{-1}\frac{\vec{a}\cdot\vec{b}}{\|\vec{a}\|\|\vec{b}\|}</math><br/> | |
− | 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 | + | 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. |
Second, the dot product can be used to compute ''projections''. | Second, the dot product can be used to compute ''projections''. | ||
===The vector projection=== | ===The vector projection=== | ||
− | The vector projection of <math>\ | + | The vector projection of <math>\vec{a}</math> onto <math>\vec{b}</math> is, intuitively, the "shadow" cast by <math>\vec{a}</math> onto <math>\vec{b}</math> by a light source delivering rays perpendicular to <math>\vec{b}</math>. We imagine <math>\vec{b}</math> to be a screen and <math>\vec{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>\vec{a}</math> onto <math>\vec{b}</math> is the foot of the perpendicular from the tail of <math>\vec{a}</math> to <math>\vec{b}</math>, and the head of the projection is likewise the foot of the perpendicular from the head of <math>\vec{a}</math>. The vector projection is a vector pointing in the same direction as <math>\vec{b}</math>. There is no standard notation for vector projection; one notation is <math>\operatorname{proj}_\vec{b}\,\vec{a}</math> for the projection of <math>\vec{a}</math> onto <math>\vec{b}</math>, and ''vice versa''. |
===The scalar projection=== | ===The scalar projection=== | ||
− | The scalar projection is the directed length of the vector projection. That is, if the angle between <math>\ | + | The scalar projection is the directed length of the vector projection. That is, if the angle between <math>\vec{a}</math> and <math>\vec{b}</math> is acute, then <math>\operatorname{proj}_\vec{b}\,\vec{a}</math> points in the same direction as <math>\vec{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}_\vec{b}\,\vec{a}</math> and <math>\vec{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}_\vec{b}\,\vec{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=== | ===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>\ | + | 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>\vec{a}</math> and <math>\vec{b}</math> tail-to-tail at the origin. Now rotate both vectors so that <math>\vec{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>\vec{a}</math> and <math>\vec{b}</math> is the scalar projection of <math>\hat{a}</math> onto <math>\vec{b}</math>, from the definition of the cosine function. By similar triangles, <math>|\operatorname{proj}_\vec{b}\,\vec{a}|</math> is <math>\|\vec{a}\|</math> times this. Therefore we find:<br/> |
− | + | <math>|\operatorname{proj}_\vec{b}\,\vec{a}| = \|\vec{a}\| \cos \theta = \|\vec{a}\| \frac{\vec{a}\cdot\vec{b}}{\|\vec{a}\|\|\vec{b}\|} = \frac{\vec{a}\cdot\vec{b}}{\|\vec{b}\|}</math><br/> | |
− | and ''vice versa''. | + | and ''vice versa''.<br/> |
− | + | To compute a vector projection, we notice that we need a vector with the directed length <math>|\operatorname{proj}_\vec{b}\,\vec{a}|</math> along <math>\vec{b}</math>. This is accomplished by scaling the unit vector <math>\hat{b}</math> by the value of the scalar projection:<br/> | |
− | + | <math>\operatorname{proj}_\vec{b}\,\vec{a} = \frac{\vec{a}\cdot\vec{b}}{\|\vec{b}\|}\hat{b}</math><br/> | |
− | To compute a vector projection, we notice that we need a vector with the directed length <math>|\operatorname{proj}_\ | + | |
− | + | ||
− | + | ||
− | + | ||
Two notes: first, projecting onto the zero vector is meaningless since it has no direction, and second, neither scalar nor vector projection is commutative. | Two notes: first, projecting onto the zero vector is meaningless since it has no direction, and second, neither scalar nor vector projection is commutative. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=Circles= | =Circles= | ||
Line 764: | Line 717: | ||
===Two points of intersection=== | ===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. | + | 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. The algebraic method must be used to find these points of intersection. |
− | + | ||
− | + | ||
==Intersection of a circle with a circle== | ==Intersection of a circle with a circle== | ||
Line 775: | Line 726: | ||
===One point of intersection=== | ===One point of intersection=== | ||
− | + | When the distance between the centres of the circles is exactly the difference between their radii, the two circles will be internally tangent. When the distance between the centres of the circles is exactly the sum of their radii, they will be externally tangent. | |
− | + | ||
− | + | ||
===Two points of intersection=== | ===Two points of intersection=== | ||
In all other cases, there will be two points of intersection. | In all other cases, there will be two points of intersection. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |