如何连接两个平行的2d多边形以创建无缝的3d网格？

Question

假设我有两个多边形，一个位于另一个之上，如下所示：

我想将它们的顶点连接起来，以围绕其周边的三角形创建一个3d网格。这张图显示了您可以执行此操作的一种方式（橙色线代表三角形边缘）：

这类事情可以由人类直观地完成，但是在将其转换为有效的算法方面确实遇到了麻烦。

多边形存储为List<Vector2>。它们将总是简单的，并且可能是凹形的。

Answer 1

我会这样做：

1. 在每个多边形中找到两个最接近的点

   这将用作起点

2. 从这两个起点重新排列顶点

   具有相同的缠绕规则，例如图像上的CW

3. 找到每个多边形的“中心”点

   例如所有顶点的平均值或边界框的中点之类的值。它不需要很精确，但是在复杂的凹形上，错误选择的中心位置将导致输出网格的错误。

4. 为每个顶点添加角度信息

   角度很容易使用

   a=atan2(vertex-center)
   

毕竟，它看起来应该像这样：

角度角度[deg]

index: 0   1   2   3   4
green: 355 085 135 170 230 
 blue: 020 135 255

现在，您只需将两个最接近的顶点从一个多边形匹配到另一个多边形

不要忘记角度差最大+/-180 deg，如果使用弧度，也可以将常数转换180,360为PI,2.0*PI

da=ang1-ang0;
while (da<-180.0) da+=360.0;
while (da>+180.0) da-=360.0;
if (da<0.0) da=-da;

下一个文本line(i,j)将表示i-th绿色的j-th顶点和蓝色多边形的顶点

现在加入：

1. 加入最近的顶点

   只需处理所有绿色顶点并将它们连接到最接近的蓝色顶点（图像上的黑线）

   line(0,0)
   line(1,1)
   line(2,1)
   line(3,1)
   line(4,2)
   

2. 填补漏洞

   网格三角剖分每个顶点至少需要2个关节，因此连接较少的处理点：

               index: 0 1 2 3 4
   green connections: 1 1 1 1 1
    blue connections: 1 3 1
   

   因此现在处理少于2次的蓝色顶点(0,2)，并将它们连接到最接近的绿色顶点（图像上的黄线），而忽略已使用的连接（在这种情况下，选择下一个）

   line(1,0)
   line(3,2)
   

   所以：

               index: 0 1 2 3 4
   green connections: 1 2 1 2 1
    blue connections: 2 3 2
   

   现在处理剩余的绿色（少于2个使用过的顶点），再处理少于3倍的蓝色顶点。如果连接少于3个，则选择已使用的连接的下一个点；如果连接大于1个，则选择最接近的一个（图像上的红线）。

line(0,2)绿色0连接到蓝色0，所以从蓝色1,2（1太用了，所以2）中进行选择
line(2,-)绿色2连接到蓝色1（使用了3次），因此忽略此顶点
line(4,-)绿色4连接到蓝色2（使用了3次）所以忽略这个顶点

                index: 0 1 2 3 4
    green connections: 2 2 1 2 1
     blue connections: 2 3 3

仅此而已。现在，您应该像这样完成镶嵌处理：

[笔记]

• 您还可以使用周长位置/周长代替角度（有时效果更好）
• 凹面多边形会使这一点变得很混乱，因此应添加一些三角形相交检查以避免出现问题。
• also the number of vertexes should not differ too much between polygons in that case you can still divide some lines to add missing points otherwise that 3 times usage conditions will be wrong (if the vertex count differs 2 or more times)
• if you want to be safe you should cut polygons to convex parts and tesselate them separately and only after that join the meshes back together

[Edit1] new approach less susceptible to concavity and points density

Its slower but looks its working for more complex shapes. As example I took the modified star and plus sign from the comments.

1. find two closest points in each polygons

   this will be used as start point

2. reorder vertexes from this two start points

   with the same winding rule for example CW like on image

3. prepare edge lists

   we will need a structure holding all the connections between polygons. I decided to something like this:

   a=atan2(vertex-center)
   

   where edg0[point0][i] is holding i-th point1 connected to point0. Beware in the code array index is the point index and the actual value n the array is point index in a global point table pnt where I can transform between the two like this:

   point0 = (pnt_index - ix0)/3 
   point1 = (pnt_index - ix1)/3 
   pnt_index = ix0 + 3*point0
   pnt_index = ix1 + 3*point1
   

   where ix0,ix1 are start indexes in pnt for each polygon.

4. join close points

   Instead of joining to the closest points I added thresholding so the point distance must be smaller than threshold minll. This threshold is a multiply of the distance of the 2 start points (min distance). In code:

   minll=2.5*l0;
   

   but beware I am comparing distance^2 for speed so if you got distance it would be

   minl=sqrt(2.5)*l0;
   

   The multiply coefficient can be tweaked ...

   

   as you can see the distant point on star is not connected due thresholding.

5. fill unused holes in points0

   simply find sequence of unused points0 and then interpolate the join from start to end with first neighbors that are connected. so if points0 i0 .. i1 are unconnected and their closest neighbors are connected take their closest connected points1 j0 .. j1 and simply linearly connect point i with j where:

   i = i0 + t*(i1-i0)
   j = j0 + t*(j1-j0)
   

   where t is parameter t=<0.0,1.0> going through all "integer" point indexes. (use DDA).

   

6. fill unused holes in points1

   its the same as #5 but look for the unconnected points1 in the other polygon.

   

7. find&connect singular connection lines

   both endpoints are used just once. So simply find such edge and connect it to neighboring points.

   

8. find singular poinst0 that form QUAD hole and triangulate it

   so find point0 that is connected just once and then test its neighbors if the are connected back to the point1 the first one was connected to. If no you found QUAD hole so triangulate it.

   

9. now just extract triangles and lines from the edg0,edg1

   line are simple as they are already encoded directly, for triangles simply search neighboring point0 for connection to the same point1. If found form a triangle. the triangles should be formed also in the other edge list so search neighboring point1 that are connected to the same point0 too.

Here GL/C++ example

index: 0   1   2   3   4
green: 355 085 135 170 230 
 blue: 020 135 255

I also us