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