java - 对复杂的不规则凹凸多边形进行三角测量的最佳方法

Question

我需要对一个有很多顶点靠近的多边形进行三角测量。多边形将代表国家的形状。我正在使用 libgdx 并想利用它的 PolygonRegion类:

PolygonRegion(TextureRegion region, float[] vertices, short[] triangles)

Creates a PolygonRegion by triangulating the polygon coordinates in vertices and calculates uvs based on that.

在libgdx中有EarClippingTriangulator用于三角剖分多边形。它的文档说:

If the input polygon is not simple (self-intersects), there will be output but it is of unspecified quality (garbage in, garbage out).

libgdx 中的其他三角器对此没有太多说明，我在 google 上找不到任何帮助。

我想知道对具有彼此相邻或非常接近的顶点的复杂多边形进行三角剖分是否会出现任何问题。我的多边形可能包含几百个顶点(我认为可能更多)。

[编辑]我不确定是否有一个点在对多边形进行三角测量，因为它将创建多少个三角形。

Answer 1

您不必自己编程。大多数高级编程语言都有一个 2D 图形库，并提供多边形可编程对象。它将定义一个闭合(简单)多边形作为按 CCW 顺序访问的顶点 [x, y] 的列表。该多边形对象具有“填充”功能，该功能专为快速填充像您这样的复杂形状而设计。三角测量将是一种相对较慢的方法......更快的算法将形状转换为一组水平扫描线(利用最低级别的图形系统必须填充像素的事实)。就岛屿而言，每个岛屿都必须有自己的多边形对象。如果一个区域(瑞士奶酪)中有切口，每个切口都会有自己的多边形。每个多边形都需要闭合。