Tessellate a plane of points

I have a file filled with 3d points. The points form a plane. Here is an example file:

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

Edit: Since my example set of points was too simple, here is a more complex example.

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

These points are plotted like so:

This file states that there are 25 points in the plane, and lists the points. The points are regularly spaced. Based on this information, how could I form triangles out of the point data and store it in a std::vector<Tri> where Tri is a

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

Note also: Problem restrictions: External libraries are not allowed. The use of C++0X is not allowed (compiler: g++ 4.5.2).

c++ algorithm math

Edit Report

1 Answer

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:

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.)
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:

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.
If the new point to add is in the interior of an existing triangle, replace that triangle with three subtriangles.
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.
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

answered 2012-07-24T17:29:52.447

Tessellate a plane of points

1 Answer

Your Answer