Handling selection of shapes on a board (algo)

Question

I have a board as a canvas with several shapes drawn on it, some of them are triangles, circles, rectangles but all are contained inside their own bound delimited rectangle.

"The circle will be inside a rectangle"

I put two circles A, B on the board where A is over B and has some area colliding. If I click on A area corresponding to the container box but not the actual A circle shape area I wont select the A circle, however that would stop me from selecting B since my A container overlaps and is over B one.

In an event base framework, the child event will go to the parent not siblings I guess.

So my choice was to do a check for all shape container which have some area at point x ordered by z index. Then for each container check if the shape inside it collide.

It does not seem super efficient but is there any other ways?

---------
|    --------  
|    |      |
-----|      |
     --------

Answer 1

You're handling it about as well as it can be handled - windowing systems generally obey Z order (layers).

This will be better in the long run anyway, especially if you want to be able to select multiple items by drawing a selection box around them.

There are algorithms for finding if rectangles overlap by converting them into 2d representations on both the x and y axis. You can do the same thing, and then compare your point to see which objects your point overlaps:

http://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles

Just treat your point selection (or rectangle selection if you draw a bounding box to select multiple items) as another rectangle to be compared as overlapping to the others.

Answer 2

There are tricks you can play if you really need speed. For example:

• If you are working with a deep pallet you can use the low order bits of the color to tag the objects. Then peeking at the pixel gives you the object or at least lest you quickly drastically cull the list.
• Even at low bit depth, if the objects are all monochrome you can use the whole color
• If you're in low enough resolution you can keep an array that says what object owns what pixel.
• At higher res you can do the same but use RLE to keep the size down (also look into quad trees)
• And so forth...

If it's just simple implementation you're after, one quick trick is to record the X & Y, repaint the screen, and note which object paints that pixel.

-- MarkusQ