Какой алгоритм использовать для получения координат сечения плоскостью многогранника?

Question

[becks]

Коллеги, добрый день!
В исходном виде задачу можно описать так, есть множество относительно простых многогранииков (порядка 300-500 штук). Есть секущая плоскоть. Необходимо получить сечение всех этих многогранников. Задачу можно успростить до поиска сечения одного (каждого) многранника - итоговым сечением будет сумма всех сечений.
Каждый многогранник задаётся двумя противолежащими гранями и хранится списком пар точек - точка на первой грани и соответствующая её точка на противолежащей. Другими словами, для каждой точки на грани всегда найдется пара на противолежащей грани. На рисунке ниже такие пары точек A1 - A2, B1 - B2 и т. д. Но существуют и многогранники, грани которых не являются выпуклыми фигурмами (как на рисунке).


И вот для таких многогранников текущий алгоритм строит неправильное сечение. Суть текущего алгоритма - проходим по каждой грани, находим точки перечения ребер грани секущей плоскостью (если грань выпуклый многоугольник получаем максимум 2 точки пересенения), соединяем эти точки, соединяем отрезки сечений смежных граней, получаем итоговое сечение. Если же грань не является выпуклым многоугольником, то не могу понять, как получить сечение этой грани, какие точки соединять ?

Подскажите, куда копать или как модифицировать существующий алгоритм, чтобы он работал с "проблемными" многогранниками или другими словами, как сечь грани, которые не являются выпуклыми многоугольниками?

Спасибо.

Comments

[Karpion]

Я не понял, что д.б. в результате. Навскидку - сечение плоскостью многогранника всегда будет многоугольником. Каждая вершина многоугольника = пересечение секущей плоскости с ребром исходного многогранника; найти это пересечение - элементарно.

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

В принципе, две точки являются соседними - если они принадлежат одной грани. Но у невыпуклой грани таких точек много.

Собственно, я бы начал искать ответ, исходя из формы, в которой задан исходный многогранник.

Answer 1

[Clark Kent]

Копай сюда:

• Булевы операции над многогранниками и пологинами
  
• Бинарные деревья для решения булевых операций
  
• Пересечение прямой и пологона
  

Answer 2

[Денис]

Ммм, далек от царицы всех наук, три идеи, последующая лучше предыдущей.

Проверьте фигуру на выпуклость, если она таковой не является - достройте её до выпуклой. Посчитайте сечение новой фигуры и вычтите из получившегося сечения то, что достроили. Подводный камень - то, что вы достроили может оказаться не выпуклой фигурой.

Вариант два, проверьте фигур на выпуклость, если она таковой не является, разбейте фигуру на отдельные выпуклые фигуры.

Вариант три, забить на проверки и разбить каждое сечение на гарантированно выпуклый многоугольник (треугольник). Ну или саму фигуру на треугольные пирамиды. И уже считать сумму сечений этих треугольников\треугольных пирамид.

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