8

我有一个充满 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

这些点绘制如下：

http://i.imgur.com/6zRrA.png

该文件指出平面上有 25 个点，并列出了这些点。这些点有规律地间隔开。基于此信息，我如何从点数据中形成三角形并将其存储在std::vector<Tri>where Triis a

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

另请注意：问题限制：不允许使用外部库。不允许使用 C++0X（编译器：g++ 4.5.2）。

4

4 回答 4

3

阅读第一行，调用它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)]);
   }
}

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

于 2012-07-24T16:06:35.247 回答
0

当然有很多不同的方法可以从一组顶点中获取一组三角形，所以我不确定我是否理解整个问题的要求。

但我的方法可能看起来像这样：

  1. 为了解决浮点舍入和/或数据准确性问题，我将首先使用最小二乘拟合算法之类的方法确定平面的法线向量。（虽然你不需要飞机本身，只需要方向。）

  2. 编写算法以使用该法线向量来确定一些常见的平面问题，例如“点 D 在三角形 ABC 的内部吗？” 和“线段 AB 和 CD 相交吗？” （在平面投影中）。

如果您有一些已知的输入结构，从这一点开始很容易，或者您想要使用现有的平面算法，那就太好了。

如果您只想获得任何一组细分凸包的非重叠三角形：

  1. 从任意三个点和一个三角形开始。还记得一个有序的顶点循环，形成到目前为止所覆盖区域的边界多边形。然后一次一个地添加其余的点。

  2. 如果要添加的新点位于现有三角形的内部，则将该三角形替换为三个子三角形。

  3. 否则，确定从边界多边形顶点到新点的哪些 N (N>=2) 条线段不与边界多边形相交。添加 (N-1) 个新三角形。新点将 (N-2) 个旧点替换为边界多边形中的新顶点。

  4. 假设避免几乎共线的三角形和不必要的长线段是一件好事：遍历不在边界上的三角形边缘，并检查两个相邻三角形覆盖的四边形是否是凸的，以及它的另一个对角线是否（显着) 比正在研究的常见三角形边短。如果是这样，请替换这两个三角形。重复直到不能再进行这样的替换。（这个循环必须终止，因为边的总长度总是在减少，并且有有限数量的镶嵌。）

于 2012-07-24T17:29:52.447 回答
0

将平面上的网格分成一组线。通过取一条线上的每对相邻点并将相邻线上该对中每个成员的最近点添加到该对中来给出曲面细分。

您可以使用矢量算术将平面分成线。将文件中的第一个点作为平面基础，将第二个点的向量作为您的 X 轴。将向量从第一个点投影到 X 轴向量上的任意一点，并将投影的长度作为 X 坐标。由于您假设一个规则网格，这些值应该是 0、1、2、3 等等，直接将点分割成线。

于 2012-07-24T16:11:46.037 回答
0

对于镶嵌算法，尝试创建相邻点的直角三角形并将其推送到向量（不重叠）。假设您以正确的顺序将所有点存储在m x n矩阵中，您可以创建这组三角形：

  • {(i,j),(i+1,j),(i+1,j+1)}对于0 < i < m-1和0 < j < n-1。
  • {(i,j+1), (i+1,j+1), (i,j)对于0 < i < m-1和0 < j < n-1。

我对三角形使用 {p1,p2,p3} 的形式，对矩阵中点的索引对使用 (x,y) 形式。在您的情况下，这些m和n变量也等于 5。

于 2012-07-24T16:12:47.453 回答