Rectangle selection algorithm

Question

Rectangles are located in a doubly-linked list. In this context, a rectangle is a figure, formed using a data of the rectangle's structure (no matter how).

struct rect {
    int l; /* left */
    int t; /* top */
    int r; /* right */
    int b; /* bottom */
};

Its fields has the strict positions (I guarantee it for any rectangle).

[l; t]          [r; t]
       +------+ 
       |      |
       |      |
       +------+ 
[l; b]          [r; b]

Rectangles are stored in objects.

struct object {
    struct rect *rect;
    bool selected;
};

And objects are stored in the list's nodes.

struct node {
    struct object *obj;
    struct node *next;
    struct node *prev;
}; 

Rectangles draws consistently, beginning from the list's head -- first draws a rectangle, closer to the beginning of the list. Thereby, an each next figure overlaps previous figures.

I select rectangles, with a selection rectangle, that forms by mouse cursor. The selection check is done, during iterating over the list from the end.

struct node *node = getend(list);
struct object *obj;

do {
    obj = node->obj;

    /* Check, if a selection rectangle somehow 
     * intersects with a rectangle of the current 
     * object. */
    if (rcheck(sel_rect, obj->rect))
        obj->selected = true;
}
while ((node = node->prev));

Take a look to the demonstration of my problem, a little below.

As you can see, the selection rectangle selects two rectangles: yellow and green. In this case, only the yellow figure should be selected; in general -- if behind a forward rectangle another figure is located (a backward rectangle), and a selection rectangle does not cover a "visible" part of this figure (on the animation it's the green polygon, formed by overlapping the yellow figure), but covers its "hidden" part, then a backward rectangle should not be selected.

---

A forward rectangle means, that it's located closer to the end of the list; a backward rectangle - that it's located closer to its beginning.

This alrogithm is used in game's two-dimensional map editor, for rectangular textures selection.

Answer 1

I though of the solution myself, and it turned out to be a little more difficult, than I expected. And it took me a while.

The method of the list traversing wasn't changed -- I do the selection check for each node from front to back.

First, I select root rectangle (first rectangle, intersecting with the selection). Next, if other rectangles intersecting, they are checked on intersecting with root to make sure they aren't just aside.

I memorize rectangles between r (the current rectangle) and root (including root) -- it will be needed for the further checks. Rectangles are stored in rect_list (in another list).

Traversing this list starts. On this moment, I firstly check r and sr (a node's rectangle) aren't intersecting together, and store their intersection in ir. Also, the selection rectangle should intersect ir.

if (!rintersect(r, sr, ir))
    continue;

if (!rcheck(sel_rect, ir))
    continue;

Now, I scan the area around ir -- points of each side of rectangle with coordinates:

struct rect scan_area {
    ir.l - 1,
    ir.t - 1,
    ir.r + 1,
    ir.b + 1
};

to check for a point in current rectangle and in the selection, but not in all memorized rectangles (list_check does this).

bool l = false;
bool t = false;
bool r = false;
bool b = false;
struct point p;
int i;

for (i = ir.l; i <= ir.r; i++) {
    p.x = i;

    p.y = ir.t - 1;
    if ((t = list_check(rect_list, p))
        break;

    p.y = ir.b + 1;
    if ((b = list_check(rect_list, p))
        break;
}

for (i = ir.t; i <= ir.b; i++) {
    if (t || b)
        break;

    p.y = i;

    p.x = ir.l - 1;
    if ((l = list_check(rect_list, crd))
        break;

    p.x = ir.r + 1;
    if ((r = list_check(rect_list, crd))
        break;
}

if ((obj->selected = l || t || r || b))
    break;

---

I wouldn't say this alrogithm highly inefficient, comparing it with the first Brendan's proposed way: screen space selection, because I need to check all rectangles, firstly; check all pixels of these rectangles, including each pixel of the selection, secondly.

Objectively, this alrogithm isn't fast (O(n^3)). However, it isn't noticeable within my task.