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>場所に格納するにTriはどうすればよいですか。

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

Separate the grid on the plane into a set of lines. The tesselation is given by taking each pair of adjacent points on a line and adding the closest point of each member of the pair in the adjacent lines to the pair.

You can separate the plane into lines by using vector arithmetics. Take the first point in the file as the plane basis, and the vector to the second point as your X axis. Project the vector from the first point to any point on the X axis vector, and use the length of the projection as the X coordinates. Since you assume a regular grid, these values should be 0, 1, 2, 3, and so on, straightforwardly segmenting the points into lines.

于 2012-07-24T16:11:46.037 に答える
0

For the tesselation algorithm, try creating, and pushing to the vector, right triangles of adjacent points (without overlapping them). Assuming you have stored all points in an m x n matrix in the right order, you can create this set of triangles:

  • {(i,j),(i+1,j),(i+1,j+1)} for 0 < i < m-1 and 0 < j < n-1.
  • {(i,j+1), (i+1,j+1), (i,j) for 0 < i < m-1 and 0 < j < n-1.

I used the form {p1,p2,p3} for a triangle and (x,y) for the point's index pair in the matrix. In your case also, these m and n variables are equal to 5.

于 2012-07-24T16:12:47.453 に答える
0

There are of course many different ways to get a set of triangles from a set of vertices, so I'm not sure I understand the entire problem requirements.

But my approach would probably look something like this:

  1. To account for floating point rounding and/or data accuracy issues, I would first determine a normal vector to the plane, using something like a least squares fit algorithm. (Though you don't need the plane itself, just the direction.)

  2. Write algorithms to use that normal vector to determine some common plane questions like "Is point D in the interior of triangle ABC?" and "Do segments AB and CD intersect?" (in the plane projection).

If you have some known structure to the input that makes it easy from this point, or an existing plane algorithm you want to use, great.

If you just want to get any set of non-overlapping triangles that tesselate the convex hull:

  1. Start with any three points and a single triangle. Remember also an ordered cycle of vertices forming the boundary polygon of the region covered so far. Then add the rest of the points one at a time.

  2. If the new point to add is in the interior of an existing triangle, replace that triangle with three subtriangles.

  3. Otherwise, determine which N (N>=2) line segments from boundary polygon vertices to the new point do not intersect the boundary polygon. Add (N-1) new triangles. The new point replaces (N-2) old points as a new vertex in the boundary polygon.

  4. Assuming it's a good thing to avoid nearly-collinear triangles and unnecessarily long segments: Loop over the triangle edges which are not on the boundary, and check whether the quadrilateral covered by the two adjacent triangles is convex, and whether its other diagonal is (significantly) shorter than the common triangle edge being investigated. If so, replace those two triangles. Repeat until no more such substitutions can be made. (This loop must terminate since the total length of edges is always decreasing, and there are a finite number of tesselations.)

于 2012-07-24T17:29:52.447 に答える