Понимание и реализация триангуляции

Вы когда-нибудь задумывались, как соединить несколько трехмерных точек в поверхность? Ответ триангуляция. Мы собираемся посмотреть, что это такое и как его использовать в python.

Прежде чем мы начнем

В этом посте будет использоваться следующий контекст.

Код из поста есть и в этом репозитории.

Что такое триангуляция?

Скажем, у нас есть набор точек в трехмерном пространстве, которые описывают поверхность. Но по причинам, связанным с оптимизацией или отсутствием данных, мы не можем расширить эти точки, чтобы сформировать непрерывную поверхность. Введите триангуляцию. Что, если мы опишем набор треугольников с нашими точками в качестве вершин и вместо этого нарисуем их? Это звучит идеально!

Но как мы определяем эти треугольники? К счастью, существует алгоритм под названием триангуляция Делоне, который может определить их для нас. Хотя он делает это только для наборов 2d точек, так как в 3d нет единого способа триангуляции заданного набора точек (разные триангуляции могут создавать разные поверхности).

Алгоритм создаст каждый треугольник таким образом, чтобы его вершины находились как можно ближе друг к другу. Причина в том, что мы не можем нарисовать треугольник над тремя удаленными точками, между которыми могут быть другие точки. Все треугольники должны быть склеены бок о бок, чтобы ни один из них не содержал другого.

С помощью этого алгоритма легко триангулировать трехмерные поверхности, которые описываются точками(x, y, f(x,y)), гдеf — некоторая функция. Это означает, что каждой паре (x, y) соответствует ровно одна точка z (высота). Наша триангуляция точек (x, y, f(x,y)) определяется через триангуляцию проекций (x, y), поскольку они полностью описывают близость точек на нашей поверхности.

Небольшая проблема возникает, когда у нас есть более сложная трехмерная поверхность, такая как сфера. Тогда мы не можем спроецировать точки на плоскость, так как это больше не сохраняет информацию о том, какие точки были близки друг к другу. Например, точки (0,0,1) и (0,0,-1) лежат на противоположных сторонах единичной сферы, но обе проецируются в одну и ту же точку. (0,0)на плоскости. В этом случае мы должны сопоставить нашу поверхность с триангулированной плоскости. Это определение параметризации поверхности.

Обратите внимание, что мы делали это раньше, когда сопоставляли (x,y) с (x, y, f(x,y)).

Посмотрите пример того, как мы складываем лист бумаги в тор. Это складывание можно рассматривать как параметризацию. Должно быть ясно, как мы получаем триангуляцию тора из триангуляции точек на бумаге (в процессе складывания мы оставляем треугольники в покое).

Триангуляция лица

Здесь мы триангулируем этот набор 3d точек, описывающих лицо. В нашем случае лицо описывается точками вида (x, y, f(x,y)), поэтому мы можем использовать простой способ триангуляции их проекций.

Мы также добавили cm.inferno карту цветов для визуализации высоты точек. После запуска кода мы получаем что-то вроде этого.

Триангуляция эллипсоида

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

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

Сфера

Чтобы не утомлять вас точными деталями рисования эллипсоидов в самом начале, давайте сначала научимся рисовать (единичную) сферу. Мы увидим, что с этого момента рисовать эллипсоид будет довольно легко.

Нам нужно параметризовать нашу сферу. Наиболее естественная параметризация

(cos(u) sin(v), sin(u) sin(v), cos(v)),

где u изменяется от 0 до 2π, а v изменяется от 0 до >п.

Если вам интересно, это вытекает из того факта, что для любых двух нормированных и ортогональных векторов q и p параметризация cos(t) q + sin (t) p(гдеt изменяется от 0 до 2π) представляет единичный круг, натянутый на q и p. Чтобы нарисовать сферу, мы проводим (половину) окружности через каждую пару векторов (0, 0, 1)и (cos(u), sin(u), 0), где u изменяется от 0 до 2π.

Давайте реализуем это.

Увеличение параметра k определяет больше точек, а значит, треугольники меньшего размера и, следовательно, более гладкую сферу. Запуск кода дает что-то вроде этого:

Вы также можете рисовать части сферы и наблюдать за ее внутренней частью, ограничивая домен, например, [0, 2𝝅] x [0,𝝅/2].

Эллипсоид

Все, что нам нужно сделать, чтобы получить эллипсоид, это выбрать матрицу 3x3 и применить ее к каждой точке на сфере. Матрица определяет оси эллипсоида и растяжение вдоль этих осей. В контексте статистики это тесно связано с матрицей ковариаций.

Мы использовали матрицу из моей домашней работы.

Триангуляция двух других поверхностей

Примечания

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