给定不规则多边形的顶点列表，如何创建内部三角形以有效地构建平面 3D 网格? [英] Given an irregular polygon's vertex list, how to create internal triangles to build a flat 3D mesh efficiently?

问题描述

我正在使用 Unity，但解决方案应该是通用的.我将通过鼠标点击获得用户输入，它定义了一个封闭的不规则多边形的顶点列表.这些顶点将定义平面 3D 网格的外边缘.

I'm using Unity, but the solution should be generic. I will get user input from mouse clicks, which define the vertex list of a closed irregular polygon. That vertices will define the outer edges of a flat 3D mesh.

要在 Unity 中按程序生成网格，我必须指定所有顶点以及它们如何连接以形成三角形.

To procedurally generate a mesh in Unity, I have to specify all the vertices and how they are connected to form triangles.

所以，对于凸多边形，这很简单，我只需制作顶点为 1、2、3 和 1、3、4 等的三角形，形成孔雀尾巴.

So, for convex polygons it's trivial, I'd just make triangles with vertices 1,2,3 then 1,3,4 etc. forming something like a Peacock tail.

但是对于凹多边形，它就不是那么简单了.有没有找到内部三角形的有效算法?

But for concave polygons it's not so simple. Is there an efficient algorithm to find the internal triangles?

推荐答案

你可以使用一个受约束的 Delaunay三角测量(这不是简单的实现！).Triangle 和 CGAL，提供高效的 O(n*log(n)) 实现.

You could make use of a constrained Delaunay triangulation (which is not trivial to implement!). Good library implementations are available within Triangle and CGAL, providing efficient O(n*log(n)) implementations.

如果顶点集很小，耳剪算法也是一种可能，虽然它不一定会给你一个 Delaunay 三角剖分(它通常会产生次优三角形)并在 O(n^2) 中运行.不过，自己实现很容易.

If the vertex set is small, the ear-clipping algorithm is also a possibility, although it wont necessarily give you a Delaunay triangulation (it will typically produce sub-optimal triangles) and runs in O(n^2). It is pretty easy to implement yourself though.

由于输入顶点存在于 3d 空间的平面上，您可以通过投影到平面上，计算 2d 中的三角剖分，然后将相同的网格拓扑应用于您的 3d 顶点集来获得 2d 问题.

Since the input vertices exist on a flat plane in 3d space, you could obtain a 2d problem by projecting onto the plane, computing the triangulation in 2d and then applying the same mesh topology to your 3d vertex set.

这篇关于给定不规则多边形的顶点列表，如何创建内部三角形以有效地构建平面 3D 网格?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！