Собственно, столкнулся на производстве с такой вот задачей. Дан 3-мерный не обязательно выпуклый многогранник (mesh), грани — треугольники. Задача такая: построить один или несколько многогранников вложенных в данный так, чтобы суммарный объем этих многогранников был максимальным и никакая точка внутренних многогранников не была ближе k мм от внешнего. Проще говоря — вырезать полость (полости) максимального объема так, чтобы "стенки" везде были толщины не менее k мм.

Нужно это, естественно, для 3Д печати. Вот здесь показано как это делать, например, для куба: https://www.shapeways.com/tutorials/creating-hollow-objects Наши модели, само собой, более сложные — фигурки людей и пр.

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

Соответственно требования такие:

• максимальный внутренний объем

• толщина стенок

• количество "внутренних" граней должно быть не больше, чем количество граней в исходном меше

• работает быстро и не жрет память, в идеале O(количество вершин)

• естественно, никаких самопересечений, вырожденных граней и прочего

У кого нибудь есть идеи как написать такой алгоритм? Буду рад любым идеям — можно начать с решения в 2мерном случае, например. Заранее спасибо :)