镶嵌点平面

Question

我有一个填充3d点的文件.这些点形成一个平面.这是一个示例文件:

25
1 -1 0
1 -0.5 0
1 0 0
1 0.5 0
1 1 0
0.5 -1 0
0.5 -0.5 0
0.5 0 0
0.5 0.5 0
0.5 1 0
0 -1 0
0 -0.5 0
0 0 0
0 0.5 0
0 1 0
-0.5 -1 0
-0.5 -0.5 0
-0.5 0 0
-0.5 0.5 0
-0.5 1 0
-1 -1 0
-1 -0.5 0
-1 0 0
-1 0.5 0
-1 1 0

编辑:由于我的示例点集太简单了,这里有一个更复杂的例子.

30
-0.298858 -0.816497 1.11536
0.0546949 -0.816497 0.761802
0.408248 -0.816497 0.408248
0.761802 -0.816497 0.0546949
1.11536 -0.816497 -0.298858
-0.462158 -0.489898 0.952056
-0.108604 -0.489898 0.598502
0.244949 -0.489898 0.244949
0.598502 -0.489898 -0.108604
0.952056 -0.489898 -0.462158
-0.625457 -0.163299 0.788756
-0.271904 -0.163299 0.435203
0.0816497 -0.163299 0.0816497
0.435203 -0.163299 -0.271904
0.788756 -0.163299 -0.625457
-0.788756 0.163299 0.625457
-0.435203 0.163299 0.271904
-0.0816497 0.163299 -0.0816497
0.271904 0.163299 -0.435203
0.625457 0.163299 -0.788756
-0.952056 0.489898 0.462158
-0.598502 0.489898 0.108604
-0.244949 0.489898 -0.244949
0.108604 0.489898 -0.598502
0.462158 0.489898 -0.952056
-1.11536 0.816497 0.298858
-0.761802 0.816497 -0.0546949
-0.408248 0.816497 -0.408248
-0.0546949 0.816497 -0.761802
0.298858 0.816497 -1.11536

这些点的绘制如下:

此文件表明平面中有25个点,并列出了这些点.这些点是有规律的间隔.基于这些信息,我怎么可能形成三角形出点数据,并将其存储在一个std::vector<Tri>地方Tri是

struct Tri 
{
  double x1, y1, z1;
  double x2, y2, z2;
  double x3, y3, z3;
};

另请注意:问题限制:不允许使用外部库.不允许使用C++ 0X(编译器:g ++ 4.5.2).

Answer 1

阅读第一行，将其命名为N。将其余点读入数组中A。

Point xdir = A[1] - A[0];
int xdim = 2;
while (A[xdim] - A[xdim-1] == xdir) xdim++;
int ydim = N / xdim;
for (int y = 0; y < ydim-1; y++) {
   for (int x = 0; x < xdim-1; x++) {
      addTriangle(A[y*xdim+x],A[(y+1)*xdim+x],A[(y+1)*xdim+(x+1)]);
      addTriangle(A[y*xdim+x],A[y*xdim+(x+1)],A[(y+1)*xdim+(x+1)]);
   }
}

当然，这是假设您确实按网格顺序获得了所有分数。如果没有，请先对它们进行排序。