Ответ 1
Поскольку ваши сетки не выпуклые, результирующее поперечное сечение может быть отключено, поэтому на самом деле они состоят из нескольких полигонов. Это означает, что каждый треугольник должен быть проверен, поэтому вам понадобятся хотя бы O (n) операции для n треугольников.
Вот один из способов сделать это:
T <- the set of all triangles
P <- {}
while T is not empty:
t <- some element from T
remove t from T
if t intersects the plane:
l <- the line segment that is the intersection between t and the plane
p <- [l]
s <- l.start
while l.end is not s:
t <- the triangle neighbouring t on the edge that generated l.end
remove t from T
l <- the line segment that is the intersection between t and the plane
append l to p
add p to P
Это будет выполняться в O (n) времени для n треугольников, при условии, что ваши треугольники имеют указатели на их три соседства и что T поддерживает удаление посто нного времени (например, хэш-набор).
Как и во всех геометрических алгоритмах, дьявол находится в деталях. Подумайте о случаях, когда вершина треугольника находится точно в плоскости, например.