Разработка алгоритма для создания фигур

Question

У меня уже есть теория, лежащая в основе алгоритма, но, поскольку у меня нет формального образования, у меня возникают проблемы с переводом его в код. Более подробная информация о теории ниже. Любая помощь приветствуется.

make_shape

Вам даны x вершин и их координаты относительно угла (пусть это будет относительно нижнего левого угла для простоты) в качестве аргумента функции.

using vertices_t = std::vector< std::pair< double,
                                           double > >;

make_shape( vertices_t const & vertices );
// doesnt need to be a vector of a pair of doubles.
// use anything else, like a valarray of ints if you so choose

В свою очередь, вы должны построить объект, который описывает фигуру в треугольниках (примитивах)

using triangles_t = std::vector< std::tuple< std::size_t,
                                             std::size_t,
                                             std::size_t > >;

triangles_t make_shape( vertices_t vertices );
// once again, it does not need to be a vector of a 3 tuple of size_t

Теория: любая форма может состоять из треугольников. Требуемое количество треугольников равно числу вершин минус два.

auto && triangles = vertices.size( ) - 2;

Алгоритм прост: вы берете вершину и две смежные вершины и соединяете их. Затем поочередно увеличивайте вершины и сохраняйте последнюю увеличенную вершину в качестве трех следующих вершин. Это приведет к серии треугольников, которые составляют любую форму. Проблема возникает с вогнутыми формами, где выбор вершины имеет значение.

Ниже приведены некоторые изображения того, как алгоритм выглядит в действии

Answer 1

Часть, которую вы пропустили, - это «алгоритм обрезки ушей», который выбирает «ухо» многоугольника, который является вершиной, которую можно обрезать описанным способом. Гарантируется, что любой многоугольник (как минимум с 4 вершинами) имеет как минимум 2 ушка; так называемая «теорема о двух ушах» .

Если вы ищете «алгоритм обрезания ушей», вы получите несколько ссылок о том, как реализовать его более или менее эффективно.

Например, это некоторый очень четкий код, который идентифицирует ухо (хотя в go, поэтому вам придется его перевести): https://github.com/fogleman/triangulate/blob/master/ring.go