矩形选择算法

Question

矩形位于双向链表中。在这种情况下，矩形是一个图形，使用矩形结构的数据形成（无论如何）。

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

它的字段有严格的位置（我保证它适用于任何矩形）。

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

矩形存储在对象中。

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

并且对象存储在列表的节点中。

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

矩形绘制始终如一，从列表的头部开始 -- 首先绘制一个矩形，靠近列表的开头。因此，每个下一个数字都与前面的数字重叠。

I select 矩形，带有一个 selection 矩形，由鼠标光标形成。 select离子检查在从末尾迭代列表的过程中完成。

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));

请看下面我的问题演示。

如您所见，selection 矩形 select 有两个矩形：黄色和绿色。在这种情况下，应该只 selected 黄色数字；一般来说——如果在前向矩形后面有另一个图形（后向矩形），并且 selection 矩形确实不覆盖该图形的“可见”部分（在动画上它是绿色多边形，通过重叠黄色图形形成），但覆盖了它的“隐藏”部分，那么一个向后的矩形应该 not selected.

A forward 矩形意味着它位于更靠近列表末尾的位置；一个向后矩形 - 它更靠近它的开始。

此算法用于游戏的二维地图编辑器，用于矩形纹理 selection.

Answer 1

五种不同的方法：

屏幕Space选择

将矩形从后到前渲染到一个临时 array/grid 的“像素”上，但使用“矩形 ID”而不是颜色。使用 selection 矩形到 select“像素”并检查它们以确定 selected 矩形的“矩形 ID”。这可能是最简单的选项（并且可能性能最差）。

选择矩形细分

从前到后搜索（就像你一样）；但是当你找到一个与 selection 矩形重叠的矩形时，使用它的边缘将 selection 矩形分割成子矩形并丢弃与找到的矩形重叠的子矩形。这将为您留下 0 到 8 个不与找到的矩形重叠的子矩形。使用每个生成的子矩形（而不是原始 selection 矩形）重复此过程，以找到更多 selected 的矩形。请注意（对于“最坏情况”）每个矩形的子矩形数量可以增加 7 selected.

矩形列表细分

使用前矩形的边对矩形列表进行预处理，以细分任何后多边形，并丢弃任何重叠的子矩形；这样生成的矩形列表不再包含任何重叠的内容。在这之后;找到与 selection 矩形重叠的所有（子）矩形。请注意，如果矩形列表不经常更改并且可以多次重复使用相同的“预处理的矩形列表”，这会更好。

选择多边形减法

假设select离子区是一个N个顶点和N条边的任意形状，刚好一开始是4个顶点和4条边。从前到后搜索（就像你一样）；但是，当您找到与 selection 多边形重叠的矩形时，从 selection 多边形中减去重叠区域。这非常复杂；部分原因是 selection 多边形可以分割成“separated/non-touching”块 and/or 可以变成“甜甜圈状”。这可以与以前的方法结合使用 - 例如使用重叠矩形的边将 selection 多边形拆分为子多边形，然后丢弃重叠的子多边形，然后合并共享公共边的子多边形以减少子多边形的数量。

矩形列表减法

使用类似于“选择多边形减法”的方法预处理矩形列表（并将它们全部转换为任意形状的多边形）。在这之后;找到与 selection 矩形重叠的所有（子）多边形。请注意，如果矩形列表不经常更改并且可以多次重复使用相同的“多边形预处理列表”，这会更好。

备注

有比我描述的“拆分然后合并”方法更高级的多边形减法技术，后者更复杂并且性能更好。有关一篇研究论文，请参阅 https://www.pnnl.gov/main/publications/external/technical_reports/PNNL-SA-97135.pdf

我自己，如果不需要尽可能高的性能（并且如果矩形列表比 selection 矩形更频繁地更改），我可能会使用“选择矩形细分”方法。

Answer 2

我自己想到了解决方案，结果比我预期的要难一些。这花了我一段时间。

列表遍历的方法没有改变 -- 我从前到后对每个节点进行 selection 检查。

首先，我 select root 矩形（第一个矩形，与 selection 相交）。接下来，如果其他矩形相交，将检查它们是否与 root 相交，以确保它们不只是放在一边。

我记住了 r（当前矩形）和 root（包括 root）之间的矩形——进一步检查将需要它。矩形存储在 rect_list（在另一个列表中）。

遍历此列表开始。此时，我首先检查r和sr（节点的矩形）是否相交，并将它们的交集存储在ir中。此外，selection 矩形应与 ir.

相交

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

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

现在，我扫描 ir 周围的区域 -- 矩形每边的点坐标：

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

检查当前矩形和 selection 中的点，但不检查所有记忆的矩形（list_check 执行此操作）。

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;

我不会说这个算法非常低效，将它与第一个 Brendan 提出的方法进行比较：screen space selection，因为我需要检查所有矩形，第一;其次检查这些矩形的所有像素，包括 selection 的每个像素。

客观地说，这个算法并不快 (O(n^3))。但是，它在我的任务中并不明显。

矩形选择算法

Rectangle selection algorithm

c

algorithm

geometry

rectangles

selection