Как фигуры (прямоугольники) работают в четырехугольных деревьях?

10

Мне сказали, что четырехугольное дерево является идеальной структурой данных для моей игры, но у меня возникают проблемы с пониманием того, как именно формы работают в четырехугольных деревьях.

Я делаю это в JavaScript, но я думаю, что эти вопросы могут применяться к деревьям квадратов на любом языке.

Я думаю, что в основном понимаю, как базовые (x, y) точки и вставка точек работают в четырехугольных деревьях, и что я могу сделать это на бумаге.

Вот JSfiddle из моих экспериментов с точками.

точки четырех деревьев

Помимо одного случая, мои тесты с баллами работают как положено.

Но мое замешательство начинается, когда фигуры, подобные прямоугольникам, задействованы. Когда вы извлекаете данные из четырехугольного дерева с фигурами, проверяет ли оно каждую точку фигуры и в какие узлы они попадают? И как же работает вставка фигур, когда она принимает (x, y, width, height) параметры для каждой фигуры? Использует ли он ширину / высоту от начальной точки для вычисления других угловых точек, которые затем распределяются по соответствующим узлам? Если вставленная фигура охватывает четыре узла, сохраняются ли данные этой фигуры во всех четырех узлах?

И когда метод поиска принимает форму в качестве параметра (x, y, width, height), что на самом деле происходит? Сначала он видит, на какие узлы распространяется форма, если ее вставить, а затем извлекает все объекты этих узлов?

У меня есть JSfiddle, работающий с фигурами , но я совершенно запутался в результатах своего тестирования. Я получаю дубликаты объектов, которые возвращаются!

формы четырехугольного дерева

Например, красный квадрат - это нарисованный эквивалент параметров, которые я ввожу в свой метод поиска. Я думаю, что, поскольку этот красный квадрат охватывает все четыре узла, он должен возвращать каждый объект в четырехугольном дереве! Но это не так, и у меня возникают проблемы с рационализацией того, что он возвращает. У меня есть ряд других тестов, которые в настоящее время закомментированы, но вы можете отменить комментирование и запустить их, чтобы увидеть более запутанные результаты!

Как сказать, если я хочу вернуть все точки в четырехугольном дереве, как бы я это сделал? Метод извлечения, использующий фигуру по всему размеру границ? Например, получить (0, 0, canvas.width, canvas.height)?

Библиотека JavaScript QuadTree, которую я использую, упоминалась в различных других источниках, поэтому я предполагаю, что фактическая реализация является правильной и заслуживающей доверия.

Я думаю, что большая часть моей путаницы может быть вызвана неправильным пониманием терминологии четырехъядерных деревьев. Например, почему они говорят о границах, а не о размерах, когда у «точки» также есть параметры ширины / высоты? Это условность / сокращение или это совершенно разные понятия?

Спасибо за ваше время!

user2736286
источник
Они хранятся в квад-дереве как обычно, в зависимости от их положения. Обычно они находятся в центре, но могут быть в углу, как вы определили. Ваш вопрос может быть дубликатом этого вопроса: QuadTree: хранить только точки или регионы?
MichaelHouse
Я прочитал этот вопрос, но до сих пор не до конца понимаю ответы :(. «Вы должны хранить его в самом маленьком узле, который полностью содержит его, даже если это превышает емкость (используйте контейнер с изменяемым размером).» - Когда он говорит, что наименьший узел, который содержит его ПОЛНОСТЬЮ, если объект очень большой, разве этот узел часто не является листовым узлом? Как в более высоком узле, который состоит только из других узлов? меня, так как это будет означать, что содержащий узел будет иметь 1 лист и 4 меньших узла в нем
user2736286
1
@ user2736286 Если вы посмотрите на код для библиотеки quadtree (он не очень длинный), вы увидите, что он сохраняет прямоугольники в узлах более высокого уровня, чтобы они не выходили за границы узла. Смотрите ссылки на _stuckChildrenполя в коде. Вы также можете увидеть это в примере «извлечение элементов с границами» - он всегда выделяет красным узлы, которые пересекают границы узлов, по которым вы щелкнули, вплоть до корневого узла.
Натан Рид
@ user2736286 Кроме того, в библиотеке quadtree, как представляется, имеется ошибка при получении элементов с границами - если вы зададите ей прямоугольник запроса, который охватывает некоторые границы узлов, он не вернет все линии в узлах, к которым обращается запрос. Это можно легко увидеть также в «получении элементов с границами», щелкнув возле границ узла.
Натан Рид
@NathanReed Ранее я пытался понять код, но я не достаточно опытен, чтобы понять его без концептуальной основы. Благодаря псевдокоду Джона Макдональда я теперь понимаю, как прямоугольники вставляются в узлы, но я думаю, что мне все еще неясно, как работает поиск. Что касается «извлечения элементов с границами» - я совершенно запутался в примере. Например, когда я щелкаю прямоугольник, который точно вписывается в один из самых маленьких узлов, почему все эти другие участки вне этого узла также подсвечиваются?
user2736286

Ответы:

10

Quadtree обычно хранят и получают прямоугольники. Точка - это особый случай, когда ширина и высота равны нулю. Следующая логика используется, чтобы найти дом для новых прямоугольников в дереве, начиная с корневого узла:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Обратите внимание, что прямоугольники могут храниться на любой глубине, это не обязательно должен быть четырехугольник листа. Если прямоугольник пересекает границу прямо на корневом уровне, корневой квад будет хранить прямоугольник.

Например, красный квадрат - это нарисованный эквивалент параметров, которые я ввожу в свой метод поиска. Я думаю, что, поскольку этот красный квадрат охватывает все четыре узла, он должен возвращать каждый объект в четырехугольном дереве! Но это не так, и у меня возникают проблемы с рационализацией того, что он возвращает.

При запросе quadtree он будет возвращать только те прямоугольники, которые содержатся в запросе. В вашем примере вы заставляете смотреть каждый из 4 дочерних квадов более детально, потому что красный прямоугольник запроса пересекает каждый дочерний квад. Поскольку у детей больше нет детей, каждый из прямоугольников в этих дочерних квадратах будет сравниваться с красным прямоугольником. Поскольку ни один из прямоугольников в дереве не сталкивается с красным прямоугольником запроса, ничего не должно быть возвращено.

Вы действительно начинаете видеть преимущества дерева квадрантов, когда у вас много объектов и много места для объектов по сравнению с областями запросов. В этих случаях небольшая область запросов может быстро исключить из рассмотрения обширные куски четырехугольного дерева. Только квадраты, которые пересекаются с прямоугольником запроса, будут рассмотрены более подробно.

РЕДАКТИРОВАТЬ

Извлечение обычно выполняется следующим образом:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

Однако в вашей библиотеке, похоже, не проверяется, пересекаются ли возвращаемые прямоугольники с запросом, поэтому вам нужно добавить это самостоятельно.

Джон Макдональд
источник
После более подробного изучения вашей библиотеки она возвращает список всех возможных кандидатов на столкновение для указанного вами прямоугольника запроса. Похоже, что ваша работа - сравнивать прямоугольник запроса с каждым кандидатом, чтобы увидеть фактическое столкновение. Большинство библиотек делают этот последний шаг для вас и просто возвращают фактические коллизии с областью запроса. Итак, все, что вам нужно сделать, это добавить некоторую логику в ваш retrieveметод для сокращения списка. Здесь вы можете увидеть, что он делает, более четко: mikechambers.com/html5/javascript/QuadTree/examples/…
Джон Макдональд,
1
@ user2736286 Если вы его не заметили, важно принять к сведению рекурсию функций Query и Store, написанную JohnMcDonald. Это не будет иметь большого смысла, если вы не получите эту часть. В обоих случаях каждая рекурсия углубляется в дерево, т. Е. На ветви и, наконец, в листья.
TASagent
Спасибо Джон, твой псевдокод очень полезен. Когда вы говорите «if (queryRect пересекается с границами childNode)», означает ли это в основном, что queryRect содержится в границах - частично или полностью? Просто хочу быть на 100% прозрачным. Кроме того, в обсуждаемом примере «извлечение элемента по границам» у меня есть изображение результата моего клика. Pic Синяя точка - это то, где я щелкнул. Так почему же не выделены только два прямоугольника внутри этого узла? Почему прямоугольники так же далеко от него выделены? Я думаю, это то, что действительно смущает меня.
user2736286
Часть или полная. Если два касания, или одно из них полностью содержится в другом. Вы хотите прочитать вики на Quadtrees , но я взял вашу фотографию и раскрасил ее цветом, чтобы представить различные дочерние границы. Все синие прямоугольники пересекаются с границами первых дочерних четырехугольников, затем пурпурный цвет на один слой глубже, а зеленый еще на один слой глубже. Красные прямоугольники пересекаются с четырехугольником, по которому щелкнули. Ваша библиотека возвращает все ректы на дочерних границах плюс все, что содержится в последнем дочернем квадрате
Джон Макдональд,
Итак, я старался изо всех сил просмотреть исходный код библиотеки и наконец понял поведение stuckChildren, и что все эти дополнительные прямоугольники на моем рисунке - просто stuckChildren. Первоначально я думал, что любые каналы, охватывающие несколько узлов, просто дублируют свои данные и вставляют в каждый меньший узел. Теперь я понимаю, что stuckChildren не вставляется в охватываемые им узлы, а просто остается в одном содержащем его узле, поэтому я должен также проверять все родительские узлы, а не только самый маленький узел, содержащий мой прямоугольник запроса. Спасибо за фото; теперь это имеет больше смысла :)
user2736286