Re: [Plib-users] Geometry library?

[Steve B. <sjb...@ai...>]

Marlin Mixon wrote:

> >You should be able to form a parametric equation for each line that takes
> >the value zero at one end of the line and 1.0 at the other...finding the
> >intersection in parametric space of infinite lines is then quite easy and
> >you can just test the value of the parameter for each line.
> 
> That sounds interesting, but I'm not familiar with the parametric techniques
> you are describing.  Do you mean like for the general
> form of the line AX + BY + C = 0, the parameters are A,B & C?  Or is it
> something completely different?

You can express a line as:

  x = x1 + p * dx
  y = y1 + p * dy
 
Where (x,y) is any point on the line, (x1,y1) is a point on the line and
(dx,dy) is the direction vector of the line.

If (dx,dy) is a unit vector then 'p' is just the distance of (x,y) from (x1,y1)
which is quite useful - but you don't *have* to make (dx,dy) be a unit vector,
you'd just wind up with different values of 'p' - right?

So, if you have a line *segment*  (x1,y1)...(x2,y2) and you say:

  dx = x2 - x1 ;
  dy = y2 - y1 ;

...then the parameter 'p' is no longer a 'distance' in normally understood
terms.  But (usefully), it is zero at (x1,y1) and 1.0 at (x2,y2) - it's negative
'before' (x1,y1) and >1 for points 'after' (x2,y2).  That's a useful thing to
know when you are doing intersection tests!

So, for two different lines A and B, you have:

  x = x1A + pA * dxA
  y = y1A + pA * dyA
  x = x1B + pB * dxB
  y = y1B + pB * dyB
 
...four equations with four unknowns: (x,y) the point at which they
intersect, pA and pB are the parameteric positions along each line at
which they intersect.

Solving those four equations (which is left as an exercise for the
reader - as all the best math books say), gets you pA and pB.

Now, you can just test pA and pB and if they are both in the range
0..1 then the line segments intersect - if either lies outside
that range - then they don't.  You don't even need to compute
(x,y) if you don't need to - but it drops out of the equations
very easily of you do.

> One feature about the sweep method that I found is it's more than just
> intersection, it also helps you considerably narrow down the lines to
> compare: normally you want to compare each line with every other line but
> the sweep method has you comparing neighbors based on a vertical sweep line,
> so the actual intersection determination is just one part of a solution.

Yes - there are other cute things you can do if you know more about the
problem than just "please intersect these two lines".

>  + <-   sorry, purring cat walked on the keyboard.

Hmmm - typical dumb cat  '+<-' ...plus is less than minus?? Geez! Get
a dog!

> Also, I will gladly contribute any code that I write that is within the
> scope of PLIB.

Excellent!

-- 
Steve Baker   HomeEmail: <sjb...@ai...>
              WorkEmail: <sj...@li...>
              HomePage : http://web2.airmail.net/sjbaker1
              Projects : http://plib.sourceforge.net
                         http://tuxaqfh.sourceforge.net
                         http://tuxkart.sourceforge.net
                         http://prettypoly.sourceforge.net
                         http://freeglut.sourceforge.net