|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The intersection of two lines and in two dimensions with, containing the points and , and containing the points and , is given by
where denotes a determinant. This corresponds to simultaneously solving
for and . Other treatments are given by Antonio (1992) and Hill (1994). The intersections of two lines given in trilinear coordinates as
is
Pseudocode for segment intersection is given by de Berg et al. (2000). Three lines in trilinear coordinates
concur if their trilinear coordinates satisfy
in which case the point is
Three lines in Cartesian coordinates concur if the coefficients of the lines
satisfy
In three dimensions, the algebra becomes more complicated. The intersection of two lines containing the points and , and and , respectively, can also be found directly by simultaneously solving
together with the condition that the four points be coplanar (i.e., the lines are not skew),
for , eliminating and . This set of equations can be solved for to yield
where
(Hill 1994). The point of intersection can then be immediately found by plugging back in for to obtain
A slightly more symmetrical and concise form can obtained by additionally defining
where denotes a unit vector, then
(Goldman 1990). REFERENCES: Antonio, F. "Faster Line Segment Intersection. Ch. IV.6 in Graphics Gems III (Ed. D. Kirk). San Diego: Academic Press, pp. 199-202 and 500-501, 1992. Bentley, J. and Ottmann, T. "Algorithms for Reporting and Counting Geometric Intersections." IEEE Trans. Comput. C-28, 643-647, 1979. de Berg, M.; van Kreveld, M.; Overmars, M.; and Schwarzkopf, O. Computational Geometry. New York: Springer, pp. 19-29, 2000. Goldman, R. "Intersection of Two Lines in Three-Space." In Graphics Gems I (Ed. A. S. Glassner). San Diego: Academic Press, p. 304, 1990. Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products." Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994. Mehlhorn, K. and Näher, S. "Implementing a Sweep Line Algorithm for the Straight Line Segment Intersection Problem." n.d. http://www.mpi-sb.mpg.de/LEDA/articles/sweep.ps.gz. Prasad, M. "Exact Computation of 2-D Intersections." Ch. IV.4 in Graphics Gems II (Ed. J. Avro). Boston, MA: Academic Press, pp. 7-9, 1991. Prasad, M. "Faster Line Segment Intersection." Ch. IV.6 in Graphics Gems II (Ed. J. Avro). Boston, MA: Academic Press, pp. 7-9, 1991. CITE THIS AS: Weisstein, Eric W. "Line-Line Intersection." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Line-LineIntersection.html |
댓글
댓글 쓰기