如何将多边形转换为非重叠三角形上的集合？ [英] How to convert a polygon to a set on non-overlapping triangles?

问题描述

我有一个2D点的坐标集，这些点构成一个闭合的多边形。我需要生成一组2D三角形来完全分布多边形。

I have a coordinate set of 2D points that form a closed polygon. I need to generate a set of 2D triangles that distribute the polygon completely.

除了三角形应该完全填充多边形的区域外，没有其他限制。

There are no constrains as such except that the triangles should fill the area of polygon completely. It would be even more helpful if it is a standard algorithm I could implement.

推荐答案

如上所述，Delaunay三角剖分是一个相当不错的选择。完成此任务的复杂算法。如果您接受O（n ^ 2）的运行时间，则可以尝试使用Ear Clipping算法，该算法更易于理解和编码。基本思想如下。每个具有> = 4个顶点且没有孔的多边形（即其边界是一条没有自相交和自切线的多段线），至少具有一个耳。耳朵是三个连续的顶点，因此建立在它们上面的三角形位于多边形内部，并且内部不包含多边形的其他点。如果您割耳（在答案中添加一个三角形，然后替换掉这三个点的中点），则将任务简化为顶点较少的多边形，依此类推。可以在O（n ^ 2）中发现耳朵（根据定义），从而得到O（n ^ 3）三角剖分算法。有O（n）寻耳算法，尽管它不是很复杂，但是用几个短语来描述它相当长。

As mentioned above, Delaunay triangulation is a rather complicated algorithm for this task. If you accept O(n^2) running time, you may try Ear Clipping algorithm which is much more easier to understand and to code. The basic idea is the following. Every polygon with >= 4 vertexes and no holes (i.e. its border is a single polyline without self-intersections and self-tangencies) has at least one "ear". An ear is a three consecutive vertexes such that the triangle built on them lies inside the polygon and contains no other points of the polygon inside. If you "cut an ear" (add a triangle to the answer and replace remove the middle point of these three points), you reduce the task to a polygon with less vertexes, and so on. Ears may be trivially (by definition) found in O(n^2) resulting in a O(n^3) triangulation algorithm. There is O(n) ear finding algorithm, and, though it is not very complicated, it is rather long to be described in a couple of phrases.

此外，如果如果您需要更快的算法，则应该查看有关单调多边形三角剖分以及将多边形拆分为单调多边形的内容。甚至存在线性时间三角剖分算法，但是它与Delaunay三角剖分一样复杂。

Furthermore, if you need faster algorithms, you should look something about monotone polygons triangulation and splitting a polygon into monotone ones. There even exists a linear-time triangulation algorithm, but its just as complicated as Delaunay triangulation is.

您可以考虑维基百科文章，并在那里看到现有方法的简短概述。

You may consider Wikipedia article and see an small overview of existing methods there.

这篇关于如何将多边形转换为非重叠三角形上的集合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！