Как заполнить форму на основе сетки с помощью Трис

Question

У меня есть форма, определяемая массивом 2D точек (по часовой стрелке вокруг формы) и значением высоты. Точки соответствуют сетке с целыми числами, однако в форме может быть отрицательное пространство. Простой пример может быть похож на различные блоки из тетриса.

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

Я уверен, что об этом уже спрашивали, но я не знаю, как сформулировать это, чтобы найти то, что мне нужно.

Answer 1

Вы ищете термин «триангуляция полигонов». Статья в Википедии объясняет несколько алгоритмов.

Answer 2

Как уже упоминалось выше, вы хотите исследовать триангуляцию. Отличный метод для начинающих называется «Клиппирование ушей». Ниже приведена ссылка на замечательный PDF-файл, в котором подробно объясняются шаги, которые необходимо предпринять для его реализации.

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Answer 3

Если вы работаете в C ++, вы можете использовать библиотеку CGAL для этого: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Mesh_2/Chapter_main.html