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 writing, vectors are represented as letters with small rightward-pointing arrows over them, ''e.g.'', <math>\ | + | In writing, vectors are represented as letters with small rightward-pointing arrows over them, ''e.g.'', <math>\mathbf{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== | ==Basic operations== | ||
Line 764: | Line 739: | ||
===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 748: | ||
===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. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
[[Category:Geometry]] | [[Category:Geometry]] | ||
[[Category:Pages needing diagrams]] | [[Category:Pages needing diagrams]] |