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 684: | Line 684: | ||
===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 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. | 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. | ||
Line 710: | Line 708: | ||
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: | 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> | :<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 | + | 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''. | ||
Line 735: | Line 733: | ||
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: | 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} \ | + | :<math>\mathbf{a} \cross \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: | 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> | :<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.) | (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 | + | 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. |
− | + | ||
− | + | ||
=Circles= | =Circles= |