Лично я бы решил это с 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 intersected
int axis = node.Axis;
// Only child nodes actually have rects in them
if (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);
}
}
Эта функция должна работать после преобразования из псевдокода, но алгоритм верный. Это алгоритм поиска по журналу (n) и, возможно, самая медленная его реализация (преобразование из рекурсивного в стек).
- ОБНОВЛЕНИЕ - Добавлен простой алгоритм построения дерева KD
Простейшая форма дерева KD, содержащая фигуры области / объема, выглядит следующим образом:
Rect bounds = ...; // Calculate the bounding area of all shapes you want to
// store in the tree
int plane = 0; // Start by splitting on the x axis
BuildTree(_root, plane, bounds, insertRects);
function BuildTree(KDNode node, int plane, Rect nodeBds, List<Rect> insertRects)
if (insertRects.size() < THRESHOLD /* Stop splitting when there are less than some
number of rects. Experiment with this, but 3
is usually a decent number */)
{
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 lists
List<Rect> leftRects, rightRects;
FillLists(insertRects, splitPos, plane, leftRects, rightRects);
Rect leftBds, rightBds; // Split the nodeBds rect into 2 rects along the split plane
KDNode leftChild, rightChild; // Initialize these
// Build out the left sub-tree
BuildTree(leftChild, (plane + 1) % NUM_DIMS, // 2 for a 2d tree
leftBds, leftRects);
// Build out the right sub-tree
BuildTree(rightChild, (plane + 1) % NUM_DIMS,
rightBds, rightRects);
node.LeftChild = leftChild;
node.RightChild = rightChild;
Здесь есть куча очевидных оптимизаций, но время сборки обычно не так важно, как время поиска. Тем не менее, хорошо построенное дерево - это то, что делает поиск быстрым. Посмотрите SA-KD-Tree, если вы хотите узнать, как построить быстрое KD-дерево.