Учитывая некоторые AABB, найдите минимальную общую площадь AABB, содержащую их все?

У меня есть ряд объектов, которые нужно отобразить на HTML5 холсты. Мой вход - упорядоченный список ограничивающих прямоугольник по оси. Эти ящики часто перекрываются, но также часто оставляют большие пространства пустого пространства между ними.

Я хотел бы свести к минимуму площадь поверхности холста, которую я должен создать, чтобы отобразить все эти элементы в правильном порядке, в то же время не имея возможности отображать части одного объекта на нескольких холстах (тем самым предотвращая простое решение просто создавая холсты, которые плотно подходят ко всему занятому пространству).

Итак, в основном, я хочу, чтобы все группы объектов были отображены на одном холсте, а объекты с неперекрывающимися объектами должны отображаться на отдельном холсте. Но не все перекрывающиеся объекты должны отображаться на отдельных холстах - например, очень высокий и очень широкий объект, который слегка перекрывается, чтобы сформировать L, должен все же отображаться на двух отдельных холстах, так как их объединение приводит к большому количеству пространства в пустоте в открытой части L.

Поддержание порядка Z также приводит к некоторым трудным случаям. Например, следующее изображение представляет собой одно возможное расположение:

В этом случае вам может понадобиться объединить синий и зеленый слои в один холст, но вы не сможете создать правильное распределение таким образом, не включая также красный слой, и в итоге вы получите много мертвых пространство.

Но вы также не можете просто ограничить объединение слоев с элементами, которые являются последовательными в порядке Z. Порядок Z может совпадать с приведенным выше изображением, но красный элемент может не совпадать с другими, и в этом случае вы хотите объединить синий и зеленый слои.

Я изо всех сил пытаюсь найти хороший алгоритм для этой проблемы. Кто-нибудь хочет перезвонить?

Ответ 1

Вот простое предложение, которое, вероятно, не затрагивает некоторые угловые случаи, но, по крайней мере, частично разрешит его и, надеюсь, предложит лучшее решение:

a = <a z-ordered list of the objects> ;
b = [];
bounds = null;
objects = [];
while ( a.length > 0) {
    c = a.pop();
    if( <c overlaps bounds> && <area of combined canvases> < <area of seperate canvases> || bounds === null) {
         objects.push(c);
         bounds = <union of bounds and c, or bounds of c if bounds is null>;
     } else {
          b.push(c);
     }
     if( a.length === 0) {
          a = b;
          b = [];
          <do something with the current bounds and objects list>
          bounds = null;
          objects = [];
     }
}

Где

 < area of combined canvases> = sum( < area of each canvas> ) - sum( <interesections> )
 < area of seperate conavases> = sum( < area of each canvas> )

Это не будет ловить случаи, когда у вас есть два непересекающихся объекта, которые пересекают общий объект, но, вероятно, могут быть улучшены для этого, просмотрев все объекты с меньшим z-порядком на каждой итерации.

Ответ 2

Начиная с z-упорядоченного массива AABB,

Добавить каждый AABB в массив результатов, также z-упорядоченный

а. Сравните каждый из этих добавленных AABB ко всем другим AABB уже в массиве результатов
- Посмотрите, какая комбинация AABB и любого другого AABB приведет к наименьшей дополнительной площади поверхности. (Возможно, что ни один из них и добавленный AABB не должны сочетаться с другими.)
- Когда комбинация приведет к меньшей площади поверхности, проверьте проблемы пересечения (то есть другую AABB, которая перекрывает другую AABB и перекрывается с помощью AABB для добавления)
- Если таких проблем пересечения не существует, помните об этом другом AABB и продолжайте искать еще лучшие возможные комбинации.
б. Когда будет найдено наилучшая комбинация (или нет комбинации), добавьте добавленный AABB к массиву результатов
- В зависимости от наличия проблем пересечения добавляемый AABB может быть объединен и вставлен вместо другого AABB в массив результатов
- В противном случае комбинация или новый AABB сам по себе добавляется в верхнюю часть массива результатов
Повторите со следующим AABB

Это не довольно алгоритм, и он не делает все отлично. Во-первых, когда найдено сочетание AABB, он не пытается выяснить, может ли быть добавлен третий или четвертый (или пятый) AABB в смесь для улучшения сохранения области.

Здесь реализация этого алгоритма в Javascript:

algorithm = function(allAABBsInSortedOrder) {
    var smallestCanvasSurfaceArea = [];

    goog.array.forEach(allAABBsInSortedOrder, function(aabb) {
        smallestCanvasSurfaceArea = findSmallestSurfaceArea(aabb, smallestCanvasSurfaceArea);
    })
};

findSmallestSurfaceArea = function(nextAABB, combinedAABBsInSortedOrder) {
    var nextAABBarea = areaOf(nextAABB);

    if (!nextAABB) {
        return combinedAABBsInSortedOrder;
    }

    var aabbToCombineWith = {'index': -1, 'area': nextAABBarea, 'upOrDown': 0};

    goog.array.forEach(combinedAABBsInSortedOrder, function(aabb, idx) {
        // Improvement - exhaustive combinations (three AABBs? Four?)
        if (areaOf(combine(aabb, nextAABB) - nextAABBarea <= aabbToCombineWith['area']) {
            var overlapLower = false;
            var overlapNext = false;

            goog.array.forEach(combinedAABBsInSortedOrder, function(intersectAABB, intersectIdx) {
                if (intersectIdx > idx) {
                    if (checkForIntersect(aabb, intersectAABB)) {
                        overlapLower = true;
                    }
                    if (checkForIntersect(nextAABB, intersectAABB)) {
                        overlapNext = true;
                    }
                }
            });

            if (overlapLower && !overlapNext) {
                aabbsToCombineWith['index'] = idx;
                aabbsToCombineWith['area'] = areaOf(aabb);
                aabbsToCombineWith['upOrDown'] = -1;
            }
            else if (!overlapLower && overlapNext) {
                aabbsToCombineWith['index'] = idx;
                aabbsToCombineWith['area'] = areaOf(aabb);
                aabbsToCombineWith['upOrDown'] = 1;
            }
            else if (!overlapLower && !overlapNext) {
                aabbsToCombineWith['index'] = idx;
                aabbsToCombineWith['area'] = areaOf(aabb);
                aabbsToCombineWith['upOrDown'] = 0;
            }
        }
    });

    if (aabbToCombineWith['index'] != -1) {
        var combinedAABB = combine(combinedAABBsInSortedOrder[aabbToCombineWith['index']], nextAABB);
        if (aabbToCombineWith['upOrDown'] == -1) {
            combinedAABBsInSortedOrder[aabbToCombineWith['index']] = combinedAABB;
        }
        else {
            combinedAABBsInSortedOrder.push(combinedAABB);
            combinedAABBsInSortedOrder.splice(aabbToConbineWith['index'], 1);
        }
    }
    else {
        combinedAABBsInSortedOrder.push(nextAABB);
    }

    return combinedAABBsInSortedOrder;
};

Ответ 3

Поскольку это оптимизация, вы, вероятно, не заинтересованы в алгоритме с большим вычислительным требованием, даже если результаты являются оптимальными. Вы должны сбалансировать время работы с хорошими результатами.

Без Z-порядка

Для простоты сначала рассмотрим задачу без z-порядка. Простое и эффективное решение состоит в том, чтобы жадно рассматривать и комбинировать прямоугольники по два за раз. Умение заключается в эффективном рассмотрении как комбинированных ящиков, так и несвязанных, что гарантирует, что в конце не будет сохраняться парная комбинация слева.

function minBoxes(boxes) {
    var result = [];

    boxes.forEach(function(box1) {
        var bestCombinedBox,
            bestIndex;
        result.reduce(function(bestSavings, box2, i) {
            var x = Math.min(box1.x, box2.x),
                y = Math.min(box1.y, box2.y),
                w = Math.max(box1.x + box1.w, box2.x + box2.w) - x,
                h = Math.max(box1.y + box1.h, box2.y + box2.h) - y;
            var savings = box1.w * box1.h + box2.w * box2.h - w * h;
            if(savings > bestSavings) {
                bestCombinedBox = {x:x, y:y, w:w, h:h};
                bestIndex = i;
                return savings;
            }
            return bestSavings;
        }, 0);
        if(bestCombinedBox) {
            result[bestIndex] = bestCombinedBox; //faster than splicing
        } else {
            result.push(box1);
        }
    });

    return result;
}

minBoxes([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, y:5}]);

Это выполняется в O(N*N), когда N - количество ящиков.

Конечно, даже эта более простая проблема имеет очень сложные случаи. Рассмотрим следующие четыре прямоугольника.

Никогда не выгодно комбинировать любые два из этих прямоугольников. Лучше всего объединить все четыре, но если вы проанализируете их попарно, вы никогда ничего не соберете.

Тем не менее, этот относительно быстрый алгоритм работает в большинстве случаев замечательно (JSFiddle), поэтому мы его сохраним.

С Z-порядком

Если прямоугольники имеют z-порядок, то во время наших вычислений объединенные прямоугольники можно считать имеющими диапазон z-порядков. Я добавлю свойства minZ и maxZ для каждого прямоугольника, чтобы отразить этот факт. Я также добавлю набор (фактически, объект, чьи ключи являются значением набора), overlapping, всех прямоугольников, на которые накладывается прямоугольник.

Я буду использовать minZ, maxZ и overlapping, чтобы гарантировать, что любые прямоугольники, которые я совмещаю, не имеют третьего прямоугольника, который они оба перекрывают, чей порядок z будет находиться между ними. Я также сортирую прямоугольники сначала по z-порядку, который может работать лучше, когда есть много перекрывающихся прямоугольников. (Я немного не уверен в этом, но это не может повредить.)

Это выполняется в O(N*N*K) времени, где N - количество ящиков, а K - количество ящиков, каждое поле которых перекрывается.

ПРИМЕЧАНИЕ. Ниже я предполагаю, что z-порядки уникальны. Если это не так, их нетрудно сделать.

function minBoxes(boxes) {
    boxes = boxes.sort(function(box1, box2) {
        return box1.z - box2.z;
    }).map(function(box1) {
        var overlapping = {};
        boxes.forEach(function(box2) {
            if(box1 != box2
                && box1.x + box1.w > box2.x
                && box2.x + box2.w > box1.x
                && box1.y + box1.h > box2.y
                && box2.y + box2.h > box1.y
            ) {
                overlapping[box2.z] = true;
            }
        });
        return {
            x: box1.x,
            y: box1.y,
            w: box1.w,
            h: box1.h,
            minZ: box1.z,
            maxZ: box1.z,
            overlapping: overlapping
        };
    });

    var result = [];

    boxes.forEach(function(box1) {
        var bestBox,
            bestIndex;

        function combinedBox(box2) {
            var x = Math.min(box1.x, box2.x),
                y = Math.min(box1.y, box2.y);
            return {
                x: x,
                y: y,
                w: Math.max(box1.x + box1.w, box2.x + box2.w) - x,
                h: Math.max(box1.y + box1.h, box2.y + box2.h) - y
            };
        }
        result.reduce(function(bestSavings, box2, i) {
            //check z-order
            var min = Math.max(Math.min(box1.minZ, box2.maxZ), Math.min(box1.maxZ, box2.minZ)),
                max = Math.min(Math.max(box1.minZ, box2.maxZ), Math.max(box1.maxZ, box2.minZ));
            for(var z in box1.overlapping) {
                if(min < z && z < max && z in box2.overlapping) {
                    return bestSavings;
                }
            }
            for(var z in box2.overlapping) {
                if(min < z && z < max && z in box1.overlapping) {
                    return bestSavings;
                }
            }
            //check area savings
            var combined = combinedBox(box2);
            var savings = box1.w * box1.h + box2.w * box2.h - combined.w * combined.h;
            if(savings > bestSavings) {
                bestBox = box2;
                bestIndex = i;
                return savings;
            }
            return bestSavings;
        }, 0);
        if(bestBox) {
            var combined = combinedBox(bestBox);
            combined.minZ = Math.min(box1.minZ, bestBox.minZ);
            combined.maxZ = Math.max(box1.maxZ, bestBox.maxZ);
            combined.overlapping = box1.overlapping;
            for(var z in bestBox.overlapping) {
                combined.overlapping[z] = true;
            }
            result[bestIndex] = combined; //faster than splicing
        } else {
            result.push(box1);
        }
    });

    return result.map(function(box) {
        return {
            x: box.x,
            y: box.y,
            w: box.w,
            h: box.h,
            z: (box.minZ + box.maxZ) / 2 //really, any value in this range will work
        };
    });
}

minBoxes([{x:0, y:0, w:5, h:5, z:0}, {x:1, y:1, w:5, y:5, z:1}]);

Пример OP
Пример OP, но с переупорядоченными z-порядками (чтобы было желательно объединение)
Случайные входы

Есть более простые способы сделать это, например, сортировать по z-порядку заранее и надеяться на лучшее, или не позволять объединять два прямоугольника, если между ними расположен перекрывающий прямоугольник (только) один из них. Но эти подходы охватывают меньше случаев.

Ответ 4

У вас есть интересный вопрос!

Что-то рассмотреть...

Поскольку холст уже оптимизирован для скорости рисования, , я предполагаю, что простое рисование всех прямоугольников в z-порядке будет вашим самым быстрым решением. Таким образом, большая часть чертежа выгружается из CPU на GPU, и ваши 2 процессора делают то, что они делают лучше всего.

В любом случае, вернемся к вашему вопросу.

Оптимизация первого прохода...

В этом ядре вас задает вопрос о теории столкновений: какой из моих прямоугольников пересекает друг друга (которые сталкиваются)?

Таким образом, ваш первый проход будет заключаться в том, чтобы организовать ваши прямоугольники в "сваи", которые минимально пересекают друг друга.

Если вы нарисуете каждую из этих дискретных "свай" на отдельные холсты, вы эффективно разделите свои прямоугольники на управляемые холсты.

Текущая теория игр придумала некоторые очень хорошие алгоритмы столкновений. Один называется Quadtree и имеет сложность, приближающуюся к O (n log (n)). Здесь ссылка на Quadtree:

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

После первого прохода...

Quadtree делает пространственную сортировку - очень хорошо. Когда Quadtree выполняется, у вас есть непересекающиеся груды прямоугольников.

Хорошо, я соврал. Результаты в основном непересекаются. Здесь вы можете рассмотреть компромисс между совершенством и практичностью. Совершенство будет стоить вам некоторой вычислительной мощности. Практичность отказывается от совершенства, но также и снижает вычислительную мощность.

"Я принимаю практичность..."

Скважины Quadtree являются хорошей отправной точкой. Если вы признаете некоторые недостатки быстрой и недорогой путь состоит в том, чтобы просто отсортировать каждую кучу в z-порядке и нарисовать каждую кучу на отдельном холсте. Тогда у вас есть "очень хорошее" решение. Недостаток: этот практический подход может позволить некоторым прямоугольникам, которые охватывают 2 свая, неправильно накладываться на 1 из двух свай. Если ваш дизайн может жить с этим, вы будете золотым.

"Я хочу совершенство..."

Скважины Quadtree являются хорошей отправной точкой.

Теперь, сортируйте каждую кучу в z-порядок, и вы получили 90 +% от всех ваших исправлений.

Любой прямоугольник, который не распространяется на соседнюю кучу, является полным и правильно упорядочен.

Thats 90 +% ваших исправлений, сделанных с помощью Quadtree plus Sorts!.

То, что остается, - это 10% -ые "нарушительные" прямоугольники, которые частично простираются в 1 куче и частично в другой куче.

Как вы должным образом переплете эти нарушающие права на оба соседних прямоугольника?

Theres аккуратный трюк здесь!.

Фон на Quadtree: если вы нарисуете каждую кучу прямоугольников прямоугольников с помощью отдельного холста, объединенный набор холстов с холстом полностью и без перекрытия заполняет оригинальный холст.

Подумайте о кучевых полотнах как кусочки головоломки, которые полностью строят полную картину - не перекрываются.

Итак, трюк заключается в том, чтобы нарисовать любой нарушающий прямоугольник в обоих штабелях!

Почему? Ректы, которые выходят за пределы холста, автоматически обрезаются (холст не будет отображаться за его пределами). Это именно то, что мы хотим!

Результат состоит в том, что холст # 1 будет правильно нарисовать половину наружного прямоугольника, а соседний холст # 2 будет правильно заполнять вторую половину.

Результат: Совершенство без дополнительной математики за пределами алгоритма Quadtree плюс Сортировка!

И имейте в виду, что Quadtree предназначен для обработки конфликтов в реальном времени, поэтому он быстрый и эффективный.

[Обновление, основанное на дополнительном комментарии от опроса]

Я вижу... так что память - это чисто ключ.

Затем, если ваш дизайн позволяет вам вообще не использовать html-холст и вместо этого использовать изображение или несколько изображений.

Объем памяти холста всегда примерно в 4,5 раза больше размера статического изображения (ouch!).

Изображения Plus могут быть быстро увеличены с помощью графического процессора, поэтому память очищается/восстанавливается намного быстрее с помощью изображений.

Если ваш дизайн требует, чтобы rects был динамическим, вы использовали бы гораздо меньше памяти, просто создавая несколько изображений и преобразовывая их с помощью CSS. Кроме того, побочным преимуществом было бы гораздо меньше вычислений на процессоре.

Еще лучше, если ваши прямоугольники являются "разными цветными ящиками с рамкой", вы получите огромную экономию памяти за счет того, что каждый прямоугольник является элементом div (с цветом фона и границей). Затем выполняйте преобразования с CSS на div. Огромные сбережения!

Тем не менее, ваш первоначальный вопрос остается интересным упражнением;)

Ответ 5

Эта проблема хорошо известна в 3D для построения высокопроизводительных иерархий AABB при обнаружении лучей или обнаружении конфликтов. Попробуйте Google для "BVH", "эвристика поверхности" и/или "SAH". Раздел 3.1 следующей работы имеет хороший эвристический алгоритм; который должен быть легко адаптирован к вашему 2D-случаю: http://graphics.stanford.edu/~boulos/papers/togbvh.pdf

Ответ 6

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

Учитывая этот многоугольник, вы можете легко вычислить минимальную ширину и высоту вашего холста как height = max(y coordinates) - min(y coordinates) width = max(x coordinates) - min(x coordinates)

Z-порядок не имеет значения для вычисления выпуклой оболочки.