Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!tut.cis.ohio-state.edu!rutgers!psuvax1!swatsun!jackiw
From: jackiw@cs.swarthmore.edu (Nick Jackiw)
Newsgroups: comp.sys.mac.programmer
Subject: Hit Check for Lines
Message-ID: <WJTN47C@cs.swarthmore.edu>
Date: 10 Aug 90 14:07:17 GMT
Sender: jackiw@cs.swarthmore.edu (Nick Jackiw)
Organization: Visual Geometry Project, Swarthmore College, PA
Lines: 84


Following up yesterday's discussion, I've heard from a number of
people who would like to see the algebra for testing if a line is
hit efficiently. Here it is.

-----
Hit Detection for Geometric Lines
Address questions or comments to
Nick Jackiw -> jackiw@cs.swarthmore.edu

My application involves several types of geometric objects--lines, rays,
segments, circles and polygons--and therefore prior to calling an object-
type-specific hitCheck I first check if the hit-point is within a bounding
rectangle of the object.  (This rectangle is computed when the object is
created, or when it is dynamically transformed.)  While the formulas below
apply to full geometric lines (infinitely extending), a preliminary 
bounding-rectangle check throws away hits which are on the line but off
the segment.  If your application uses segments, you'll have to make
a similar check before (or after) evaluating this formula.

Given point P(p,q)
      line L through two points (x1,y1), (x2,y2)

Test: Is the distance D from P to L less than k units?
      [You may want to let k=2 or even 3 so the user has some
       latitude in selecting the line]

[Terminology: |n|=absolute value of n
              n^m=n raised to mth power]

Let dX=x2-y1
    dY=y2-y1
    dP=p-x1
    dQ=q-y1

The distance between the P and the line is therefore

       |dQ*dX-dP*dY|
D=   -----------------
     sqrt(dX*dX+dY*dY)

So D<k for positive k is true if and only if

(dQ*dX-dP*dY)^2 < k^2(dX^2+dY^2)

which is true iff

(dQ*dX-dP*dY)-sqrt(k^2(dX^2+dY^2))<0

The entire second term is a constant unique to a line.  When the line is
created, allocate in its descriptor fields with values dX, dY, and
sqrt(k^2(dX^2+dY^2)).  These fields will not vary given different hit points.
Indeed, they will not vary if the line is translated.  Other transformations,
such as dilation, rotation, reflection, or lengthening/shortening *will*
alter these values and they will need to be recomputed.  (The bounding
rectangle discussed in the first paragraph will need to be recomputed after
*any* transformation to the line.)

During your hit-detection algorithm, to which these precomputed values are
available, you'll want to compute dQ and dP. Pseudocode:

{Inherits LinePt1, a point on the line, dX and dY, differentials between
any two points on the line, and HitCheck, a value set equal to 
round(sqrt(k^2(dX^2+dY^2)).}
   

	var dQ,dP:integer;
	    isLineHit:boolean;

          dQ:=HitPoint.y-LinePt1.y;
          dP:=HitPoint.x-LinePt1.x;
          isLineHit:=abs(dQ*dY-dP*dY)<HitCheck

          
That's it. Don't forget to update your dX,dY, and HitCheck when you transform
the line!

---------------

-- 
-----Nicholas Jackiw [jackiw@cs.swarthmore.edu|jackiw@swarthmr.bitnet]-----
"Here is how I built this artificial mine. I snatched a female louse from the
hair of humanity. I was seen to lie with her on three successive nights, and
then I flung her into the pit."       _Maldoror_, Canto II