yahnke@vms.macc.wisc.edu (Ross Yahnke, MACC) (08/09/90)
In programming a MacDraw style environment where the
user can click-n-drag objects around, it's ez enuf to grab
objects with mass like squares and rectangles. You just see if
the clicked on pixel is in any of the regions defined by the
objects, i.e., you do a "PtInRgn()" call.
But what if the object is a line? Can a region be defined to
be a line, w/no thickness? I'm posting this for a friend who
said he tried creating a region w/only a line in it and
subsequent PtInRgn calls would fail... any ideas?
>>> yahnke@macc.wisc.edu <<<jackiw@cs.swarthmore.edu (Nick Jackiw) (08/09/90)
yahnke@vms.macc.wisc.edu (Ross Yahnke, MACC) writes: > In programming a MacDraw style environment where the > user can click-n-drag objects around, it's ez enuf to grab > objects with mass like squares and rectangles. You just see if > the clicked on pixel is in any of the regions defined by the > objects, i.e., you do a "PtInRgn()" call. > > But what if the object is a line? Can a region be defined to > be a line, w/no thickness? I'm posting this for a friend who > said he tried creating a region w/only a line in it and > subsequent PtInRgn calls would fail... any ideas? > > >>> yahnke@macc.wisc.edu <<< This has been gone over a couple of times in the past, and there are two basic approaches which seem wise. Regions are definitely *not* wise: a region, internally, can be thought of as a list of rectangles which define the space enclosed. (This isn't quite accurate, but it's sufficient...) Thus, while regions can efficiently model horizontal and vertical lines (one rectangle, the length of the line by its pixel width in dimension), diagonal lines can give rise to regions which consist of hundreds of single-pixel rectangles. Horribly memory inefficient, and not the sort of data structures you want to create on the fly every time your user clicks the mouse. The two basic approaches, bitmap inclusion and algebraic solution, differ in their appeal. The former offers elegant consistency and broad applicability; the latter is the fastest and most memory-efficient. Before describing them, let me note a few terms which are relevant to both solutions. You presumably have an object list (or array, or whatever), which may or may not be ordered, describing all the objects in your window. You have your hit, a Quickdraw point expressed in the same coordinate system as your object list. And you may want to have some slop--a pixel tolerance for hits so that if I hit one or two pixels off the line I can still select it. Bitmap Inclusion This is Larry Rosenstein's favored approach. Calculate a rectangle about your hit-point which is as wide and high as your desired slop: say 3 pixels square. Now allocate an offscreen bitmap with these dimensions. (Or better, allocate it in your application's initialization stage, and simply substitute this new rectangle for its bounds field when you get a hit.) Substitute this bitmap for your window's (with SetPortBits), and erase it. Now draw every object in your object list with a solid black pattern. This will be quite speedy, in that Quickdraw will realize that most of them lie outside of your portBits and not draw them at all. After drawing each object, check the actual bit-image you've allocated in the bitmap. (For a 3x3 rectangle, this data need only be six bytes long.) If any bit has been set--i. e. if Quickdraw has drawn your most recent object within a tiny rectangle representing the user's hit--than that object is hit; select it. The main advantage of this method is that it works for all types of objects. If Quickdraw can draw it, bitmap inclusion will tell you if the user's hit it. Algebra Alternately, you can calculate the distance from the point to the line, and determine whether it is less than your maximum slop tolerance. The formula for the distance between point (q,r) and a line passing through points (x1,y1) and (x2,y2) is: |(q-y1)(x2-x1)-(p-x1)(y2-y1)| ----------------------------- sqrt[(x2-x1)^2+(y2-y1)^2] which, if you precalculate the invariant portions and store them with the object can reduce to two integer multiplications and a few subtractions in your hit-check loop. The disadvantage of this method is that you have to implement separate arithmetic for each type of object; consequently, there's more code to maintain and more potential bugs to crop up. However, algorithms for all quickdraw objects (points, lines, circles, ovals, arcs, and polygons) are available in any basic Computational Geometry text; most of them are probably in an Algebra I text; and they will be consistently faster and take up less run-time memory than the bitmap inclusion method. I prefer the algebraic solution, but then my program tends to have windows with several hundred objects in it so speed is more important than elegance to my situation. Give a holler if you want source code for algebraic stuff; someone else can probably provide a working example of bitmap inclusion. -Nick -- -----Nick Jackiw [jackiw@cs.swarthmore.edu|jackiw@swarthmr.bitnet------ "This orbe of starres fixed infinitely vp extendeth hitself in altitvde sphericallye, and therefore immovable the pallace of foelicity garnished with perpetvall shining glorious lightes innvmerable." - Thomas Digges
lsr@Apple.COM (Larry Rosenstein) (08/10/90)
In article <89RN1MB@cs.swarthmore.edu> jackiw@cs.swarthmore.edu (Nick Jackiw) writes: > >Bitmap Inclusion > >This is Larry Rosenstein's favored approach. Calculate a rectangle about Only because I don't remember enough analytic geometry to compute the distance to most shapes. Also, the mathematical approach gets complicated when you start dealing with arbitrary polygons or curves. >your hit-point which is as wide and high as your desired slop: say 3 pixels You can also account for slop by drawing the objects a bit bigger than normal. >square. Now allocate an offscreen bitmap with these dimensions. (Or better, Remember that a bitmap's rowbytes must be even. I used a bitmap that was 16 bits wide an 1 bit high. >rectangle, this data need only be six bytes long.) If any bit has been >set--i. e. if Quickdraw has drawn your most recent object within a tiny >rectangle representing the user's hit--than that object is hit; select it. Normally objects are drawn back-to-front, which means that the last one over the mouse point is the one that should be selected. If your data structure allows you to scan in reverse order then it would be the first one. >most of them are probably in an Algebra I text; and they will be >consistently faster and take up less run-time memory than the bitmap It's not clear to me that they take up less memory, especially, if you have several kinds of shapes. You need only one piece of code for the bitmap approach vs. one for each kind of shape. Each of those calculations will require a comparable amount of code. Also, part of the code to implement the bitmap approach will be the normal drawing code, which you need anyway. >Give a holler if you want source code for algebraic stuff; someone else >can probably provide a working example of bitmap inclusion. You can get my code along with the "Programming with MacApp" book (the diskette is also available separately). It's written in the context of my drawing building block, but the key piece of code should be usable in other programs. I think the key method is listed in the book, so you don't even need the diskette. I would like to see the algebraic code and compare the speed of the two. I'm not sure that it's going to be faster than the bitmap approach. -- Larry Rosenstein, Object Specialist Apple Computer, Inc. 20525 Mariani Ave, MS 46-B Cupertino, CA 95014 AppleLink:Rosenstein1 domain:lsr@Apple.COM UUCP:{sun,voder,nsc,decwrl}!apple!lsr
sund@tde.lth.se (Lars Sundstr|m) (08/10/90)
In article <4176@dogie.macc.wisc.edu> yahnke@vms.macc.wisc.edu (Ross Yahnke, MACC) writes: >In programming a MacDraw style environment where the >user can click-n-drag objects around, it's ez enuf to grab >objects with mass like squares and rectangles. You just see if >the clicked on pixel is in any of the regions defined by the >objects, i.e., you do a "PtInRgn()" call. > >But what if the object is a line? Can a region be defined to >be a line, w/no thickness? I'm posting this for a friend who >said he tried creating a region w/only a line in it and >subsequent PtInRgn calls would fail... any ideas? > >>>> yahnke@macc.wisc.edu <<< It's possible to calculate the distance between the line and the click point by using the vector product of the line and the vector between the click point and a endpoint of the line. Define A=(Ax,Ay) as a vector between the startpoint and endpoint of the line and B=(Bx,By) as a vector between the startpoint of the line and the clickpoint. Now, there is a nice relationship that can be used: |A x B| = |A| |B| sin(alfa) The angle alfa is the angle between the vectors and therefore, the distance between the line and the clickpoint is |B| sin(alfa). But according to the relationship above |B| sin(alfa) is equal to |A x B| / |A| which is pretty simple to calculate because |A x B| = abs(Ax By + Ay Bx) and |A| = sqrt(sqr(Ax) + sqr(Ay)) Because you get the distance to the line you can define your own click margin. With the formulas above you get away with 4 multiplications, 1 division, 2 additions and and square root. If you think the square root eats to much computer power then square both the distance and the click margin. I think that this approach saves both computer power and memory compared to the Point-In-Region-approach. Lars