Итак, если бы я пытался это сделать, первое, что я бы сделал, это придумал единое пространство сетки. Найдите все уникальные координаты x и y и создайте отображение на индексное пространство. Поэтому, если у вас есть значения x {-1, 1.5, 3.1}, сопоставьте их с {0, 1, 2} и аналогично для y. Тогда каждый прямоугольник может быть точно представлен этими упакованными целочисленными координатами.
Тогда я бы выделил битовый вектор или что-то, что покрывает всю сетку, и растеризовал бы ваши прямоугольники в сетке. Хорошая особенность сетки состоит в том, что с ней действительно легко работать, и, ограничивая ее уникальными координатами x и y, она минимальна и точна.
Один из способов найти довольно быстрое решение - просто сбросить каждый «пиксель» вашей сетки. Проведите их обратно через ваше отображение, и все готово. Если вы ищете более оптимальное количество прямоугольников, у вас есть какая-то проблема с поиском.
Давайте посмотрим на 4 соседних пикселя, маленький квадрат 2х2. Когда я пишу алгоритмы, подобные этим, я обычно думаю о вершинах, ребрах и гранях. Итак, это лица вокруг вершины. Если 3 из них включены, а 1 выключен, то у вас есть вогнутый угол. Это единственный недействительный случай. Например, если у меня нет вогнутых углов, я просто беру экстенты и выкидываю все это как один прямоугольник. Для каждого вогнутого угла вам нужно решить, следует ли разделять по горизонтали, вертикали или по обоим направлениям. Я думаю о разделении как о маркировке краев, чтобы не пересекаться при поиске экстентов. Вы также можете сделать это как раскраски в наборы, что вам проще. * +1007 *
Вогнутые углы и их разделенные направления - это ваше пространство поиска. Вы можете использовать любой алгоритм оптимизации, какой захотите. Ветвь / граница может хорошо работать. Могу поспорить, что вы могли бы найти простую эвристику, которая работает хорошо (например, если есть другой вогнутый угол прямо напротив того, который вы рассматриваете, всегда разделяйте в этом направлении. В противном случае делите в более коротком направлении). Вы можете просто пойти жадным. Или вы можете просто разделить каждый вогнутый вершин в обоих направлениях, что, как правило, даст вам меньше прямоугольников, чем выводить каждый «пиксель» в виде прямоугольника, и это будет довольно просто.
Читая это, я понимаю, что могут быть области, которые неясны. Дайте мне знать, если вы хотите, чтобы я что-то прояснил.