#algorithm #geometry #computational-geometry
#алгоритм #геометрия #вычислительная геометрия
Вопрос:
В геометрии многогранник представляет собой трехмерную фигуру с плоскими многоугольными гранями, прямыми ребрами и острыми углами или вершинами.
У меня есть два выпуклых многогранника, которые пересекаются друг с другом. Часть пересечения этих двух многогранников — это мое пространство желаний.
Я хочу знать, есть ли какой-либо алгоритм, который находит это пространство соответствующим образом? Если доступно, был ли для него написан код (с открытым исходным кодом)?
Комментарии:
1. Для этого существует несколько алгоритмов. Вы найдете множество статей, описывающих решения этой проблемы. Однако, если вы хотите найти реализацию, вам придется указать используемый язык. И даже тогда вам, вероятно, не повезет, и вам придется проделать значительную работу самостоятельно.
Ответ №1:
Простым решением для этого было бы следующее:
выпуклый многогранник можно описать как пересечение полуплоскостей, определяемых отдельными гранями многогранника (вероятно, об этом легче думать в 2D, но в 3D это работает точно так же).
С этим определением найти пересечение так же просто, как пересечение полуплоскостей обоих многогранников. Поскольку это довольно примитивная операция, ее должна поддерживать практически любая библиотека вычислительной геометрии.
Комментарии:
1. Моя главная цель в этом вопросе — найти способ «обрезки многогранников». Приводит ли ваше решение к отсечению многогранников? Вы нашли какой-нибудь исходный код для обрезки многогранников?
2. @NULL он вычисляет пересечение двух многогранников. То, что вы делаете с этим результатом, — это совсем другая история. Вы должны были точно указать, что вы хотите в вопросе. Однако для этого уже немного поздно, поэтому вам придется задать другой вопрос — пожалуйста, не просто редактируйте этот вопрос. Что касается исходного кода: запрос внешних ресурсов здесь является оффтопическим, и те же проблемы, о которых я уже упоминал в своем комментарии к вашему вопросу, еще больше применимы для обрезки многогранников.
3. если ваши многогранники выпуклые, они равны их выпуклой оболочке, поэтому вы можете использовать алгоритм выпуклой оболочки (например, их существует множество), чтобы найти нужное вам пересечение.