[EMAIL PROTECTED] wrote:
> I have a bitmap image that contains a several squares in it.. I have a
> program that alows the user to move around the pointer with the mouse and
> click the mouse buttons (theres more to it than that but that's all i need
> to explain)..
> So I want to know when the user is clicking in one of the squares... I know
> all the coding techiniques to check the mouse and etc..
>
> Q: What I want to know is what is everyones opinions to the best structure
> of the list of squares...
> for instance... square 1: top left: 1,1; bottom right: 5,9 etc...
> So I would want to store the 1,1 and the 5,9
> I'm not sure of all of my options for this... Should I store them in a
> list?? in a binary tree?? or just some sort of sequential table?? (I'm a
> mainframe cobol programmer by profession and it sometimes gets
> in my way when I try to think in C)
It depends upon how many squares you are likely to have.
If the number is relatively small, I would store them in a list
(linear or linked), and just scan the entire list for each mouse
click.
If there are many of them (i.e. efficiency is important), then I would
use a space partitioning tree.
Depending upon the number of rectangles and the amount of memory
available, you could either:
a) Create a list of all of the x coordinates (2 per rectangle), and
sort them into ascending order; likewise for the y coordinates. This
effectively divides the space into a non-uniform 2n+1 by 2n+1 grid.
Given an (x,y) position, you can convert this to an (i,j) grid
coordinate. You can then just look up the corresponding rectangle in a
2D array.
b) As a) above, but just the x coordinate. This divides the space into
2n+1 vertical strips. Then apply the same principle in the y
direction, resulting in an array of arrays. This is basically an n-ary
tree of height 2.
c) Partition the space into a binary tree.
The above methods are in decreasing order of memory consumption. a)
and b) should take about the same time, whereas c) is slower.
--
Glynn Clements <[EMAIL PROTECTED]>
