"Kenneth" <kdw### [at] gmailcom> wrote:

>
> But wouldn't using trace() require essentially an infinite number of trace
> points, so that trace doesn't 'miss' the intersection?

Oops, it occurred to me that I was thinking about purely 'mathematical' lines
(and maybe incorrectly at that.) If the two lines (or even one) are replaced
with actual cylinders--just temporarily, as test objects--then a *single* trace
would work very well, using your scheme.

Post a reply to this message

"Samuel Benge" <stb### [at] hotmailcom> wrote:

>
> 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().

It might be even easier, no V_Perp_To_Vector or Point_At_Trans needed : Let the
trace's initial 'position' (its "shoot-from" point) be the beginning point of
one line (call that the 1st line); then make a small-diameter cylinder for the
2nd line; then shoot a single trace ray toward the 1st line's end point (which
would be trace's "trace direction.") Voila! Trace will either hit the 2nd-line
cylinder and return its position, or it will not (and return <0,0,0> for the
normal--in which case, the two lines don't actually intersect.) The only
remaining detail is to add the cylinder's radius to the found point, for a
precise result. (Which will take some extra math, as the cylinder alignment will
most likely not be *perpendicular* to the trace ray; but using a *very
small*-diameter cylinder may make that computation unnecessary, from a practical
standpoint.)

Post a reply to this message

"Kenneth" <kdw### [at] gmailcom> wrote:

> It might be even easier...

This works; but I forgot to specifically mention that the 2nd 'line' (the
cylinder) is the object that's put into the trace() command, for it to work on;
perhaps that was obvious.

> ...but using a *very small*-diameter cylinder may make that computation
> unnecessary, from a practical standpoint.)

I've found that there's actually a limit to how small the radius can be. Trace()
has a problem working with an object below about six least-significant digits in
size. (Like, .000001) Seems to depend on the particular direction vector used.
Probably a result of ONE of trace's <x,y,z> computations dropping below a
certain precision 'threshold',

Post a reply to this message

> It might be even easier, no V_Perp_To_Vector or Point_At_Trans needed : Let the
> trace's initial 'position' (its "shoot-from" point) be the beginning point of
> one line (call that the 1st line); then make a small-diameter cylinder for the
> 2nd line; then shoot a single trace ray toward the 1st line's end point (which
> would be trace's "trace direction.") Voila! Trace will either hit the 2nd-line
> cylinder and return its position, or it will not (and return <0,0,0> for the
> normal--in which case, the two lines don't actually intersect.)

That's exactly what I suggested in my post :-) Sorry if it wasn't clear.

Post a reply to this message

scott <sco### [at] scottcom> wrote:

>
> That's exactly what I suggested in my post :-) Sorry if it wasn't clear.

Sorry; I was concentrating on Sam's post, and my mind went blank on everything
else  :-/

But unfortunately (maybe for both of us), the 'simpler' method, as I called it,
doesn't work. Actually, it *did* work in my initial test, but I didn't pay close
enough attention to what I was seeing.

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. Like your hand with a stiff finger pointing out, while moving the hand up
and down. So trace *might* hit the test cylinder--but that's an extremely
special case; and trace's returned result may not even correspond to the lines'
true intersection point (as I found out.)

So it seems that Sam's method is *definitely* the better one. ;-)

Post a reply to this message

> 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