Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!HERMES.BERKELEY.EDU!dillon From: dillon@HERMES.BERKELEY.EDU (Matt Dillon) Newsgroups: comp.sys.amiga.tech Subject: Re: Clicking on Irregular Shapes Message-ID: <8906222034.AA24121@hermes.Berkeley.EDU> Date: 22 Jun 89 20:34:41 GMT Sender: daemon@ucbvax.BERKELEY.EDU Lines: 94 :Mike Schwager Writes: :Hope someone can help with this C question: : :Given an irregularly shaped object on a Screen, how can one tell if :the mouse button has been pressed inside of it? I don't want a box all :around or inside it; I want the object and exactly the object. Here's :why I ask: I'm going to be drawing a map on the screen (into a Backdrop :window of a workbenchscreen) and I want to be able to select individual :... :I was looking at info about gadgets, but I didn't find them handy cuz :the active part is a box. I don't like the way collision detection is :... :Also- the countries will be bordered, if that helps. Maybe I need to :define my countries by a series of borders, and see if the mouse click :falls inside a border. This is more an algorithmic question. As has been said, Intuition does not handle irregularly shaped objects as gadgets and even if it did one would probably *not* want to implement your map as such. This is, in fact, a perfect application for a QUAD-TREE to handle in terms of identifying the country under the mouse when you hit a button. Once identified, you can highlight the country according to its borders which I assume have been extracted somehow from the bitmap (?? else how would you know the dimensions, eh?). The QUAD-TREE would terminate when a particular quad contains one or zero countries. --- What is a quad tree? Very simply put it is like a binary subdivision only in two dimensions instead of one. #define NEETO_ASCII_GRAPHICS_ON 0000000011110000 0000000011110000 0000000011110000 0000000011110000 1000000011111111 0000000011111111 0000000011111111 0000000011111111 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 Lets say you want to represent the above bitmap as a quad tree. First of all, note that the bounds are a power of two high and wide... this makes the quad tree extremely simple to generate. You take the square and split it up into four subsquares. If a given subsquare is all 0's or all 1's you mark it as such and do not recurse. If a given subsquare is a mix you recurse (break up that subsquare into four more subsubsquares, add infintum). The above example would be represented as: #define AWESOME_AI_GENERATED_GRAPH_USING_NEETO_ASCII_GRAPHICS_ON Quadrant: 21 34 |(1) ZEROS |(2) ONES |(1)----|(3) ONES | |(4) ONES | | | | | |(1) ZEROS ROOT----|(2)----|(2) ZEROS |(1) ZEROS | | | |(1) ZEROS | |(3)------------|(2)------------|(2) ONES | | | |(3) ZEROS | | |(3) ZEROS |(4) ZEROS | |(4) ZEROS |(4) ZEROS | |(3) ZEROS |(4) ZEROS If you use the quad tree to only identify the country the coordinate resides in, it would be quite small (with complexity only at the borders), and identification would be extremely fast. For example, you could stream line it by simplifying quads containing a single country + ocean to identify the entire quad with the country. -Matt