> I now realize what the problem is (and I should have remembered it, as it's
> fooled me in the past): Trace's 'direction' vector is solely a *direction*; it
> doesn't actually correspond to any particular point in space--like the end of
> 'line 1' in my example. It never changes. So by using this scheme and, for
> example, varying trace's 'shoot-from' point but NOT its 'direction', the
> direction it shoots in always remains 'parallel to itself', if that makes any
> sense.

Sorry it doesn't make sense to me.

If you've got line 1 defined by two end points, A and B, and line 2 
defined by two end points C and D then I would have thought the 
following would work:

Define a cylinder between points A and B with a small radius.

Use the trace command to trace from point C in direction (D-C) with the 
cylinder object. Check if there is a hit point within the length of line 
2. If no hit then trace again from point D with direction (C-D) and 
check again the hit point.

Post a reply to this message

"H. Karsten" <h-karsten()web.de> wrote:
> Hi people :)
> I have two lines and like to have there intersection-point.
>
> Like
> <Line_1_Start_X,Line_1_Start_y> to <Line_1_End_X,Line_1_End_Y>
> and
> <Line_2_Start_X,Line_2_Start_y> to <Line_2_End_X,Line_2_End_Y>
>
> And I like to get <Intersection_X,Intersection_Y>
>
> Is there any formula, coming with the PovRay-Inc-Files, like Math.inc, I can
> use?
>
> Or does someone have a quick way to solve this?
>
> Tanx,
> Holger :)

OK, if it is a pair of 2d lines, you just need to solve for the two line
equations, then solve for the intersection:

General 2-d line equation is "y = mx + b"

LINE 1
     P11 = <x11,y11>
     P12 = <x12,y12>

Solve slope (m):
     m1 = (y12-y11)/(x12-x11)

Solve intercept (b):
     b1 = y11 - m1 * x11

LINE 2
     P21 = <x21,y21>
     P22 = <x22,y22>

Solve slope (m):
     m2 = (y22 - y21) / (x22 - x21)

Solve intercept (b):
     b2 = y21 - m2 * x21

Now solve the two line equatins for 'x' and 'y':

xi = (b2 - b1) / (m1 - m2)
yi = m1 * xi + b1

Intersection point: Pi = <xi,yi>


Or to really simplify it, we can combine all of the above and get formulae to
solve directly for x and y from the points:

xi =
[(x21-x22)*(x11*y12-x12*y11)+(x11-x12)*(x22*y21-x21*y22)]/[(x21-x22)*(y12-y11)+(x11-x12)(y21-y22)]

yi = (xi-x11)*(y12-y11)/(x12-x11)+y11


As I have already noted, this only works in 2-space.  In 3-space (x,y,z) it is
not as simple, lines have parametric equations, rather than direct functions
(surfaces like planes have functions), and lines will not always intersect, in
fact it would be very rare that that do: imagine picking 2 sets of random points
in a room and tying a piece of string between each, they are not likely to
intersect.  In 3-space, the best equivalent is the closest points between the
lines.  This can also be solved using algebraic equations (need to solve for
various plane functions, and find the intersection of three planes) which I am
not going to go into at present.  Note: if the closest distance between the two
points is 0, they actually intersect (i.e., they are the same point
coordinates).

-tgq
-tgq

Post a reply to this message

> OK, if it is a pair of 2d lines, you just need to solve for the two line
> equations, then solve for the intersection:
>
> General 2-d line equation is "y = mx + b"

That doesn't work if one of the lines is between (eg) (4,4) and (4,12), 
because you won't be able to calculate "m". Also you need to check that 
the intersection point actually lies on both lines (and not beyond 
either of them).

Better to do it parametrically, so a 2D vector point on the line is 
given by p1 + a.(p2-p1) where a is the variable you're trying to find 
and p1 and p2 are the two end points of the line.

If you equate a point in this form on the two lines you essentially need 
to then solve for a and b, then you can simply check if a and b are in 
the range 0-1 to see if the point is actually on the lines:

p1 + a(p2-p1) = p3 + b(p4-p3)

I find it easiest (ie least likely to make a mistake in any equation 
rearranging!) to solve this type of equation by doing it as a matrix 
inversion (assume p1,p2 etc are column vectors):

[p1-p3] = [p1-p2 p4-p3][a]
                        [b]

[a] = [p1-p2 p4-p3]^-1 [p1-p3]
[b]

Also note up until here there is no assumption that p1,p2 are 2D, they 
could be 3D or 4D and it still works.

Post a reply to this message

Am 15.02.2013 15:24, schrieb Trevor G Quayle:

> OK, if it is a pair of 2d lines, you just need to solve for the two line
> equations, then solve for the intersection:
>
> General 2-d line equation is "y = mx + b"

... and isn't as general as would be desirable, because it doesn't work 
for vertical lines.

> Or to really simplify it, we can combine all of the above and get formulae to
> solve directly for x and y from the points:
>
> xi =
>
[(x21-x22)*(x11*y12-x12*y11)+(x11-x12)*(x22*y21-x21*y22)]/[(x21-x22)*(y12-y11)+(x11-x12)(y21-y22)]

That's a clean, nice & safe term. Note how the denominator is fully 
symmetric with respect to both x vs. y as well as line 1 vs. line 2, 
indicating that there won't be any problems with vertical lines.

> yi = (xi-x11)*(y12-y11)/(x12-x11)+y11

Better use the term symmetric to the one used for xi, i.e.:

yi = 
[(y21-y22)*(y11*x12-y12*x11)+(y11-y12)*(y22*x21-y21*x22)]/[(y21-y22)*(x12-x11)+(y11-y12)(x21-x22)]

(Note that the denominator term is the same as for xi except for the 
sign, so you can save a few computations there.)

While this requires a few more computation steps, it avoids the problem 
of vertical lines once again, and gives more precise results for 
near-vertical lines.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 15.02.2013 15:24, schrieb Trevor G Quayle:
> > Or to really simplify it, we can combine all of the above and get formulae to
> > solve directly for x and y from the points:
> >
> > xi =
> >
[(x21-x22)*(x11*y12-x12*y11)+(x11-x12)*(x22*y21-x21*y22)]/[(x21-x22)*(y12-y11)+(x11-x12)(y21-y22)]
>
> That's a clean, nice & safe term. Note how the denominator is fully
> symmetric with respect to both x vs. y as well as line 1 vs. line 2,
> indicating that there won't be any problems with vertical lines.
>
> > yi = (xi-x11)*(y12-y11)/(x12-x11)+y11
>
> Better use the term symmetric to the one used for xi, i.e.:
>
> yi =
>
[(y21-y22)*(y11*x12-y12*x11)+(y11-y12)*(y22*x21-y21*x22)]/[(y21-y22)*(x12-x11)+(y11-y12)(x21-x22)]
>
> (Note that the denominator term is the same as for xi except for the
> sign, so you can save a few computations there.)
>

No need to even do that.  You can leave the denominator the same and simply swap
only the (x21-x22) & (x11-x12) in the numerator to the equivalent ys:

[(y21-y22)*(x11*y12-x12*y11)+(y11-y12)*(x22*y21-x21*y22)]/[(x21-x22)*(y12-y11)+(x11-x12)(y21-y22)]

In this case both denominators are the same.  (If you notice, in your version in
the numerator, the second terms are the same as well except for the swapped
sign)

You do also need to watch for non-intersecting lines (i.e. parallel).  Parallel
lines can be recognized by the above formulation as when the denominator
[(x21-x22)*(y12-y11)+(x11-x12)(y21-y22)] is equal to zero (divide by zero).

If the lines are finite in length (only exist between the defined points), then
once the intersecton is solved, it is simply a matter of checking that the x
intersect lies between the x endpoints of both lines (or y).


For the general "y=mx +b" formulation, I did forget about the vertical line
situation, howver the solution would be quite simple as you would already know
the x intercept and would only need to solve the other, non-vertical line for
the 'y' intercept.



-tgq

Post a reply to this message

Trevor G Quayle <Tin### [at] hotmailcom> wrote:
> Solve slope (m):
>      m1 = (y12-y11)/(x12-x11)

Note that there's a formula that does not cause any division by zero
because of the lines being vertical.

-- 
                                                          - Warp

Post a reply to this message

> "Samuel Benge" <stb### [at] hotmailcom> wrote:
>
>> scott <sco### [at] scottcom> wrote:
>>> ...or do it numerically by using the trace function. You could define
>>> one of the lines as a very thin cylinder, then do a trace from the start
>>> point of the 2nd line towards its end point.
>>
>> Or for more accuracy, make one line a plane. Use VPerp_To_Vector or
>> Point_At_Trans to align the plane along the line and translate it to one of its
>> endpoints. Then use trace(). I do that every time I need to find a line
>> intersection and it works perfectly. Also, using trace()'s fourth parameter
>> helps make sure you get an intersection: if the ray hits nothing (the normal is
>> <0, 0, 0>) then just reverse its direction.
>
> I guess this assumes that the two lines DO lie on the same plane.
>
> But wouldn't using trace() require essentially an infinite number of trace
> points, so that trace doesn't 'miss' the intersection? Or is it an iterative
> approach--i.e., when the returned trace point is 'close' to the target spot,
> then trace is used again, but restricted to that smaller vicinity (and so on)? I
> can see that working successfully, to a certain precision; but it doesn't seem
> possible to find the *exact* point of intersection (without infinite trace
> rays.) In a practical sense, though, an exact match might not be necessary.
>
>
>
>

A single trace call should be enough in most cases, at most two.
You call the trace from a point along one of the lines toward another 
point on that same line. You replace the second line by a thin cylinder.

Post a reply to this message

That all very cool folks :)

Yesterday I did a cheat-version:

//###########################################
camera {
location  <0,0,-4>*5
direction 1.5*z
right     x*image_width/image_height
look_at   0
}

light_source{<-1,1,-1>*30 color rgb 1}
default{pigment{color rgb 1}}

#declare P1=vrotate(<2,3,0>,z*clock*360);
#declare P2=vrotate(<6,-4,0>,z*clock*360);
#declare P3=vrotate(<5,5,0>,z*clock*360);
#declare P4=vrotate(<-2,-6,0>,z*clock*360);

#declare T=16;
cylinder{P1,P2,1/T}
cylinder{P3,P4,1/T}
cylinder{x*-10,x*10,1/T}
cylinder{y*-10,y*10,1/T}

#macro Intersect(P1,P2,P3,P4)
#local TO=cylinder{P1,P2,1/999999}
trace(TO,P3,P4-P3)
#end

sphere{Intersect(P1,P2,P3,P4),1/8}
torus{.8,1/32 rotate x*90 translate Intersect(P1,P2,P3,P4)}
//###########################################


All right that doesn't count - but it works ;)
Holger

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> > I now realize what the problem is...
>
> Sorry it doesn't make sense to me.
>

It *is* a bit of a brain-twister, I admit.

The situation is probably best illustrated by a simple test scene.  (It took a
test *animation* for me to clearly see it; but here it's just a static scene.)
And I've arranged things in an even simpler way than might occur normallly, for
clarity: the two lines (which naturally have to be on the same plane for an
intersection to even occur, statistically speaking) are both on the vertical
plane running through the origin, -x to +x.

While *special* values can be chosen for both lines' end points to produce
a trace that looks like a perfect 'hit' at the intersection, it's not really
so.

The wild card is trace's shoot-from point (which represents any arbitrary
beginning point of the non-target line.) If that value is anything other than a
'special case', the found point (the traced point) doesn't coincide with the
true intersection. That's because of the unchanging nature of trace's
'direction' vector. (BTW, trace 'normalizes' that vector, I think.)

The RED cylinder is the target line; ORANGE is the other line (where trace
starts, and with the unchanging end point used as trace's 'direction');
GREEN is the *actual* trace direction--which almost never coincides with the
orange line.

Plug in different values for the orange line's y ('trace_shoot_from') to see
what happens; this represents any naturally arbitrary value for that line's
start point. You might also see the 'parallel' concept I mentioned (more easily
seen with an orthgraphic camera placed in -z).

The real key to understanding all this is that trace's 'direction' vector
doesn't automatically/dynamically change to always point at a particular
location in space.

------
global_settings {assumed_gamma 2.2}

camera {
  perspective
  location  <-4, 8, -20>
  look_at   <8, 0,  0>
  right     x*image_width/image_height
  angle 67
}

light_source {
  <0, 0, 0>
  color rgb <1, 1, 1>
  translate <-30, 30, -30>
}

light_source {
  <0, 0, 0>
  color rgb <1, 1, 1>
  translate <30, 30, -30>
}

background{rgb .7}

plane{y,0 pigment{rgbt <.8,.9,1,.3>}}

// ----------------------------------------
// RED--The 'target' line
#declare target_line_start_point = <5,-12,0>;
#declare target_line_end_point = <9,10,0>;

// ORANGE--the other line. These are the start and end points, which
// are also used in trace().
#declare trace_shoot_from = <-2,9,0>;
#declare trace_direction = <18,-8,0>; // i.e., the line end point

#declare norm = <0,0,0>;

#declare target_object =
cylinder{target_line_start_point,target_line_end_point, .2}

#declare found_position =
trace(target_object,trace_shoot_from,trace_direction,norm);

// A sphere to indicate the found position. (If this ends up AT the
// origin, then the trace ray has totally missed the target line.)
#if(vlength(norm) !=0)
sphere{0,.35
no_shadow
pigment{rgb 1*<.3,1,1>}
translate found_position
}
#else
#end

// RED--the 'target' cylinder
object{target_object
no_shadow
pigment{rgb 1*<1,.3,.3>}
}

// ORANGE--The other line--which might be imagined to be the trace
// ray direction, but is not.
cylinder{trace_shoot_from,trace_direction, .1
no_shadow
pigment{rgb 1*<1,.7,0>}
}

// GREEN--this CORRECTLY illustrates the trace ray direction...
cylinder{trace_shoot_from,found_position, .1
no_shadow
pigment{rgb 1.2*<.3,1,0>}
}

// the origin axes
union{
// X axis
cylinder{-40*x,40*x,.05}
// Y axis
cylinder{0,3*y,.05}
// Z axis
cylinder{-5*z,5*z,.05}
 no_shadow
 pigment{rgb .3}
}

Post a reply to this message

"Kenneth" <kdw### [at] gmailcom> wrote:
> "Samuel Benge" <stb### [at] hotmailcom> wrote:
> > Or for more accuracy, make one line a plane.
>
> I guess this assumes that the two lines DO lie on the same plane.

Haha, yeah. Usually when I need to find a line-line intersection, my lines
aren't all wild and going whatever-which-way; they are already laying along the
same plane.

Sorry if that sent you off on a tangent!

Post a reply to this message