Упаковка прямоугольников для компактного представления

Question

Упаковка прямоугольников для компактного представления

Это ответ на ваш заголовок.

Строка pFile = fopen("C:\\myfile.txt", "w"); вызывает функции Windows API и, вероятно, сбрасывает последний код ошибки. Таким образом, правильное обращение с последним кодом ошибки сохраняет его в переменную сразу после интересного вызова API. Попробуйте приведенный ниже код, и вы должны получить реальный код ошибки после вызова VirtualProtectEx.

if (!VirtualProtectEx(hProcess, (LPVOID)pAddr, sizeof(DWORD), PAGE_EXECUTE_READWRITE, &oldProtection)) {
    int err_code = GetLastError();
    printf("\n VirtualProtectEx() error - %d\n", err_code):

    //=============== To debug from service application ===================

    FILE * pFile = fopen("C:\\myfile.txt", "w");
    if (pFile != NULL)
    {
        fprintf(pFile, "%d\n", err_code);
        fclose(pFile);
    }
    ...

6

rectangles packing algorithm

задан stephanea 30 September 2008 в 14:39

6 ответов

Другие вопросы по тегам:

rectangles packing algorithm

Похожие вопросы:

score 2 · Answer 1

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

score 2 · Answer 2

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

score 1 · Answer 3

Являются прямоугольники всей той же высотой? Если они, и проблема, какой строкой вставить каждый прямоугольник, то проблема сводится к ряду ограничений по всем парам прямоугольников (X, Y) формы, "прямоугольник X не может быть в той же строке как прямоугольник Y" когда прямоугольник X перекрытий в направлении X с прямоугольником Y.

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

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

score 1 · Answer 4

Что-то вроде этого?

Отсортируйте свой набор прямоугольников x-position
запишите метод, который проверяет, какие прямоугольники присутствуют на определенном интервале оси X
```
Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){
...
}
```

цикл по набору прямоугольников

Collection<Rectangle> toDraw;
Collection<Rectangle> drawn;
foreach (Rectangle r in toDraw){
Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn);
int y = 0;
foreach(Rectangle overlapRect in overlapping){
y += overlapRect.height;
}
drawRectangle(y, Rectangle);
drawn.add(r);
}

score 0 · Answer 5

Поместите подобную Тетрису игру в Вас веб-сайт. Генерируйте блоки, которые падают и размер области воспроизведения на основе Ваших параметров. Присудите очки плеерам на основе компактности (меньше свободного пространства = больше точек) их дизайна. Заставьте своих посетителей веб-сайта выполнять работу для Вас.

score 0 · Answer 6

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

Теперь задача состоит в том, чтобы присвоить координаты y набору прямоугольников, чьи координаты x заданы, если я правильно вас понял.

Итерация по массиву прямоугольников. Для каждого прямоугольника инициализируйте его координату y равной 0. Затем в цикле увеличивайте координату y прямоугольника до тех пор, пока он не будет пересекаться ни с одним из ранее размещенных прямоугольников (вам нужно отслеживать, какие прямоугольники были размещены ранее). Зафиксируйте только что найденную координату y и переходите к обработке следующего прямоугольника.