Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.146.34.191] |
|
Сообщ.
#1
,
|
|
|
Имеются два выпуклых многогранника. Нужно найти такое аффинное преобразование, применяя которое к первому многограннику, он будет вписан во второй и иметь максимальный объём.
|
Сообщ.
#2
,
|
|
|
Разобьём многогранник на пирамидки. Объём каждой пирамидки поменяется в одно и то же число раз при линейном преобразовании, которое легко найти.
Вписанность как система линейных неравенств - сравнением точек нашего многогранника с плоскостями граней другого многогранника. Линейное программирование? |
Сообщ.
#3
,
|
|
|
Цитата scrambrella @ Линейное программирование? Нелинейное. Объём - это функция третьего порядка. Можно рассмотреть задачу немного проще. Передвинем многогранники так, чтобы их центры масс находились в начале координат, и теперь будем искать линейное преобразование, применяя которое к первому многограннику, он будет вписан во второй и иметь максимальный объём. Здесь мы, убирая смещение, снижаем размерность задачи с 12 ( аффинное преобразование ) до 9 ( линейное преобразование ). |
Сообщ.
#4
,
|
|
|
А если привлечь физику? Задать внутреннему многограннику характеристику давления и в точках соприкосновения вершин считать вектора сил, считая скелет многогранника абсолютно упругим. Есть нюанс: метод считает преобразование непрерывным, тогда как задача этого не требует, главное, чтоб результат показал пересечение тел, совпадающее с внутренним телом. Т.е. этот метод не даст вершинам внутреннего многогранника пересечь грани внешнего в процессе расчёта действия сил, поэтому если существует лучшее решение, проходящее через промежуточное худшее, оно не будет найдено.
|
Сообщ.
#5
,
|
|
|
Цитата Qraizer @ А если привлечь физику? Задать внутреннему многограннику характеристику давления и в точках соприкосновения вершин считать вектора сил, считая скелет многогранника абсолютно упругим. Уткнётся в стенку в плохой позиции и дальше расширяться не будет. |
Сообщ.
#6
,
|
|
|
Можно, конечно, решать градиентными методами, но это долго и будут локальные максимумы.
|
Сообщ.
#7
,
|
|
|
scrambrella, именно это я и написал. Если хочется что-то сказать, давай по существу.
prografix, никто не запрещает поставить множество экспериментов. Вообще, в общем случае тут нет решения. Иначе давно б не существовало бы нерешённых задач типа этой Т.е. лучшее, что можно, пробовать по-разному и оценивать результат. ИМХО физический движок наиболее просто это реализует. Добавлено P.S. Самому страшно: требуется максимизировать тройной интеграл в поле кватернионов на компактном многообразии, заданном ещё одним тройным интегралом. Буду признателен, если кто предложит формулировку задачи попроще. |
Сообщ.
#8
,
|
|
|
Qraizer
Формулировка такая: множество допустимых значений образует выпуклый многогранник в 9-мерном пространстве ( для второй задачи ). Нужно найти оптимальную точку. Беда в том, что она может лежать не на вершине и не на ребре многогранника, а где-то на поверхности. |