From: tom burgess <tburgess AT drao DOT nrc DOT ca>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: ALLEGRO : check for Line intersecting a point . . . how?
Date: Fri, 22 Aug 1997 22:55:53 -0700
Organization: BCTEL Advanced Communications
Lines: 31
Message-ID: <33FE7B69.669@drao.nrc.ca>
References: <33f340d2 DOT 7053399 AT news DOT btinternet DOT com> <33F38369 DOT 606CE0E9 AT spectra DOT net>
NNTP-Posting-Host: pntn02m02-87.bctel.ca
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Tom Novelli wrote:
> 
> Thomas Harte wrote:
> >         I want to know in Allegro if a line I draw intersects a point I know. Is
> > there a way to do this using Allegro, or should I just implement my own line
> > algorithm? The reason I ask is that I am doing the level editor for my next
> > project, and obviously when you try to click and drag a line it would be
> > necessary for me to know which line you are attempting to click and drag . . .
> 
> I'll have to do the same thing in my 3D modeller, so I might as well
> work on it now.  I thought about comparing the line slopes, but linear
> interpolation is better in all ways.  I just find the line's y
> coordinate at the mouse's x coordinate, and vice-versa.  If these
> coordinates match the mouse coordinates, the mouse is on the line.
(had to cut a lot here - more included than new text problems)

An idea just occurred to me:
If the line from (x1,y1) to (x2,y2) has length L, at any point P on
the line, the sum of the lengths from P to each endpoint will be L.
If the point moves off the line, the sum increases (visualize a rubber
band between two pins being pulled by your finger)
Compute L**2 = (x1 - x2)**2 + (y1 - y2)**2 (total line length squared)
And LPsum = (x1 - xP)**2 + (y1 - yP)**2 +
	 (x2 - xP)**2 + (y2 - yP)**2 (sum distance from endpoints)
If (LPsum - L) is less than some tolerance, P is considered to be on the
line. Note that no branches are needed, other than the final comparison.
This should be good for Pentium optimization. Lengths of lines in the
database can be precomputed. No divisions are needed. Is there a flaw
here? Sounds reasonable to me.

	regards, tom (tburgess AT drao DOT nrc DOT ca)