Итак, если бы я пытался это сделать, первое, что я бы сделал, это придумал бы единое пространство сетки. Найдите все уникальные координаты x и y и создайте сопоставление с индексным пространством. Итак, если у вас есть значения x {-1, 1,5, 3,1}, сопоставьте их с {0, 1, 2} и аналогично для y. Тогда каждый прямоугольник можно точно представить с помощью этих упакованных целочисленных координат.
Затем я выделял битвектор или что-то, что покрывает всю сетку, и растрировал ваши прямоугольники в сетке. Хорошая вещь в сетке заключается в том, что с ней действительно легко работать, и, ограничивая ее уникальными координатами x и y, она минимальна и точна.
Один из способов найти довольно быстрое решение — просто выгрузить каждый «пиксель» вашей сетки. Прогнать их обратно через отображение, и все готово. Если вы ищете более оптимальное количество прямоугольников, то у вас есть своего рода проблема поиска.
Посмотрим на 4 соседних пикселя, небольшой квадрат 2х2. Когда я пишу подобные алгоритмы, я обычно думаю о вершинах, ребрах и гранях. Итак, это грани вокруг вершины. Если 3 из них включены, а 1 выключен, то у вас вогнутый угол. Это единственный неправильный случай. Например, если у меня нет вогнутых углов, я просто беру экстенты и выгружаю все это как один прямоугольник. Для каждого вогнутого угла вам нужно решить, следует ли разделить его по горизонтали, по вертикали или по обоим направлениям. Я думаю о разделении как о маркировке ребер, чтобы не пересекать их при поиске экстентов. Вы также можете сделать это, раскрашивая наборы, как вам будет проще.
Вогнутые углы и направления их разделения - это ваше пространство поиска. Вы можете использовать любой алгоритм оптимизации, какой захотите. Branch/bound может работать хорошо. Бьюсь об заклад, вы могли бы найти простую эвристику, которая хорошо работает (например, если есть еще один вогнутый угол прямо напротив того, который вы рассматриваете, всегда разделяйте в этом направлении. В противном случае разделяйте в более коротком направлении). Ты можешь просто стать жадным. Или вы можете просто разделить каждую вогнутую вершину в обоих направлениях, что, как правило, даст вам меньше прямоугольников, чем вывод каждого «пикселя» в виде прямоугольника, и это будет довольно просто.
Читая это, я понимаю, что могут быть области, которые неясны. Дайте мне знать, если вы хотите, чтобы я что-то прояснил.
person
tfinniga
schedule
03.05.2010
