Most efficient way to determine in what quadrant coordinates fall

[stang966]

Hello All,

A (possibly) quick logic problem:

In a program I'm writing I've divided my monitor into 25 different quadrants.
Sort of like this:
___________________
[1] [2 ]___3_____[4][5 ]
[6] [7 ]___8_____[9][10]
| . | . |
| . | . |
| . | . |
| . | . |
|11|12| 13
| . | . |
| . | . |________[14][15]
[16][17]__18___[19][20]
[21][22]__23___[24][25]

[Edit: Sorry about the image. The formatting was terrible when I posted it. Basically, the right side should look like the left. [13] is the area in the center and [14][15] are the equivalent of [11][12]. Thanks. ]



Let's say that each of the lines of the quadrants fall at 100 and 200 pixels from the edge of my screen and the dimensions of my screen in pixels are:

0------->xdim
|
|
|
|
|
|
ydim

My program knows the x and y coordinates in pixels of each mouse click.

Does anyone know the most efficent way to find into which quadrant a mouse click falls?


I'd really appreciate it if anyone has any ideas about this. I'm currently using numerous nested if/if else statements and greather than/less than comparisons. My code works, but clearly it is not very efficient and definitely ugly.


Thank you very much,
Ben

[ZuK]

qu_width = screenwidth/5;
qu_height = screenheight/5;
quadrant = 1 + ( xpos / qu_width ) + 5 *( ypos / qu_height);
something like this should work if all the variables are ints.
Kurt
Edit: Looking at your drawing again I'm not shure anymore that all the quadrants are supposed to be the same size.

[stang966]

Thanks ZuK,

Unfortunately, the quadrants aren't the same size.


Each of the corners,
[1][2]
[6][7]

[4][5]
[9][10]

etc. are composed of 100x100 quadrants. [1] = 100 x 100, [2] = 100x100 ...

Furthermore, [11] = 100 x (screenheight-400), [12] = 100 x (screenheight-400)

[13] = (screenwidth-400) x (screenheight-400)

and so forth. (Basically, if the figure was a bit better you could see that each line separating a quadrant would be either 100 or 200 pixels from the edge).



I appreciate the help.

[ltcmelo]

Hi.

An efficient solution to this problem is not trivial. Additionally, a solution with a lot of ifs is not very elegant.

This problem falls into the area of computational geometry. There're different solutions for the problem. One of them is based on trapezoidal maps. The book Computational Geometry: Algorithms and Applications has an entire chapter dedicated to it. If you don't have access to the book, take a look at this material (http://www.cs.wustl.edu/~pless/506/l15.html). You can also try to search for other resources on the web (use keywords "point location" and "trapezoidal map" for example).

[stang966]

Thanks Itcmelo,

I really appreciate it. I'll take a look.

[JVene]

I've read Itcmelo's recommended post, and while I see the applicability, I don't see it used in situations very similar to stang666's construction. It looks no different, from a functional point of view, than a dialog with a bunch of controls, or a graphic editor window with a bunch of objects, or a gantt chart with a calender on display.

In those situations there is a container of some kind. In standard dialogs that's often the window hierarchy, but for a graphic editor, some custom dialog like windows, or even a word processor attempting to locate a character on the screen, an STL container is as likely a container as any.

If that container were a sorted vector, by Y,X, then the binary search method would be a very fast way of locating an entry in that container, considering X,Y as a key. Probably faster than a recursive search of a tree.

It's also simpler, and I doubt any slower than the trapezoidal map, which I believe is more applicable to dynamic layouts than a static layout like this one.

The search, though, isn't strictly for a match, it's for a range. This implies that the key has a start/end relationship, which, like searching for a position in a variable pitch font for a match to a character selection, suggests that the search involves either a structure with a start/end pair, or you are considering two entries for each match - the lesser and greater points surrounding the target of interest.

For small volumes like this, the redundant pair seems appropriate and simplifies the search through the container, IMO. So, I'd go with something like upperY, lowerY - and conversely, leftX, rightX - essentially the rectangles of the grid itself. This does mean you have redundant values, the lowerY if one IS the upperY of another, but in low volumes that's not a hindrance.

Let's say y is 250 - you've eliminated any interest in entries in the container where the lowerY is under 250 and the upperY is over 250. That defines your comparison operator for the search - it's as if anything between these two is a match, like an equality.

One of the things the trapezoidal maps helps with, if memory serves, is spanning various sized target areas. You have only one target that's not evenly sized in rows or columns, the central area. In all other cases, it appears, you have rows and columns that are symmetrical, the center is the only one not completely symmetrical with it's row partners, or it's column partners.

This hints at a specialization. It's probably good (and quick) to eliminate that one region first. If that rectangle contains the point (the mouse position, I assume), you're done.

Otherwise, the search is on.

Sorting the container means you can eliminate all other regions except those on one row using Y.

Now, you can perform the same search using X, knowing the targets are all the same upperY/lowerY. Obviously this isn't true if the layout isn't symmetrical, but since it is, you have an advantage.

However, the number of columns is small in rows that surround the central region (only 4) - a binary search algorithm is hardly much faster than just a quick loop, but perhaps a hint - probably no slower on average.

The other rows, however, would have a hint of an advantage with the binary search, and given that you've already stopped searching through all but 5 by now, there's leverage.

This hints, too, that it's faster and simpler, for searching, if you have a 'row' container, where each row contains a vector of the columns. That way, you're only going to find one entry in the row container in your search, rather quick - then only one entry in that row for the target.

Also, you can probably build the container 'in order', so you don't actually have to call sort.


That said, have you considered how fast it operates if you just loop through a vector of rectangles looking for a hit within one? It's not much time for such a simple algorithm, though obviously not particularly smart.

[VladimirF]

If you put right coordinates of quadrants [1], [2], [3] and [4] into one array, and bottom coordinates of quadrants [1], [6], [11] and [16] into another, you would need no more than 8 integer compare operations to find your target.
Can't see how any more complex method will be justified here.

[MikeAThon]

It would be a lot easier to program if the grid were regular, as ZuK has already suggested. Are you certain that it can't be a regular grid? There would be more cells in the grid than in yours, but you could perform the same actions for multiple different cells, so as to obtain the same end result that you're looking for. For example, assume you had an irregular 3x3 grid as follows:

|a| b |c|
| | | |
|d| e |f|
| | | |
|g| h |i|
The ugly ASCII art is intended to show an irregular 3x3 grid with cells of different sizes: the corner cells a,c,g,i are all (say) 100x100, lateral edge cells b,d,f,h are 100x200 or 200x100, and middle cell e is 200x200.

You could superimpose a more fine-grained grid on top of this:

|1|2|3|4|
|5|6|7|8|
|9|A|B|C|
|D|E|F|G|
Here, the grid is completely regular: each cell is 100x100. It's therefore easy to figure out the cell number, based on the code given by ZuK. Now, if the user clicks in either of cell 2 or 3, you take the action formerly taken if the user clicked in lateral edge cell b. Likewise, if the user clicks in any of the middle cells 6,7,A,B you take the action formerly taken for cell e. Etc.

Mike

[VladimirF]

It would be a lot easier to program if the grid were regular...
It would be even easier if there was only one quadrant! ;)
Are you certain that it can't be a regular grid?
Given that the corner pieces are 100x100, and typical width of the screen is 1024, 1152, 1280, 1440, 1680 - I doubt that...

[VladimirF]

Does anyone know the most efficent way to find into which quadrant a mouse click falls?
Since the topic of your post has "Most efficient" in it, I would like to suggest one more method.
It also demonstrates a famous trade-off between memory use and speed.
Declare to BYTE arrays; dimension of the first one (columns) equal to the screen width, second (rows) – screen height.
Initialize first 100 members of the columns array with 0, next 100 - 1, next (screen width - 400) - 2, etc. Same thing for rows.
No you can have your quadrant very fast:
col = columns[x];
row = rows[y];
quadrant= row*5 + col;

You can speed it up even more if you would create 2D byte array for each pixel on the screen and init it appropriately. Of course, you would use ~1MB of memory for that, but it's not that much!

[JVene]

VladimirF:

Actually, not only does that make a LOT of sense, since most (maybe all) of the regions in that layout are probably multiples of 10, you could divide the memory requirement by 10 (or, perhaps better, a power of 2 if that could be arranged).

[VladimirF]

VladimirF:

Actually, not only does that make a LOT of sense, since most (maybe all) of the regions in that layout are probably multiples of 10, you could divide the memory requirement by 10 (or, perhaps better, a power of 2 if that could be arranged).
That is a great idea. I did think about that. If you read my post #9 above, you'll see that 10 is not an option. Powers of 2 above 4 are not going to work for 100, and even 4 will not do on my laptop (running 1680x1050).
In other words, you can (at least I hope so) devide everything by 2 and save half-a-meg, but is it worth extra complexity?

[ltcmelo]

Hi.

The method I described earlier might be an overkill for the particular situation stang966 posted. I just tried to give a more conceptual and theoretical view of the problem. But anyway, you could also use kd-trees or range trees to search for a range. The idea is similar to what JVene explained in his post.

[JVene]

...and I for one applaud the reference, Itcmelo - it increases the depth of the conversation and at the very least shows an option that, given the right problem and reason, is otherwise not commonly known among the more casual students.

[Mitsukai]

In other words, you can (at least I hope so) devide everything by 2 and save half-a-meg, but is it worth extra complexity?
no u cant... u will get invalid results. say u click, x=101 devided by 2 is 50, arr[x][y] will return x-qaudrent 0 while this qaudrants x-size is 100 but u clicked x=101 and that should be x-qaudrent 1

if u want this as efficient as possible, why did u design such a wierd grid?
whats wrong with a grid with all same dimensions?

i think its ok to just make an array of quadrants with members X, Y and loop trough the quadrants to get the right quadrant

[YvesDaoust]

As appropriately exploited in ZuK's method, this problem is separable. I.e., you can determine the horizontal and vertical indices independently, in range 1..5 and 0..20 [step 5] respectively, and add them.

So the problem amounts to two searches among 5 intervals of unequal lengths.

This can be done with comparisons. At most 4 comparisons by sequential search, at most 3 by binary search. Less than 3 comparisons cannot be achieved unless special tricks are used that exploit symmetry. (In my opinion, not worth the effort.)

X < 100 ? 1 : X < 200 ? 2 : X < Width - 200 ? 3 : X < Width - 100 ? 4 : 5 +
Y < 100 ? 0 : Y < 200 ? 5: Y < Height - 200 ? 10 : Y < Height - 100 ? 15 : 20

Using lookup tables is a faster option if you can afford initializing these. I would not recommend using a 2D lookup table that maps the whole screen, since address computation would take one multiply anyway. Two 1D lookups are as efficient.

H[X] + V[Y]

(table H initialized with values 1, 2, 3, 4, 5 for the respective ranges, table V initialized with 0, 5, 10, 15, 20).

I don't think that using general purpose algorithms could be beneficial here given the tiny problem size.

I hope this helps,

Yves

[YvesDaoust]

Using arithmetic tricks, you get the not-so-efficient-as-it-might-look expression

1 +
(2 * X < Width ? Max(X / 100, 2) : 4 - Max((Width - X) / 100, 2)) +
(2 * Y < Height ? Max(Y / 100, 2) : 4 - Max((Height - Y) / 100, 2)) * 5

[VladimirF]

no u cant... u will get invalid results. say u click, x=101 devided by 2 is 50, arr[x][y] will return x-qaudrent 0 while this qaudrants x-size is 100 but u clicked x=101 and that should be x-qaudrent 1
Well, in my defence - I suggested an IDEA, not implementation...
You could always add 1 before division.

[Mitsukai]

faster is
(x + 2) >> 1;

[VladimirF]

faster is
(x + 2) >> 1;
Two things:
1. It is NOT faster. Any good compiler will produce "sar" instruction for "/2".
2. It is NOT correct. You only need to add 1.