🚀 go-pugleaf

:Mike Schwager	<schwager@a.cs.uiuc.edu> 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