MROBINSON@wash-vax.bbn.com (06/24/89)
First, the wish. How about selecting one (or two) clipboard devices as standard places to put clipped text (in IFF format)? And, in particular, extend the standard Commodore shell so a user can copy to and paste from these clipboard device units! My most common use for the clipboard would be to copy and paste text between shell windows, which I do all the time on the Sun. The reason I mention two clipboard device units (sorry about the improper "clipboard devices" earlier) is that very often it is handy for me to have one long-term clip and one short-term clip. As an example, when I use the debugger (on the Sun at work), I frequently want to watch a structure as I change various components of it, but occasionally I need to look at other variables as well. So, I use one clip for the command to display the structure, and the other to copy the (potentially long) names of the other variables down to display them, too. It speeds up the process of debugging quite a bit, and it irks me that while the Amiga has the ability to handle multiple clipboards, not even the standard shell will use them! Now, re: clicking on irregular shapes. Basically, I agree with Matt, but I want to illustrate further. Suppose you have 50 or so separate areas for the user to click on (like a map of the countries in North America). I suspect that if you make each one a gadget, Intuition will have to search through a linear list of those gadgets, doing a rectangular boundary check until it finds a gadget the point falls into, then translate the point into the coordinates of the mask, then check the mask. It may need to check several masks before it finds the right one. But the important point is that on average, you'll do boundary checks for half the gadgets, or 25. Suppose you do the quadtree thing, with each pixel being assigned a country value. Suppose your map is 512x512 pixels (because its close to right, and it makes the math easier). Since 512 is 2**9, you will do at most 9 selections of a child node in the quadtree, and the check you do for selecting a child node is no harder than a rectangular boundary check. Plus, there is no masking operation at the end (while checking the mask takes nearly no time, translating the coordinates is almost equal to a boundary check). Nine at worst, on average probably 6 or 7. One third the checks, three times as fast. But there is a faster way. Don't make the gadgets, but make masks for all the countries. Make a quadtree that only sorts the masks, not each individual pixel on the screen. If you place the outlines of all the masks on the screen, you can chop the screen with vertical and horizontal lines on the boundaries of the masks so that for each rectangle on the screen, you know which masks you must check. At worst, you will need to make 100 vertical lines and 100 horizontal lines. Thus, your quadtree will have a maximum depth of ceiling(log_base_2(100)) = log_base_2(128) = 7. This has the dubious advantage of trading on average 2 selections of a child node in the quadtree for checking a mask or two (actually, you will often not even need to check a mask), but it has the advantage that your quadtree is smaller by two levels, which cuts out roughly half the storage for the tree. The more complicated your picture, the more useful this is (that is, the more jagged the borders, not the more countries you have). Of course, you need to store the masks, too...but if you want to change the color of a selected country, you need those anyway. What Matt said was right; this is an algorithms issue, not a gadget issue. His point was that using quadtrees, you generally need to do log_base_2(dim) comparisons, where your screen is dim x dim pixels, and using a list of gadgets, you generally need to do N/2 comparisons, where you have N gadgets. For a 512 x 512 screen, if you have over 18 countries, quadtrees win on average, and if you have over 9 countries, quadtrees win on worst case. And, they really are not that difficult to program, IMO. And if you have 200 countries, still on a 512x512 screen, quadtrees will still take you at most 9 comparisons, where a gadget list will take you 200 at most, or 100 on average. Only 4.5% of the time do you have a chance to beat the quadtrees! --Max