Как я могу эффективно хранить сетку прямоугольников?
Так что я думал о создании игры для строителей с прямоугольниками различной формы, а не только с квадратами, но я не могу придумать эффективный способ сделать это. Например, я не хочу иметь сетку плиток, таких как тетрис, которые составляют каждую форму. Я хочу, чтобы каждая часть была одним объектом с шириной и высотой. Например, кусок 2 * 3 не будет занимать 6 плиток, это будет просто один прямоугольник. Я должен уметь эффективно организовывать фигуры и иметь возможность получать фигуры по определенной координате. Если бы я просто использовал двумерный массив плиток, он использовал бы память, которая мне не нужна.
Решение
Получение прямоугольника по любой заданной координате очень дорого для ресурсов, независимо от того, как вы это делаете, но, вероятно, наиболее эффективным способом было бы создать свободную сетку, к которой не привязаны прямоугольники. Всякий раз, когда фигура перемещается, она обновляет двумерный массив со ссылкой на все квадраты, которые он полностью или частично содержит. Всякий раз, когда задана координата, вычислите, в каком квадрате сетки находится координата, и затем из нее можно выполнить более обширные вычисления, чтобы проверить, находится ли координата внутри прямоугольника или нет.
Другие решения
Имеется в виду опубликовать это ранее, я знаю, что вы уже приняли ответ, но вы можете рассмотреть следующее.
Я думаю, я понимаю, что вы спрашиваете. Вы хотите проверить, к какому прямоугольнику принадлежит плитка (если есть), проверив границы прямоугольника. Таким образом, чтобы проверить, принадлежит ли верхняя правая плитка в этом квадрате к любому прямоугольнику, где любой - это плитка, которая не имеет прямоугольника
a a a -
a a a b
a a a b
a a a b
вы бы проверили прямоугольник a и прямоугольник b для плитки (0,3) и видите, что это не принадлежит ни одному.
Альтернативой, которую вы пытаетесь избежать, является установка каждой плитки в прямоугольник:
(0, 0).parent = 'a'
(0, 1).parent = 'a'
...
(2, 2).parent = 'a'
так далее
или что-то похожее на это.
Компромисс для каждого решения отличается «
В первом случае вам придется выполнять множество сравнений каждый раз, когда вы хотите найти прямоугольник, к которому принадлежит мозаика. O(n) сравнения, где вы будете сравнивать n раз в худшем случае, 1 в лучшем случае и n/2 Сравнение в среднем (если каждый тайл имеет равный шанс на принадлежность к прямоугольнику, что не так в играх, подобных тетрису).
Во втором решении вы должны сохранить родительскую переменную для каждой плитки. Это увеличивает использование памяти, но временная сложность всегда остается O(1),
Каждый из них может быть лучше в зависимости от того, как, вероятно, будет настроена ваша сетка:
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a - e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
Проверка родительского элемента определенной плитки выполняется довольно быстро: вы просто проверяете 5 прямоугольников, если у плитки нет ни одного, у нее нет родительского элемента.
Проверить, есть ли у плитки родитель, так же быстро.
Однако, когда вы начинаете иметь все больше и больше прямоугольников …
a b c d e f g h i j k l m n o p q r s t
A B C D E F G H I J K L M N O P Q R S T
u v w x y z U V W X Y Z 1 2 3 4 5 6 7 8
9 0 ...
...
Вы должны сделать МНОГО сравнений, чтобы найти, есть ли у конкретной плитки родитель или нет. Вместо того, чтобы точно определять координату и проверять ее родительское значение, вы должны проверить каждый прямоугольник, чтобы увидеть, есть ли плитка в каком-либо из них.
Я предлагаю вам просто использовать сетку NxN и сохранять значение родительского прямоугольника для каждой плитки (первое решение), если только вы не знаете, что не собираетесь использовать столько прямоугольников или сетка будет заполняться в основном пустыми пространствами.
Я бы просто создал класс Прямоугольник с ширина а также Рост, тогда я бы использовал массив экземпляров этого класса.
Прямоугольники перекрываются? Если нет, вы можете использовать класс RectangleGrid здесь: https://github.com/eyal0/OctoPrint-Slicer/blob/master/src/RectanglePacker.js#L10
Добавление прямоугольника потенциально медленное, но для вашего случая использования может работать.
Запрос прямоугольника в заданной позиции — O (nlogn).