Как и большинство 3-х прямоугольников, все всегда будет ориентировано и выровнено по оси xy, и перекрытия нет?Вам повезло, есть O(n<sup>2</sup>) наборов из 3 таких прямоугольников, и довольно легко перечислить их с помощью O(n<sup>3</sup>) работы.Учитывая, что вы имеете дело с небольшим количеством черных прямоугольников для визуального отображения, перечисление их всех и выбор лучшего из них должны быть более чем достаточно быстрыми.
Сначала давайте подумаем о случае с 2 ограничительными прямоугольниками, потому чтоэто проще.Легко проецировать изображение на ось X, а также легко проецировать изображение на ось Y.По крайней мере, один из этих двух проекций будет иметь видимый разрыв без перекрытия.Поэтому мы можем перечислить возможные способы деления на два прямоугольника, сначала спроецировав все чёрные на отрезки линии на оси x, ищем промежутки и для каждой щели восстанавливаем, какую пару ограничивающих прямоугольников мы получили.Затем повторите процедуру с осью Y.И мы получим их все.
Теперь случай с 3 ограничительными прямоугольниками аналогичен.Оказывается, что учитывая 3 непересекающихся прямоугольника, которые ориентированы вдоль оси xy, либо проекция x, либо проекция y должна иметь видимый зазор.Таким образом, мы можем сделать ту же процедуру, что и раньше, но вместо того, чтобы просто построить пару ограничивающих прямоугольников, мы попробуем способы создать один ограничивающий прямоугольник и разделить другой на 2, используя тот же алгоритм.
(Покак вам повезло, что вы только что хотели 3. Этот подход ломается в случае ограничивающего прямоугольника 4. Поскольку тогда возможно иметь 4 ограничивающих прямоугольника, чтобы ни x-проекция, ни y-проекция не имели видимых промежутков.)
Так как же взять n черных прямоугольников, спроецировать их на одну ось (скажем, на ось x) и найти наборы ограничивающих прямоугольников?Вы просто сортируете их, строите максимальные интервалы перекрытия и находите промежутки.Вот так:
function find_right_boundaries_of_x_gaps (rectangles) {
var ordered_rect = rectangles.sort(function (r1, r2) { return r1.x1 <=> r2.x2 });
var gaps = [];
var max_right = ordered_rect[0].x2;
for (var i = 0; i < ordered_rect.length; i++) {
if (max_right < ordered_rect[i].x1) {
gaps.push(max_right);
}
if (max_right < ordered_rect[i].x2) {
max_right = ordered_rect[i].x2;
}
}
return gaps;
}
Учитывая разрыв, легко определить 2-прямоугольный ограничивающий прямоугольник для того, что лежит на каждой стороне.(Еще проще, если у вас есть упорядоченные прямоугольники, чтобы сделать это.)
С этими частями вы теперь сможете писать свой код.К сожалению, наивные подходы дают вам выбор между созданием большого количества повторяющегося кода или созданием большого количества больших структур данных.Однако, если вам удобны замыкания, вы можете решить обе проблемы двумя совершенно разными способами.
Первый - создать замыкания, которые при вызове будут выполнять итерацию по разным структурам данных, которые вам нужны.См. http://perl.plover.com/Stream/stream.html для вдохновения.Идея здесь состоит в том, что вы пишете функцию, которая принимает набор прямоугольников и возвращает поток пар ограничивающих прямоугольников, а затем другую функцию, которая принимает набор прямоугольников, получает поток пар ограничивающих прямоугольников и возвращает поток триплетов.ограничивающих рамок.Затем имейте фильтр, который берет этот поток и находит лучший.
Другой изнутри от этого.Вместо того, чтобы возвращать функцию, которая может перебирать возможности, передавать функцию, перебирать возможности и вызывать функцию для каждой возможности.(Упомянутая функция может также выполнять дальнейшую итерацию.) Если у вас есть какие-либо воздействия на блоки в Ruby, этот подход может иметь для вас большой смысл.
Если вы не знакомы с замыканиями, вы можете пожелатьигнорировать последние несколько абзацев.