1

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.

a selection demonstration

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.

Improve this question
2
  • The selection loop should use for (struct node *node = getend(list); node; node = node->prev) { ... }. As coded with a do/while loop, you cannot handle an empty list. Commented Nov 29, 2020 at 9:19
  • From experience, describing rectangles as top, left, bottom, right produces simpler code than top, left, width, height. Commented Nov 29, 2020 at 9:42

2 Answers 2

Reset to default
2

Five different approaches:

Screen Space Selection

Render the rectangles from back to front order onto a temporary array/grid of "pixels", but using "rectangle ID" instead of colors. Use the selection rectangle to select "pixels" and examine them to determine the "rectangle IDs" for selected rectangles. This is likely to be the simplest option (and likely to have the worst performance).

Selection Rectangle Subdivision

Search from front to back (like you are); but when you find a rectangle that overlaps the selection rectangle use its edges to split the selection rectangle up into sub-rectangles and discard sub-rectangles that overlap the found rectangle. This will leave you with zero to 8 sub-rectangles that don't overlap the found rectangle. Repeat this process using each of the resulting sub-rectangles (instead of the original selection rectangle) to find more rectangles that were selected. Note that (for "worst case") the number of sub-rectangles can increase by 7 for each rectangle selected.

Rectangle List Subdivision

Pre-process the list of rectangles using the edges of front rectangles to sub-divide any back-polygons, and discard any overlapping sub-rectangles; so that the resulting list of rectangles no longer contains anything that overlaps. After this; find all (sub)rectangles that overlap with the selection rectangle. Note that this is nicer if the list of rectangles doesn't change often and the same "pre-processed list of rectangles" can be re-used many times.

Selection Polygon Subtraction

Assume the selection area is an arbitrary shape with N vertices and N sides, which just happens to be 4 vertices and 4 sides in the beginning. Search from front to back (like you are); but when you find a rectangle that overlaps the selection polygon subtract the overlapping areas from the selection polygon. This is incredibly complicated; partly because the selection polygon can be split into "separated/non-touching" pieces and/or can become "donut like". This can be combined with the previous approach - e.g. use the edges of the overlapping rectangle to split the selection polygon into sub-polygons, then discard overlapping sub-polygons, then merge sub-polygons that share a common edge to reduce the number of sub-polygons.

Rectangle List Subtraction

Pre-process the list of rectangles (and convert them all into arbitrary shaped polygons) using a similar approach to "Selection Polygon Subtraction". After this; find all (sub)polygons that overlap with the selection rectangle. Note that this is nicer if the list of rectangles doesn't change often and the same "pre-processed list of polygons" can be re-used many times.

Notes

There's more advanced techniques for polygon subtraction than the "split then merge if you can" approach I described, which are much more complicated and give better performance. For one research paper, see https://www.pnnl.gov/main/publications/external/technical_reports/PNNL-SA-97135.pdf

Myself, I'd probably use the "Selection Rectangle Subdivision" approach if the highest possible performance isn't a necessity (and if the list of rectangles changes more often than the selection rectangle).

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I would also favor the Selection Rectangle Subdivision, as it is simple to code with a recursive function. Note that the maximum number of subrectangles to process for the rest of the list is 4, not 8: for example the selection rectangle can be first be split in 3 horizontal bands, above the object, below the object, and the middle band can be further split horizontally into 3 rectangles, only 2 of which need further processing. This method is very inefficient if there are many small rectangles in the foreground.
0

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.

Improve this answer

2 Comments

Your formula for the intersection of 2 rectangles is incorrect as w and h should be the dimensions of the rectangle, not the coordinates of the bottom right corner. +1, -1 adjustments are highly suspect too. I'm afraid your solution works by coincidence only. A brute force approach iterating on all points in the selection rectangle can work, but is highly inefficient. Yet your iterations do not achieve that because the loops are not nested.
@chqrlie, yes, your proposed notation makes the problem clearer. I update the question and own answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.