 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 The intersection of two lines
where
for 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
together with the condition that the four points be coplanar (i.e., the lines are not skew),
for
where
(Hill 1994). The point of intersection can then be immediately found by plugging back in for
A slightly more symmetrical and concise form can obtained by additionally defining
where
(Goldman 1990).
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 |
and 
in two dimensions with, 
containing the points 
and 
, and 
containing the points 
and 
, is given by 
denotes a 
and 
. Other treatments are given by Antonio (1992) and Hill (1994). 
and 
, and 
and 
, respectively, can also be found directly by simultaneously solving 
![|x_1 y_1 z_1 1; x_2 y_2 z_2 1; x_3 y_3 z_3 1; x_4 y_4 z_4 1|=(x_3-x_1)·[(x_2-x_1)x(x_4-x_3)]=0](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_t5fMBwqyEslXcr8-FfQi0_K2TqkDB6b2IMcah9IX4cDGSuzeLRvynGqhzFSS_jPo2rPX5-pJ0AidpDCCNylNAH9DC--zagq4siaFshgQbr83-Ro8agfgTP_HA0KQzaWWJ3HneWHNHL_foaQwK8fsIhLgy04RfcNdxjnZ_V=s0-d)
, eliminating 
and 
. This set of equations can be solved for 
to yield 
to obtain 
denotes a 
댓글
댓글 쓰기