Как я представляю использованное пространство в 2d?

Question

У меня есть фиксированная область 2d пространство, заполненное прямоугольниками. Я хотел бы переместить прямоугольники вокруг, добавить новые, удалить некоторые, но не позволить им перекрываться. Если все ректы имеют одинаковую высоту и ширину (50x50px), какую структуру данных я должен использовать для хранения своей позиции и какое пространство они используют, и какой метод поиска я должен использовать для этой структуры при добавлении новых ректов в сцену?

Answer 1

Это простая часть классической проблемы обнаружения столкновений .В основном AABB Trees (не уверен, что это ссылка best , но в любом случае это имя) используются для ее эффективного решения, но посмотрите все, что используют алгоритмы обнаружения столкновений для ограничивающего столкновенияобнаружение.Дерево AABB (Выравнивающая ось с выравниванием по оси) предназначено для «выровненных» прямоугольников, то есть прямоугольников, которые нельзя повернуть.

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

Однако, если вы не возражаете против производительности, используйте плоский список прямоугольников и выполните O (n). ² ) поиск действительно был бы проще: в псевдокоде:

function intersection_free(rectangles)
    for rect in rectangles
        for rect2 in rectangles
            if intersects(rect, rect2)
                return false;

    return true;

Простота - замечательная вещь, не правда ли?

Answer 2

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

Однако в вашем конкретном случае - а если размер плоскости ограничен - вы можете использоватьсетка (скажем, 100x100) ячеек, которая делит плоскость и хранит список прямоугольников в каждой ячейке в соответствии с верхними левыми кординатами каждого прямоугольника.При поиске столкновения ищите в соответствующей ячейке и только у ее соседей.Так как размер ваших прямоугольников постоянен, это может быть лучшим решением для вас.Обратите внимание, что двумерный массив можно сохранить в одномерном массиве, где каждый индекс ячейки сетки равен 100X + Y.Теперь вы можете хранить ячейки сетки на карте для экономии памяти.

Если вы сталкиваетесь с проблемой малого / медленного масштаба, просто сохраните прямоугольники в списке и просмотрите список, чтобы найти столкновение.

Answer 3

Я не уверен, что полностью понимаю вашу среду, но вы можете рассмотреть возможность использования двумерного массива, который по сути является матрицей.Каждая точка будет представлять один из ваших квадратов в вашем 2D-пространстве.