Computational geometry - Revision history

217.174.232.8: 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)

2014-04-11T06:14:40Z

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)

Brian: /* Summary and discussion */ - typo = should be >=

2011-12-21T07:41:08Z

‎Summary and discussion: - typo = should be >=

Brian: /* Circles */ - tangency

2011-12-20T01:50:13Z

‎Circles: - tangency

Brian: /* Lines */

2011-12-19T23:54:49Z

‎Lines

Brian: /* Intersection of a circle with a circle */

2011-12-19T23:22:30Z

‎Intersection of a circle with a circle

Brian: /* Two points of intersection */

2011-12-19T22:50:26Z

‎Two points of intersection

Brian: /* Lines */

2011-12-19T22:46:52Z

‎Lines

Show changes

Brian: /* Standard vector notation */ - show the arrow

2011-12-19T22:08:51Z

‎Standard vector notation: - show the arrow

Brian at 05:50, 31 May 2011

2011-05-31T05:50:38Z

Brian: /* The unit vector */ --- dotless i, j

2010-12-14T02:31:20Z

‎The unit vector: --- dotless i, j

@@ Line 303: / Line 303: @@
 ==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}</math> away from <math>(x_0, y_0)</math>. Therefore, we want <math>t = \frac{h}{A^2+B^2}</math>, and finally obtain <math>\left(x_0 - \frac{Bh}{A^2+B^2}, y_0 + \frac{Ah}{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}{A^2+B^2}, y_0 - \frac{Ah}{A^2+B^2}\right)</math>.
+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==

@@ Line 883: / Line 883: @@
 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 = 0</math> and all four points <math>P_1, P_2, P_3, P_4</math> will be distinct, as expected.
+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]]

@@ Line 794: / Line 794: @@
 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}}.)
 [[Category:Algorithms]]
 [[Category:Geometry]]
 [[Category:Pages needing diagrams]]

@@ Line 441: / Line 441: @@
 \end{array}
 </math>
 =Line segments=

@@ Line 772: / Line 772: @@
 ===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.
+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>.
 ===Two points of intersection===
 In all other cases, there will be two points of intersection.
 [[Category:Algorithms]]
 [[Category:Geometry]]
 [[Category:Pages needing diagrams]]

@@ Line 761: / Line 761: @@
 ===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. The algebraic method must be used to find these 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.
 ==Intersection of a circle with a circle==

@@ Line 638: / Line 638: @@
 ==Standard vector notation==
-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>.
+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==

← Older revision		Revision as of 05:50, 31 May 2011
Line 752:		Line 752:
	===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:Geometry]]
		+	[[Category:Pages needing diagrams]]

@@ Line 666: / Line 666: @@
 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{\mathbf{i}}</math>, and [0,1], denoted <math>\hat{\mathbf{j}}</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{\mathbf{i}} + v_y\hat{\mathbf{j}}</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