🚀 go-pugleaf

paranand@cis.ohio-state.edu (murahi paranandi) writes:

>Hi,

>Is there a formula for the point of intersection (x,y,z) of lines
>(x1,y1,z1), (x2,y2,z2) and (x3,y3,z3), (x4,y4,z4) ?

>Thanks for you help!

In two dimensions, the following snippet of ML code might help you...
(I would give you my C code, but my thesis supervisor keeps telling me
that ML is far more elegant and space-efficient than C...)
(BTW: Naturally, ~ is negation in ML, because using - would result in
an overloaded operator)

fun ClipEdge line edge =
      let
	val EdgeData((x1, y1), (x2, y2)) = line
	val dy = y2 - y1
	val dx = x2 - x1

	val a = dy
	val b = ~dx
	val c = (y1 * x2) - (y2 * x1)

	val EdgeData((x1, y1), (x2, y2)) = edge
	val dist1 = (a * x1) + (b * y1) + c
	val dist2 = (a * x2) + (b * y2) + c
	
	val intersects = if Sign dist1 = Sign dist2 then false else true
	val intersects = (intersects) andalso
			 (dist1 <> 0.0) andalso (dist2 <> 0.0)
      in
	if intersects then
	  let
	    val ratio = Abs(dist1) / (Abs(dist1) + Abs(dist2))
	    val dy = y2 - y1
	    val dx = x2 - x1
	    val pointofintersection = (x1 + ratio * dx, y1 + ratio * dy)
     ...

(This code clips "edge" to the infinite extension of "line", but it's
reasonably easy to notice that the point does/doesn't lie within the bounds
of the line...)

It's using the formula "ax + by + c = 0" for the line, calculating the
a, b, and c coefficients for the line - then, by substituting the (x,y)
position of each of the two endpoints of the other line, you get
two "distance" values: 0 means the point lies on the line, and -ve and
+ve values indicate which side of the line the point lies on - if
the two values have the same sign, there is no intersection.

The ratio of one "distance" over the sum of distances gives the ratio
of the distance along the second line of the point of intersection...

You follow?

Extrapolating this into 3-d is left as an exercise for the reader ;-)
-- 
_________________  "I'd like to answer this question in two ways:
  /____ _ _/_ __       First in my normal voice, and then
 // / //_//_ /_/       in a silly, high-pitched whine." (Monty Python)

In article <1992Aug8.012801.17993@cis.ohio-state.edu> paranand@cis.ohio-state.edu (murahi paranandi) writes:
>Hi,
>
>Is there a formula for the point of intersection (x,y,z) of lines
>(x1,y1,z1), (x2,y2,z2) and (x3,y3,z3), (x4,y4,z4) ?
>
>Thanks for you help!

1) Parameterize the line equations:
 
   Line 1 = P1 + t (P2 - P1)           Line 2 = P3 + t (P4 - P3)

   Separating the components:

   x1 + t (x2 - x1)                     x3 + t (x4 - x3)
   y1 + t (y2 - y1)                     y3 + t (y4 - y3)
   z1 + t (z2 - z1)                     z3 + t (z4 - z3)

2) Pick one of the above and solve for t

   eg. set the equations for x to be equal:

   x1 + t (x2 - x1) = x3 + t (x4 - x3)

   ===> t (x2 - x1) - t (x4 - x3) = x3 - x1
   ===> t (x2 - x1 - x4 + x3) = x3 - x1
   ===> t = (x3 - x1) / (x2 - x1 - x4 + x3)

3) Use this value of t and substitute into one of the line equations.

Brian