Path: utzoo!attcan!uunet!aplcen!samsung!shadooby!netnews.engin.umich.edu!news
From: billkatt@mondo.engin.umich.edu (billkatt)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Line selection algorithims..
Message-ID: <1989Dec18.192617.10627@caen.engin.umich.edu>
Date: 18 Dec 89 19:26:17 GMT
References: <8912160053.AA00720@cadman.nyu.edu> <981@biar.UUCP> <1043@maytag.waterloo.edu> <L7GB0A2@cs.swarthmore.edu>
Sender: news@caen.engin.umich.edu (USENET News System)
Reply-To: billkatt@mondo.engin.umich.edu (billkatt)
Organization: Computer Aided Engineering Network (CAEN), University of Michigan
Lines: 48

In article <L7GB0A2@cs.swarthmore.edu> jackiw@cs.swarthmore.edu (Nick Jackiw) writes:
>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.
>
Just because the data structure is large doesn't mean the useage is
"computationally dreadful".  It does gobble memory, but to check whether a
point is inside or outside a region requires at max, x+y+1 bytes examined (where
x and y are the distance from the top and left of the bounding box.  This is
excluding the initial point in rect check.  This is cheap for most things,
since it doesn't involve any multiplication or division.

And I sincerely doubt you would get a heap scramble on just indexing through
a list.  You see, the regions are stored ahead of time, you don't make them
every time you need to check.  If you don't make any new data structures while
indexing through, you aren't going to get a scramble.

-Steve