Re: [Plib-users] Geometry library?

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

Marlin Mixon wrote:
> 
> I needed to compute 2-D line segment intersections.  I looked through plib
> and saw some 3D intersection routines, but no 2D. 

Well, it *is* a 3D library!...If you see a 3D routine that does what you want,
can't you just use the 3D version and just set all the Z coordinates to zero?

But the routine that I recollect in PLIB/SG does *infinite* line versus
*infinite* line...so you need to do a little more:

  Step 1: Intersect two *infinite* lines to find the intersection point.

  Step 2: Does that point lie between the end-points of both lines?

So, if you have the endpoints of your two line segments:

  1) Use sgIsectInfLineInfLine (or a make a 2D version of it) to compute the
     intersection point.

  2) For 2D lines, it's enough to ask whether the X coordinate of that
     point lies between the X coordinates of the ends of both lines...but
     for numerical precision reasons with near-vertical lines, you probably
     ought to check that the Y coordinate also lies between the Y coordinate
     of the end-points.

  3) Contribute the resulting function to the library (please!).

Things are a little simpler for 2D lines than for 3D because you *know*
that two infinite 2D lines will definitely intersect (unless they are
parallel).

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.

-- 
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