一种形状生成算法的设计

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

理论上:任何形状都可以由三角形组成。所需的三角形数等于顶点数减去2。

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

算法很简单:取一个顶点和两个相邻的顶点并将它们连接起来。然后，交替地增加顶点，并将最后一个增量顶点存储为三个下一个顶点。这将导致一系列的三角形组成任何形状。这个问题产生于凹形，在那里选择顶点很重要。

下面是有关该算法的工作方式的一些图像

​

​

Answer 1

您缺少的部分是“耳裁剪算法”，它选择多边形的"ear“，这是一个顶点，可以以您描述的方式切断。它保证任何多边形(至少有4个顶点)至少有两个耳朵；所谓的“双耳定理”。

如果您搜索"ear裁剪算法“，您将得到许多关于如何更有效地实现它的链接。

例如，这是一些非常清晰的识别ear的代码(虽然在go中，所以您必须翻译它)：https://github.com/fogleman/triangulate/blob/master/ring.go