矩形交点

Question

我有一个矩形列表，我需要生成一个相交的矩形列表。
定义矩形

• 使用Point
• Size
• Boolean 矩形是否可以移动
• Boolean 矩形是否可以移除 矩形

不能移动但不能移除

交集使用 Point Size 定义 交点使用

• 指向第一个矩形的
• 指针 指向第二个矩形的指针
• 第一个矩形的点列表 第二个列表中
• 在第一个矩形中第二个矩形的点的

，我需要一个容器，因为可以添加、删除或移动矩形。我需要的操作：

1. 插入矩形
2. 删除矩形（仅适用于那些标记了它的人）
3. 更改矩形的位置（不是大小，仅适用于那些标记了它的人）
4. 生成交集集。

我将如何实施这样的容器？我可以使用交叉检查方法轻松完成此操作，但这远未达到优化。
我想保留一张矩形地图 ->交集，然后每当添加一个矩形时，检查它是否与任何东西相交并将交集添加到地图中，当删除它时，从地图上删除键，但我不知道如何快速检查它是否与任何东西相交，或者如何移动矩形而不删除并重新插入。
我可以使用 C++11。

Answer 1

假设从左到右/从上到下的坐标系，两个矩形的交集就是顶部是顶部中最底部的矩形，底部是底部中最顶部的矩形，左如果是左和右中最右的是最左边的权利。

如果您可以通过按左、上、右和下排序的容器间接访问矩形，则可以有效地运行测试。

另一种方法可以是使用一个键（对于映射），该键是 ax/delta 对以及运算符<<。在 a.x+a.delta a.x+a.delta 的地方考虑 a bx 和 y 相同。
原始点只是一个大小为 1 的矩形。

本质上，您需要一个矩形本身的容器（修改时不得重新分配矩形，因此 std::list 可以工作）和两个 std::map（用于水平和垂直）映射）具有位置/大小对作为键和列表迭代器（可以是由 &*iter 生成的矩形指针）作为值。

Answer 2

我的建议是一个模糊的容器：

class region {
    typedef std::vector<vector*> subregion;
    std::array<std::array<subregion, 100>, 100> locations;
    std::vector<rectangle> children;
public:
    std::vector<rectangle>::iterator add(rectangle addme);
    void remove(std::vector<rectangle>::iterator deleteme);
    void move(std::vector<rectangle>::iterator moveme, point to);
    void intersect(std::vector<rectangle>::iterator left, 
                   std::vector<rectangle>::iterator right);
};

children 成员只是容器中矩形的迭代列表。每个子区域是可容纳矩形的总区域的百分之一。添加矩形后，指向它的指针将添加到该矩形接触的所有子区域。当删除矩形时，它的指针将从该矩形接触的所有子区域中删除。移动实际上是删除、矩形更新，然后添加。

然后，要找到交集（取决于您想要的方式），您只需查看包含多个指针的每个子区域，并对该子区域中的每个矩形进行简单比较。