=Paper= {{Paper |id=Vol-1787/295-301-paper-50 |storemode=property |title=Прикладные проблемы решения задачи вписывания многогранников (Applied problems of polyhedron inscribing task solving) |pdfUrl=https://ceur-ws.org/Vol-1787/295-301-paper-50.pdf |volume=Vol-1787 |authors=Denis Kokorev }} ==Прикладные проблемы решения задачи вписывания многогранников (Applied problems of polyhedron inscribing task solving)== https://ceur-ws.org/Vol-1787/295-301-paper-50.pdf

Прикладные проблемы решения задачи вписывания
многогранников
Д. С. Кокорев
Федеральное государственное бюджетное учреждение науки Институт Проблем Передачи Информации
им. А.А.Харкевича Российской академии наук
Россия, 127051, г. Москва, Большой Каретный переулок, д.19 стр. 1.
E-mail: korvin-d@yandex.ru

В статье рассматривается задача нахождения многогранников заданной формы внутри других мно-
гогранников. Данная задача является частным случаем третьей части 18-ой проблемы Гильберта. Она
имеет практическое применение в компьютерном моделировании трехмерных объектов, решении задач
раскроя и упаковки, автономном перемещении роботов, ювелирной промышленности. В статье предла-
гается метод нахождения вписанных многогранников, основанный на сведении задачи к задаче нелиней-
ного программирования. Описываются основные функциональные ограничения, использующиеся для
данной задачи и программные ресурсы, позволяющие эффективно работать с задачами нелинейного про-
граммирования. Приведенный метод требует довольно хорошее начальное решение. В качестве старто-
вой точки могут быть взяты данные работы других менее точных алгоритмов. Самым распространенным
из таких алгоритмов является гомотетичное раздувание искомого объекта под разными углами и с цен-
тром масс в разных точках до пересечения с внешним многогранником. Описанию и недостаткам этих
методов посвящена отдельная глава. Главным недостатком является локальность решения. А также не-
обходимость в переборе жестко заданных форм многогранника. Предлагается аналог этих методов, осно-
ванный на задаче нелинейного программирования. Предложенный метод основывается на представлении
любого возможного движения в виде композиции поворота, трансляции и гомотетии. В описанном экс-
перименте матрица поворота представлена через кватернионы. Придуманный алгоритм работает качест-
веннее имеющихся аналогов, но пока недостаточно быстро для прикладных целей. Планы дальнейшего
развития алгоритма описаны в заключении.

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

Работа выполнена при финансовой поддержке Российского Научного Фонда(№16-11-10352)

295
1. Введение
Одной из классических математических проблем является третья часть 18-ой проблемы
Гильберта. В своей общей постановке она посвящается упаковкам одних тел другими. В случае
упаковки правильными объектами, например, сферами, существуют доказанные результаты.
Например: сильная проблема тринадцати сфер [Tarasov, 2010], проблема двадцати пяти сфер
[Мусин, 2003] и гипотеза Кеплера [Hales, 1994]. Для случая двухмерных многогранников и
простых трехмерных объектов есть ряд решенных задач. Подобные задачи перечислены в ста-
тье Валиахметовой Ю.И. и Филипповой А.С.[Валиахметова, Том 18, №1, стр 62]. В случае упа-
ковки многомерных многогранников в другие многогранники, задача является значительно бо-
лее сложной, и пока не существует теоретических подходов, позволяющих подступиться к этой
задаче в общем виде.
Частным случаем этой проблемы является задача нахождения в выпуклом многограннике
произвольной формы объекта заданной формы с наибольшим объемом. Описанные в статье
подходы используются в прикладных целях, когда нужно из большого тела вырезать части оп-
ределенной формы. Например, в ювелирной промышленности или при нарезке гранитных плит,
удовлетворяющих заданным параметрам.
Первоначальным этапом алгоритма, решающего эту задачу, является нахождение старто-
вой точки - начального приблизительного расположения объекта. В качестве стартовой точки
могут быть взяты данные работы других менее точных алгоритмов. Самым распространенным
из таких алгоритмов является гомотетичное раздувание под разными углами и с центром масс в
разных точках искомого объекта до пересечения с внешним многогранником. Таким образом
находится стартовая точка с максимальным объемом, но строго зафиксированной формой. Да-
лее необходимо двигая вершины на незначительные расстояния найти положение с максималь-
ным объемом и удовлетворяющие некоторым требованиям на форму.

2. Используемые термины
Определение 1. Вписыванием одного многогранника в другой будем называть нахождение
многогранника, комбинаторно эквивалентного первому, максимального объема и содержаще-
гося во втором.
Определение 2. Будем говорить, что два многогранника обладают одинаковой комбина-
торной структурой тогда и только тогда, когда изоморфны их граничные комплексы [Много-
гранники, графы, оптимизация, 1981]. Такие многогранники называются комбинаторно эквива-
лентными.
Определение 2.1. Комплексом называется конечная совокупность K многогранников в Ed,
удовлетворяющая условиям: 1) наряду с каждым многогранником М из семейства K в K входит
также и любая грань многогранника М; 2) пересечение любых двух многогранников из K явля-
ется гранью каждого из них.
Определение 2.2. Пусть М — d-многогранник (размерности d ) в Еd , и пусть целое число k
удовлетворяет условию 0 < k < d. Множество всех граней многогранника М размерности, не
превышающей k, является комплексом, который называется k-скелетом многогранника М.
Определение 2.3. (d - 1)-скелет многогранника М будем обозначать символом F(М) и на-
зывать граничным комплексом многогранника.
Определение 2.4. Два комплекса K и K' называются изоморфными комплексами, если ме-
жду ними существует взаимно однозначное отображение φ, сохраняющее операцию включе-
ния:
F1 ⊂ F2  φ (F1)⊂ φ (F2)

296
Определение 3. Задачей нелинейного программирования (НП-задача) называется оптими-
зационная задача следующего вида:
f(x) → min
при ограничениях:
gL ≤ g(x) ≤ gU
xL ≤ x ≤ xU
где n
– оптимизационные переменные с верхними и нижними ограничениями:
n n
xL , xU
f : → - целевая функция
n

g: n → - общие нелинейные ограничения с верхними и нижними границами:
m m
gL , gU
f(x) и g(x) могут быть линейными или нелинейными, выпуклыми или невыпуклыми.
Определение 4. AMPL [Fourer, 2003] (A Modeling Language for Mathematical
Programming ) — язык программирования высокого уровня для описания и решения слож-
ных задач оптимизации и теории расписаний. Главным преимуществом AMPL является подо-
бие его синтаксиса математической записи задач оптимизации, что позволяет дать очень крат-
кое и легко читаемое определение задач математического программирования. Для решения за-
дач, написанных на AMPL, используются вычислительные солверы.
Определение 5. Нелинейный солвер – программа для решения задач нелинейного про-
граммирования, использующая один из алгоритмов таких как: метод градиентного спуска, ме-
тод внутренней точки или квазиньютоновские методы.
Определение 6. Выпуклой оболочкой множества X называется наименьшее выпуклое мно-
жество, содержащее X.

3. Метод колебания вершин
Даны два выпуклых многогранника – внешний и внутренний. Внутренний многогранник
является начальным приблизительным решением задачи и содержится внутри внешнего. Тре-
буется максимально увеличить, незначительно изменяя положение вершин, внутренний много-
гранник так, чтобы он остался вписанным и сохранил свою комбинаторную структуру. Помимо
комбинаторной структуры могут быть добавлены соотношения каких-либо размеров фикси-
рующих форму многогранника необходимые для прикладного использования алгоритма.
Поставленную геометрическую задачу необходимо записать в терминах задачи нелиней-
ного программирования. В качестве целевой функции f(x) в нашем случае берется объем внут-
реннего многогранника. Основными ограничениями g(x) являются:
ограничения на сохранность комбинаторной структуры
ограничения на выпуклость внутреннего многогранника
ограничения на нахождение внутреннего многогранника внутри внешнего

Помимо обязательных ограничений, в зависимости от конкретной задачи, могут быть до-
бавлены дополнительные ограничения, связанные с определенными размерами многогранника,
которые должны сохраниться при колебании вершин или удовлетворять некоторым требовани-
ям в результате решения задачи. В зависимости от степени доверия начальному решению вво-
дятся ограничения xL и xU на переменные, отвечающие за координаты вершин внутреннего
многогранника. Конечные координаты не должны отходить от начальных дальше, чем на вели-
чину dx. Чем меньше эта величина, тем быстрее будет решаться задача, что очень важно в при-
кладных целях.
Для вычислений сформулированной НП-задачи был использован солвер IPOPT(Internal
Point OPTimization) [Kawajir, 2010]. Этот солвер предназначен для поиска локального оптимума
в задаче нелинейного программирования методом внутренней точки. Для упрощения работы с
солвером может быть использован язык программирования AMPL.

297
Метод был реализован и протестирован на задачах разного размера. Задачи варьировались
от простых учебных примеров с простыми, подобными или просто легко вписываемыми мно-
гогранниками с количество вершин меньше пятидесяти до реальных прикладных задач с коли-
чеством вершин от ста до пятисот и ограничениями на симметрию разной жесткости. На реаль-
ных примерах данный метод улучшает любой результат других алгоритмов в исследуемой при-
кладной области на 2-5% объема.
Основные тестируемые примеры содержали вписываемый многогранник с количеством
вершин и граней порядка 150 и внешний многогранник с количеством вершин и граней порядка
500, общее количество ограничений порядка 15000. Время построения задачи на этих приме-
рах составляет около одной секунды. Время вычисления на солвере без ограничений на сим-
метрию ~5 секунд. Время вычислений на солвере с ограничениями на симметрию 20-40 секунд
в зависимости от жесткости ограничений.
В этой статье описаны только общие принципы работы этого метода, более подробно с ме-
тодом можно ознакомиться в более ранних статьях автора [Кокорев, 2013], [Кокорев, 2016]. В
них рассмотрено как эффективнее задавать разные ограничения в виде уравнений.

4. Проблемы нахождения начальной точки
В исследуемой отрасли самым распространенным алгоритмом для поиска максимального
вписанного многогранника является перебор его возможных положений с отсечением случаев с
заведомо маленьким объемом. Принцип работы алгоритма – есть жестко зафиксированная
форма вписываемого тела, которая может подвергаться только повороту, трансляции и гомоте-
тии. Внутри внешнего многогранника перебираются по сетке с заданным шагом возможные
центры масс вписанного тела и его ориентация в пространстве. Для каждого центра масс и ори-
ентации, тело увеличивается до пересечения с внешним многогранником. Случай, когда полу-
чается наибольший коэффициент увеличения является искомым максимальным решением. В
такой упрощенной формулировке алгоритм работает слишком долго при маленьком шаге сетки
и дает слабые результаты на большом шаге. Недостатки данного алгоритм можно исправить
следующими способами.
Во-первых, необходимо максимально ускорить процедуру нахождения коэффициента уве-
личения. Для этого минимизируют вычислительную сложность компонент процедуры. Повы-
шают эффективность работы с памятью. Используют различные способы более быстрого на-
хождения пересечения двух многогранников. Например, с помощью суммы Минковского, или
с помощью представления границы в виду вокселей (многомерный пиксел).
Во-вторых, возможно улучшить обход по сетке центров масс и ориентаций. На основании
ранее полученных результатов исключаются некоторые направления поиска. Оптимизируется
последовательность обхода сетки. Кроме того, сетка может быть не стабильная, а меняться в
зависимости от предыдущих результатов, в частности может уменьшаться шаг сетки, когда
найдена зона локального максимума.
Чаще всего есть не одна форма вписываемого тела, а некоторый конечный набор форм.
Это обусловлено тем, что вырезаемые объекты могут быть разной формы и необходимо опти-
мально использовать дорогостоящие материалы. Более слабые алгоритмы для каждой из форм
запускаются отдельно. В более современных и развитых алгоритмах перебор форм участвует на
ровне с перебором центра масс и ориентации, как еще одна размерность сетки перебора.
Наилучший алгоритм такого типа работает в среднем 10 секунд. Это время можно увели-
чить вдвое, если добиться значительно более хороших результатов по объему или более хоро-
шего взаимодействия с методом колебания вершин
Описанные алгоритмы для нахождения начального приблизительного расположения объ-
екта являются не надежными по двум основным причинам:
1) Они, как и любая оптимизация, находят локальный максимум. Кроме того, так как они
работают с частными геометрическими объектами, а не с системами уравнений, то не

298
существует развитого математического аппарата для решения подобных задач. Поэтому
эти алгоритмы работают на основе частных разработок, в которых из нескольких суще-
ствующих локальных максимумов может находиться более плохой с точки зрения гло-
бальности, чем в аналогичной системе линейных уравнений, решенной стандартными
математическими методами.
2) Эти алгоритмы работают с набором жестко зафиксированных форм, которые может под-
вергаться только повороту, трансляции и гомотетии. В то время как метод колебания
вершин может менять форму, сохраняя только комбинаторную структуру и определен-
ные требования на форму. И получается, что даже, если отбросить проблемы локально-
сти, бывают ситуации, когда лучшее решение с зафиксированной формой и лучшее ре-
шение метода колебания вершин находятся в совершенно разных местах и заданного от-
клонения dx не достаточно, чтобы метод колебания вершил нашел свое лучшее решение.
Из-за этого иногда приходится запускать метод колебания вершин на различных началь-
ных точках, чтобы достичь более хорошего результата. Поэтому для повышения эффек-
тивности алгоритма необходимо найти альтернативный подход без использования на-
чальной точки.

5. Альтернативный подход
В связи с описанными проблемами начаты исследования по разработке алгоритма, рабо-
тающего на базе НП-задачи, не нуждающегося в начальной точке. Первым этапом исследова-
ния стало написание алгоритма, который находит оптимальное расположение для одной жестко
зафиксированной формы
Есть начальные координаты вершин вписываемого многогранника vi. Они только задают
форму, сам многогранник может быть любого размера и иметь любое расположение по отно-
шению к внешнему многограннику. Конечные координаты v1i записываются в виде ограниче-
ний g(x) следующим образом:

Где zoom – это произвольный коэффициент увеличения, – это произвольный вектор
трансляции, R – произвольная матрица поворота, заданная через кватернионы.

Кроме этих уравнений необходимо задать, что сумма квадратов кватернионов равна еди-
ницы.
Таким образом, мы задаем, что данная форма может подвергаться повороту, увеличению и
трансляции и занимать любое расположение в пространстве. Также необходимо задать ограни-
чения на нахождение внутреннего многогранника внутри внешнего. Целевой функцией являет-
ся объем, выраженный через переменные v1i, аналогично методу колебания вершин.
Этот алгоритм дает объем в среднем на 0.4% больше, чем исследуемые алгоритмы, рабо-
тающие с одной фиксированной формой. То есть методы численной оптимизации являются бо-
лее надежными для получения начальной точки для метода колебания вершин. Но алгоритм
работает в среднем 41 секунду, что является слишком большим временем для прикладных це-
лей.
В дальнейшем планируется протестировать другие способы задания преобразования про-
странства, например, использовать матрицу поворота, выраженную через углы Эйлера или че-
рез базисные вектора. Также планируется настроить солвер Ipopt специально под конкретную

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

6. Заключение
В статье рассмотрена цепочка алгоритмов вписывания одного многогранника в другой, ко-
торая используется в реальных прикладных задачах. Кратко описаны основные принципы, по
которым работают эти алгоритмы. И приведены возникающие проблемы, которые требуют
объединения алгоритмов в единый более сложный алгоритм. Рассмотрены первые шаги иссле-
дований в этом направлении, приведены их результаты и дальнейшие планы работы.

Литература
Емеличев В.А., Ковалев М.М, Кравцов М.К., Многогранники, графы, оптимизация, - Москва
"Наука", 1981
V.A. Emelichev, M.M.Kovalev, M.K. Kravtsov, Mnogogranniki, grafy, optimizatsiya, - Moskva "Nauka", 1981 (in Rus-
sian)
Fourer R., Gay D., and Kernighan B., AMPL: A Modeling Language For Mathematical
Programming, - Duxbury Press/Brooks/Cole Publishing Company, 2003
Hales T., The status of the Kepler conjecture, Mathematical Intelligencer 16(1994), С. 47-58.
Kawajir Y., Laird C., Wächter A., Introduction to Ipopt: A tutorial for downloading, installing, and
using Ipopt, 2010, URL: http://www.coin-or.org/Ipopt/documentation/
Кокорев Д.С. , Алгоритм поиска выпуклого многогранника максимального объема, вписанного
в другой многогранник, - журнал «Информационные технологии и вычислительные сис-
темы», - номер 2013/03, С. 27-31.
D.S. Kokorev, Algoritm poiska vypuklogo mnogogrannika maksimal'nogo ob"ema, vpisannogo v drugoy
mnogogrannik, - zhurnal «Informatsionnye tekhnologii i vychislitel'nye sistemy», - nomer 2013/03, S. 27-31. (in Rus-
sian)
Кокорев Д.С., Оптимизационный алгоритм поиска вписанного многогранника максимального
объема, - журнал «Программные продукты и системы», - номер 2016/01, Стр. 90-95.
D.S. Kokorev, An Optimization algorithm to find inscribed polyhedron of maximum volume,- magazine Programmnye
produkty i sistemy №1, 2016, pp 90-95 (in Russian)
Мусин О.Р., Проблема двадцати пяти сфер, Успехи математических наук, 2003, Т.58, №4(352),
стр. 153-154
O.R.Musin, Problema dvadtsati pyati sfer, Uspekhi matematicheskikh nauk, 2003, T.58, №4(352), str. 153-154 (in
Russian)
Tarasov A., Musin O., The strong thirteen spheres problem,- Topology, Geometry, and
Dynamics: Rokhlin Memorial January 11-16, 2010. Saint Petersburg, Russia
Валиахметова Ю.И., Филиппова А . С., Теория оптимального использования ресурсов Л. В.
Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения,
Вестник УГАТУ, Том 18, №1(62).
Yu. I. Valiakhmetova, A. S. Filippova, Teoriya optimal'nogo ispol'zovaniya resursov L. V. Kantorovicha v zadachakh
raskroya-upakovki: obzor i istoriya razvitiya metodov resheniya, Vestnik UGATU, Tom 18, №1(62). (in Russian)

300
Applied problems of polyhedron inscribing task solving
D. S. Kokorev
Federal state-financed Institution Institute for Information Transmission Problems of the Russian Academy of
Sciences(Kharkevich Institute)
Bolshoy Karetny per. 19, build.1, Moscow 127051 Russia
E-mail: korvin-d@yandex.ru

The article discusses problem of finding the polyhedrons given shape inside another polyhedrons. This
problem is a particular case of the 18th Hilbert problem third part. It has a practical application in the computer
simulation of three-dimensional objects, the cutting-stock problems solution, the autonomous robots moving, and
the jewelry industry. It is proposed method for finding the inscribed polyhedrons, based on the reduction of the
problem to a nonlinear programming problem, in the article. It describes the basic functional limitations that are
used for this task, and program resources to work effectively with the nonlinear programming problems.
Described method requires a good initial solution. Solutions of other less accurate algorithms can be taken as a
starting point. One of the most common algorithm with such goal is a homothetic bloating of object under differ-
ent angles and with a center of mass in different points until an intersection with an external polyhedron. A sepa-
rate chapter is devoted to the description and disadvantages of these methods. The main disadvantage is a locali-
ty of decision. As well as the need for iterating of rigidly defined forms of a polyhedron. This methods analogue,
based on the nonlinear programming problem, is offered. The proposed method is based on representing any
possible movement as composition of a rotation, a translation, and a dilation. Rotation matrix represented by
quaternions in the described experiment. Invented algorithm works better than the existing analogs, but it is still
insufficient fast for practical purposes. Future development plans are written in the conclusion.

Keywords: Computer modelling, convex polyhedrons, combinatorial structure, inscribed polyhe-
dron, nonlinear programming problems, solver

The work was supported by Russian Science Foundation (№16-11-10352).

301