Выпуклая оболочка в пространстве: видимые грани

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

На плоскости новая точка удаляет цепочку рёбер выпуклого многоугольника. Что она удалит у многогранника? Попробуй представить точку над одной гранью тетраэдра. Видна одна грань, и вместо неё появляются три треугольника. Если видны две соседние грани, строить по три треугольника для каждой уже нельзя: общее ребро лежит внутри удаляемой области.

На что это похоже

Представь шатёр, к которому добавляют внешнюю опору. Часть старого покрытия обращена к новой опоре и должна быть снята. Новое покрытие натягивают между опорой и краем оставшегося шатра. Край проходит только между снятой и сохранённой частями. Швы внутри снятого покрытия не должны превращаться в границы нового шатра.

Механизм: от определения к алгоритму

Треугольную грань ориентируют наружу. Видимость грани из точки определяется знаком ориентированного объёма: скалярным произведением нормали грани на вектор к точке. Положительный знак означает наружную сторону, ноль - точку в плоскости грани. Определитель вычисляется через разности координат, поэтому с целочисленным входом знак можно получать точно целочисленной арифметикой.

Сначала выбери четыре некомпланарные точки и построй тетраэдр. Если все точки лежат в одной плоскости, задача вырождается в плоскую оболочку; искусственный тетраэдр её не исправляет. Для очередной внешней точки найди все видимые грани. Горизонт состоит из рёбер, у которых одна соседняя грань видима, другая нет. Удали видимые грани и закрой отверстие треугольниками «ребро горизонта плюс новая точка». Внутренняя точка не меняет оболочку.

Граф конфликтов - двудольный граф между текущими гранями и оставшимися точками: ребро говорит, что точка видит грань. Он позволяет не проверять заново все пары. Конфликты новых граней ищут среди кандидатов, связанных с прилегающими старыми гранями. Начальный граф строится за линейное время относительно числа точек, поскольку граней тетраэдра четыре. Затем случайная перестановка входа обеспечивает ожидаемую оценку O(n log n).

Триангулированная граница выпуклого трёхмерного многогранника с v вершинами имеет 2v-4 грани при v≥4. Это следует из формулы Эйлера и того, что каждое ребро разделяют два треугольника. Линейный размер ответа объясняет достижимость оценки, но не доказывает её для произвольной реализации вставок.

Правило

Обновляй оболочку по горизонту видимой области, а для ожидаемых O(n log n) сохраняй конфликты и используй случайный порядок; линейное число граней не заменяет анализ алгоритма.

Разбор: проследим вычисление

Посмотрим на тетраэдр с вершинами на координатных осях. Его противоположная началу координат грань лежит в плоскости x+y+z=3. Точка (2,2,2) видит эту грань, но не три координатные. Программа определяет знаки точно и находит горизонт. Это один шаг обновления, а не реализация графа конфликтов: полного построения за O(n log n) здесь нет.

def sub(a, b):
    return tuple(x - y for x, y in zip(a, b))

def cross(a, b):
    return (a[1]*b[2] - a[2]*b[1],
            a[2]*b[0] - a[0]*b[2],
            a[0]*b[1] - a[1]*b[0])

def dot(a, b):
    return sum(x*y for x, y in zip(a, b))

points = [(0, 0, 0), (3, 0, 0), (0, 3, 0), (0, 0, 3)]
faces = [(0, 2, 1), (0, 1, 3), (0, 3, 2), (1, 2, 3)]
p = (2, 2, 2)
visible = []
for i, (a, b, c) in enumerate(faces):
    normal = cross(sub(points[b], points[a]),
                   sub(points[c], points[a]))
    if dot(normal, sub(p, points[a])) > 0:
        visible.append(i)
edges = {}
for i, face in enumerate(faces):
    for k in range(3):
        edge = tuple(sorted((face[k], face[(k + 1) % 3])))
        edges.setdefault(edge, []).append(i)
horizon = [e for e, fs in edges.items()
           if sum(i in visible for i in fs) == 1]
print("видимые грани", visible)
print("горизонт", sorted(horizon))
print("новых граней", len(horizon))
print("итого граней", len(faces) - len(visible) + len(horizon))

видимые грани [3]
горизонт [(1, 2), (1, 3), (2, 3)]
новых граней 3
итого граней 6

Разбор: где проходит граница

Если вставить (1,1,1), точка попадёт в плоскость одной грани: знак равен нулю. В данном тетраэдре она уже принадлежит оболочке и не создаёт новых наружных граней. Если считать ноль положительным, алгоритм построит вырожденные треугольники в той же плоскости. При нескольких копланарных точках нужно выбрать политику представления: например, хранить триангуляцию общей плоской грани, а не считать каждую тройку отдельной гранью.

Что ломается без этого

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

Зачем это в работе

Оболочку облака точек используют как грубую границу детали, для отбрасывания заведомо далёких столкновений и проверки пространственного охвата. Для инженерной геометрии знак определителя важнее красивой картинки: почти копланарные точки выявляют ошибки численной устойчивости. Проверяй отдельно топологию замкнутой поверхности и расположение всех исходных точек на внутренней стороне каждой итоговой грани.

Теперь сам

У выпуклого многогранника шесть вершин, все грани треугольные. Сколько граней?