0

У меня есть набор точек на одной плоскости, которые составляют полигон. Как мне "протриангулировать" этот полигон, если плоскость, на которой он лежит, может находиться под разными углами и в разных местах?

Вот примеры этих плоскостей (вместо круга может быть любой полигон(без "дырок"))

введите сюда описание изображения

8
  • Что вы понимаете под триангуляцией? Обычно это нахождение координат до точки через 3 угла из 3х точек с известными координатами
    – eri
    18 дек 2019 в 22:49
  • 1
    @eri: "Триангуляцией" в вычислительной геометрии обычно называют построение набора треугольников (декомпозицию внутренности многоугольника на треугольники, построение набора треугольников по набору вершин и т.п.) 18 дек 2019 в 22:54
  • 1
    Вопрос не ясен. Какая разница, где и как находится плоскость. Задача все равно натуральным образом двумерна. В чем сложность? Также не ясно, каковы критерии оптимальности триангуляции. 18 дек 2019 в 22:55
  • Так через одну их соединить спиралью и будут треугольнички
    – eri
    18 дек 2019 в 23:07
  • Если полигон выпуклый. Если есть впуклости, то разбить его на несколько выпуклых
    – eri
    18 дек 2019 в 23:11

2 ответа 2

2

Комбинаторика триангуляции нисколько не изменится, если вы просто проигнорируете одну из 3D координат, следя при этом за тем, чтобы задача не выродилась. А именно, если, например, ваша плоскость вдруг параллельна оси Z, то нельзя игнорировать координату z. Так как одновременно всем трем координатным осям ваша плоскость параллельна быть не может, координата, которую можно игнорировать, всегда существует. То есть задача элементарным образом сводится к 2D задаче триангуляции путем тривиальной ортогональной проекции на одну из координатных плоскостей.

Другое дело, что ваша задача триангуляции может содержать критерии оптимальности триангуляции, которые могут искажаться при выполнении вышеупомянутой проекции. Но вы ни слова об этом не сказали. И, если вас интересует лишь банальный ear-clipping, как вы написали в заголовке, то ни о чем подобном задумываться не нужно - задача сводится к 2D задаче тривиальным образом.

Неясно, правда, почему вы ведете речь об ear-clipping - алгоритме, который в общем случае очень неэффективен.

3
  • Я, скорее всего, задал вопрос не правильно. У меня не получилось проверить вершину на выпуклость: пытался делать по предикату «левого поворота», но там есть формула векторного произведения в 2D (m.habr.com/ru/post/138168). Его код подойдёт для меня, если у меня вершины треугольника, могут быть такие: A(1,2,3), B(4,6,8) C( 10,5,20). 19 дек 2019 в 7:51
  • И еще, вы сказали про неэффективность метода, какие можете посоветовать вместо него ? 19 дек 2019 в 7:53
  • @ANGRYSHARKknyaz2000 Я уже писал выше. Существует классический алгоритм триангуляции, основанный на разбиении исходного полигона на монотонные полигоны и затем тривиальной триангуляции монотонных частей. Любой источник по триангуляции вам даст ссылку на этот алгоритм. Другое дело, что реализация разбиения на монотонные делается алгоритмом сканирующей прямой, то есть все это придется реализовывать. 19 дек 2019 в 8:15
1

Предположим, что мы можем выполнить триангуляцию полигона на плоскости XY. Тогда задача сводится к переходу от плоского полигона в 3D к полигону в 2D.

Возьмите любые две точки на Вашей плоскости. Это могут любые две вершины полигона, главное, чтобы они были разные. Это будет вектор/направление OX. Найдите вектор в этой же плоскости, перпендикулярный вектору OX. Это будет вектор OY. Нормализуйте их. Найдите координаты всех точек в этой новой системе координат. Это будут скалярные произведения вектора, проведенного из той же точки, что и OX, с OX и с OY, соответственно. Все вектора, естественно, в трехмерном пространстве. Теперь у Вас есть полигон в плоскости XY.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.