Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!rutgers!cbmvax!vu-vlsi!swatsun!jackiw From: jackiw@cs.swarthmore.edu (Nick Jackiw) Newsgroups: comp.sys.mac.programmer Subject: Re: Line selection algorithims.. Message-ID: Date: 18 Dec 89 16:06:44 GMT References: <8912160053.AA00720@cadman.nyu.edu> <981@biar.UUCP> <1043@maytag.waterloo.edu> Reply-To: jackiw@cs.swarthmore.edu (Nick Jackiw) Organization: Visual Geometry Project, Swarthmore College, PA Lines: 55 jb@aries5.UUCP (James Bruyn) writes: > In article <981@biar.UUCP> trebor@biar.UUCP (Robert J Woodhead) writes: > >deragon@CADMAN.NYU.EDU (John Deragon) 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. > assuming the line goes from lower left to upper right. > (left.h-3,left.v-3;, > right.h+3, right.h-3; > right.h+3, right.v+3; > left.h+3, left.v+3; > left.h+3, left.v-3) > and then checking whether the mouse in local coordinates is within the > region. Regions are essentially stored as composite rectangles, in a somewhat compressed format. (MacTutor once documented their internal structure.) Diagonal lines are composed of a number of rectangles proportional to the degree to which the slope of the line reaches 1 (in which each pixel requires a separate rectangle). A quick check reveals that a rgn containing the area defined by MoveTo(0,0) / LineTo(150,0) is 10 bytes--one rectangle because the line is horizontal--but the size of MoveTo(0,0) / LineTo(150,150) is 1212 bytes--over 1K of memory. This is a short line; longer lines take more space. Obviously, this is computationally dreadful... if your heap space is tight, you could even cause a scramble during selection, which will lead to miserable performance. I maintain that the most computationally efficient method is to check the bounding rectangle (which, I agree, gets progressive less useful the closer to slope=1 your line is), and--if the mouse point lies within it-- to calculate the distance between the point and the line in a mathematical fashion rather than in some Quickdraw-related one. I posted here three days ago a solution which required three integer multiplies and one integer subtraction per line to tell if a point was within some constant distance from a line. This is less overhead than *one* dispatch through the trap-table. Check your archives for the derivation. -Nick -- +-------------------+-jackiw@cs.swarthmore.edu / !rutgers!bpa!swatsun!jackiw-+ | nicholas jackiw | jackiw%campus.swarthmore.edu@swarthmr.bitnet | +-------------------+-VGP/MathDept/Swarthmore College, Swarthmore, PA 19081--+ "Ah...I've got this CHRONIC pain." _True Believer_