查找重叠矩形算法

就个人而言，我将使用KD-Tree或BIH-Tree解决此问题。它们都是具有log（n）搜索时间的自适应空间数据结构。我为我的Ray
Tracer实施了这两种方法，并且它们都尖叫了。

-更新-

将所有固定的矩形存储在KD-Tree中。测试相交时，请按以下步骤遍历KD-Tree：

function FindRects(KDNode node, Rect searchRect, List<Rect> intersectionRects)// searchRect is the rectangle you want to test intersections with// node is the current node. This is a recursive function, so the first call//    is the root node// intersectionRects contains the list of rectangles intersectedint axis = node.Axis;// only child nodes actually have rects in themif (node is child){    // Test for intersections with each rectangle the node owns    for each (Rect nRect in node.Rects)    {        if (nRect.Intersects(searchRect))   intersectionRects.Add(nRect);    }}else{    // If the searchRect's boundary extends into the left bi-section of the node    // we need to search the left sub-tree for intersections    if (searchRect[axis].Min  // Min would be the Rect.Left if axis == 0,         // Rect.Top if axis == 1     < node.Plane) // The absolute coordinate of the split plane    {        FindRects(node.LeftChild, searchRect, intersectionRects);    }    // If the searchRect's boundary extends into the right bi-section of the node    // we need to search the right sub-tree for intersections    if (searchRect[axis].Max  // Max would be the Rect.Right if axis == 0        // Rect.Bottom if axis == 1     > node.Plane) // The absolute coordinate of the split plane    {        FindRects(node.RightChild, searchRect, intersectionRects);    }}

从伪代码转换后，此功能应该可以工作，但是算法正确。这是一个log（n）搜索算法，可能是最慢的实现（从递归转换为基于堆栈）。

-更新-添加了一个简单的KD-Tree构建算法

包含面积/体积形状的KD树的最简单形式如下：

Rect bounds = ...; // Calculate the bounding area of all shapes you want to    // store in the treeint plane = 0; // Start by splitting on the x axisBuildTree(_root, plane, bounds, insertRects);function BuildTree(KDNode node, int plane, Rect nodeBds, List<Rect> insertRects)if (insertRects.size() < THRESHOLD ){     AddRectsTonode(node, insertRects);     node.IsLeaf = true;     return;}float splitPos = nodeBds[plane].Min + (nodeBds[plane].Max - nodeBds[plane].Min) / 2;// once you have a split plane calculated, you want to split the insertRects list// into a list of rectangles that have area left of the split plane, and a list of// rects that have area to the right of the split plane.// If a rect overlaps the split plane, add it to both listsList<Rect> leftRects, rightRects;FillLists(insertRects, splitPos, plane, leftRects, rightRects);Rect leftBds, rightBds; // Split the nodeBds rect into 2 rects along the split planeKDNode leftChild, rightChild; // Initialize these// Build out the left sub-treeBuildTree(leftChild, (plane + 1) % NUM_DIMS, // 2 for a 2d tree          leftBds, leftRects);// Build out the right sub-treeBuildTree(rightChild, (plane + 1) % NUM_DIMS,          rightBds, rightRects);node.LeftChild = leftChild;node.RightChild = rightChild;

这里有很多明显的优化，但是构建时间 通常 不如搜索时间重要。话虽这么说，一棵好树才能使搜索迅速。如果您想学习如何构建快速的kd树，请查找SAH-KD-
Tree。