Интересная задача

← →
Unknown user © (2009-10-09 16:53) [0]

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

Какие будут предложения?

← →
MBo © (2009-10-09 17:09) [1]

Это оптимизационная задача двумерной упаковки 2D Packing
Она сложна даже для случая только прямоугольников (bin packing)

← →
Unknown user © (2009-10-09 17:12) [2]

> MBo ©

Спасибо за подсказку. Имеются готовые решения?

← →
MBo © (2009-10-09 18:18) [3]

> Имеются готовые решения?
для прямоугольников видел, но линков нет.

← →
Unknown user © (2009-10-10 13:22) [4]

Подскажите еще, пожалуйста, в какую сторону копать в задаче объединения трехмерных фигур, представленных сеткой треугольников (mesh). Фигуры - это модели зданий, чаще всего набор параллелепипедов. После объединения появляются невидимые грани, их надо удалять. Кроме того при пересечении формируются новые грани. Как может называться такая задача. По запросу merging meshes ничего путного не нашел.

← →
MBo © (2009-10-10 14:42) [5]

возможно, это относится к constructive solid geometry

Спасибо, действительно CSG.

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

Тут и возникает проблема. Вроде бы несложная математика, комбинация 3-х поворотов, но не получается. Может есть готовые функции для разворота грани параллельно заданной плоскости и возвращение результирующей грани в исходное положение?

подобные вещи есть,например, в библиотеке wildmagic
www.geometrictools.com

Интересная задача Найти похожие ветки