Path: utzoo!attcan!uunet!cbmvax!vu-vlsi!swatsun!jackiw
From: jackiw@cs.swarthmore.edu (Nick Jackiw)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Line selection algorithims..
Message-ID: <ZMDBHYY@cs.swarthmore.edu>
Date: 16 Dec 89 20:34:35 GMT
References: <8912160053.AA00720@cadman.nyu.edu>
Reply-To: jackiw@cs.swarthmore.edu (Nick Jackiw)
Organization: Visual Geometry Project, Swarthmore College, PA
Lines: 63

deragon@CADMAN.NYU.EDU (John Deragon) writes:
> 		I was wondering how the current applications like
> MacDraw, MacDraft...etc etc do the line selection. For example in 
> MacDraw you click on the line and it becomes selected? How does it 
> do this? What is it testing on mouseDown? 

Presumably you store you objects in some sort of list.  Rather than
check if each line is some pixel-distance close to the mouseDown
(which can get very expensive, if you have lots of lines in your
list), it's good to implement some sort of preprocessing. In
my object-manipulating program, each object has a HitZone:Rect
field, which is simply the minimal bounding box of that object.
So for any line segment between X1,Y1 and X2,Y2, SetRect(HitZone,
min(X1,X2),min(Y1,Y2),max(X1,X2),max(y1,y2)).

Then, once you've got the mouseDown, run through the list. If 
mousePt is in HitZone, then there's possibly a hit on this line.
At this point, you'll have to do some more cumbersome math. As
you may recall from school, the distance between is hairy. Rather
than rederive it all for you, I'll give you one--that seems to me
pretty computationally efficient--free.

Given: point P(p,q) / line L through 2 pts (x1,y1), (x2,y2)
Test:  is the distance D from P to L less than k units?

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

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

But sqrts and real divides are extremely costly, therefore continue

So D<k (k>0) iff
|dQdX-dPdY|^2<k^2(dX^2+dY^2)

which is true iff
((dQdX-dPdY)^2-k^2(dX^2+dY^2)<0.

The cool thing about this is that the whole right term (k^23(dxdx+dYdY))
is constant for each line.  That means you can work it out just once,
when the line is drawn, and then when you're paging through the list
of objects, you'll only have to compute the left term and compare it to
the stored term.

Of course, be sure to recalculate the stored term if you reorient the line.
Also note that this treats the line as a geometric line (extending to
infinity in both directions), so it will register false hits if your line
is only a ray or a segment. Fortunately, if you FIRST decide whether the
line could possibly be hit by checking if the mouseDown was in the HitZone,
then you'll clip out all possible hits except those on the segment.
(My program is a geometry program which uses segs, rays, and lines; so
I needed this flexibility. Somebody else may be able to derive a 
quicker way to check if you're limited to segments.)

Hope this helps.

-Nick


-- 
     _  _|\____    Nick Jackiw | Visual Geometry Project | Math Department
   / /_/   O>  \   ------------+-------------------------+ Swarthmore College
   |       O>   |  215-328-8225| jackiw@cs.swarthmore.edu| Swarthmore PA 19081
    \_Guernica_/   ------------+-------------------------+                 USA