найти максимальное перекрытие области эффекта на 2d сетке

Question

Я надеюсь написать программу, которая поможет мне оптимизировать сетку 2d.В этой сетке есть «блоки», диапазон которых определяет область его действия.Многие блоки могут быть размещены на сетке.Каждый блок может занимать более 1 плитки, но всегда квадратный.Я хочу узнать максимальное количество раз, когда область эффекта может перекрывать одну позицию XY.

Мне нужно выяснить это для 36 комбинаций (4 типа блоков - 1x1, 2x2, 3x3 и 4x4 и диапазоны 1-9)

Область воздействия всегда в квадратешаблон.В приведенном ниже примере буквы являются блоками, а цифры - областью действия.A - это блок 1x1 с областью действия, равной 1. B - блок 1x1 с областью действия, равной 2. А C - блок 2x2 с зоной действия, равной 1.

X X X X X
X 1 1 1 X
X 1 A 1 X
X 1 1 1 X
X X X X X

X X X X X X X
X 2 2 2 2 2 X
X 2 2 2 2 2 X
X 2 2 B 2 2 X
X 2 2 2 2 2 X
X 2 2 2 2 2 X
X X X X X X X

X X X X X X
X 1 1 1 1 X
X 1 C C 1 X
X 1 C C 1 X
X 1 1 1 1 X
X X X X X X

Я могу разместить столько блоков на сетке, сколько захочу, и я хочу выяснить, сколько раз область эффекта перекрывает целевой тайл.Например, если у меня есть плитка A (1x1 с 1 диапазоном), я максимизирую область эффекта, окружая цель T. Поэтому ответ здесь будет 8.

X X X X X
X A A A X
X A T A X
X A A A X
X X X X X

Кто-нибудь знает, как я могувыяснить это для других комбинаций?Спасибо!

Answer 1

Вам нужна некоторая форма пространственного разбиения, чтобы было легко найти блоки, которые влияют на определенную позицию. Погуглив «древовидные алгоритмы», вы должны получить представление о различных способах разбиения пространства, но общая идея такова:

for each block
  addblock (root, block)

addblock (node, block)
  if block fits inside node
    if there are child nodes
      for each child
        addblock (child, block)
    else
      add block to node by dividing into area occupied by block and areas not occupied by block, moving any blocks at this node into all new child nodes
  else
    if there are child nodes
      for each child
        addblock (child, block)
    else
      add block to node block list

Затем, чтобы найти количество блоков, покрывающих квадрат, найдите в дереве узел, покрывающий данный квадрат, а затем посмотрите, сколько блоков в этом узле.

Answer 2

Вам нужна кривая заполнения пространства, такая как Z-кривая или кривая Гильберта, а затем вместо того, чтобы вычислить индекс, преобразуйте его в ключ дерева квадрантов для каждой плитки.SFC сводит 2D-проблему к 1D-задаче.Затем с новым ключом вы хотите выполнить DFS или BFS для поиска перекрывающихся плиток.Я написал класс для sfc в php на phpclasses.org (кривая Гильберта).Вы можете скачать.