Path: utzoo!attcan!uunet!cs.utexas.edu!rice!uw-beaver!cornell!biar!trebor
From: trebor@biar.UUCP (Robert J Woodhead)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Line selection algorithims..
Message-ID: <989@biar.UUCP>
Date: 18 Dec 89 15:13:58 GMT
References: <8912160053.AA00720@cadman.nyu.edu> <981@biar.UUCP> <1043@maytag.waterloo.edu>
Organization: Biar Games, Inc.
Lines: 47

jb@aries5.uucp (James Bruyn) writes:

>That was my immediate thought to - gee how simple.  But then I realized
>that a line could be on a diagonal, and the enclosing rectangle would
>then be quite large.  So I think a more reasonable way would be
>to define a region around the line with some room for slop. i.e.

Jim, what do you think a Region is?  It is a structured grouping of
rectangles.  Such a region is going to be seriously huge and slow to check.
Sure, you are going to check the line rect often in the case of diagonals?
So what?  Given the start and end point it is a simple calculation to
determine how "close" the click is to the line.  Given:

Cx,Cy	Click X and Y
Sx,Sy	Line start X and Y
Ex,Ey	Line end X and Y
Lx,Ly	Points on Line near Cx,Cy (vertically or horizontally)
Slope	used in expressing line parametrically

	(This uses floating point math for simplicity but can be done
	 using fake fixed point very quickly)

	Note : assumes Sx<>Ex and Sy<>Ey, eg: diagonal line

	Note : off the top of my head, don't flame for stupid screwups!

Slope := (Ex-Sx) / (Ey-Sy);	{ slope of the line }
Ly    := Sy + ((Cy-Sy)*Slope);

Slope := (Ey-Sy) / (Ex-Sx);	{ slope expressed other way }
Lx    := Sx + ((Cx-Sx)*Slope);

if (abs(Lx-Cx)<CRITERIA) or (abs(Ly-Cy)<CRITERIA) then
   begin
      { hit code }
   end;

In this case the points Cx,Ly and Lx,Cy are the two points on the line
between Sx,Sy and Ex,Ey that are reached by travelling vertically (up
or down) or horizontally from Cx,Cy.  Since you want to be at most a
couple of dots away anyway, this is a good enough approximation.

-- 
Robert J Woodhead, Biar Games, Inc.   !uunet!biar!trebor | trebor@biar.UUCP
Announcing TEMPORAL EXPRESS.  For only $999,999.95 (per page), your message
will be carefully stored, then sent back in time as soon as technologically
possible.  TEMEX - when it absolutely, postively has to be there yesterday!