0

We want to create our own list of triangles from a list already existed of STL mode (it's a 3D geometric model, which composed of triangle), several triangle can had the same point, we want to use the best solution:

S1) that goes through the list, use the coordinates of each triangle (element) of this list to create a triangle object and we put it in our list (victor). but here there are points that must be created multiple times, because as I have said many triangles can have the same point.

S2) there already existed another list that contains all the points, then it goes through the list of triangle already existed and for each point of triangle we search it in the list of points (so we have to use sort and search algorithms) to use pointers (point on these points) and create objects that contients 3 pointers (*p1, *p2, *p3) and put them in our list.

HamidMly
  • 42
  • 1
  • 7
  • Unless you get out of memory (or use too much), store the trivial structure and avoid pointers. On the other hand geometric algorithms may take advantage of knowing a point belonging to multiple triangles. –  Apr 22 '15 at 17:14
  • 1
    The question is not clear to me. An example would be of great help. – Nawaz Apr 22 '15 at 17:16
  • sorry mister @Nawaz, my English is not good – HamidMly Apr 22 '15 at 17:22
  • One popular solution is S3) Have a list of all unique points, store the indexes of the points in the "point list" and look them up when you need them (and the list should most likely not be a list but something contiguous, like a vector). – molbdnilo Apr 22 '15 at 17:22
  • I agree with @DieterLücking: it really depends on algorithms you are going to run on this data. So the simplest solution would be to prototype both approaches and measure performance (assuming performance is your main concern). – anxieux Apr 22 '15 at 17:24
  • Thanks Mr.@molbdnilo, but i need this ponts to creat triangle list. – HamidMly Apr 22 '15 at 17:25

1 Answers1

1

Store the points in an std::unordered_set then store the triangles as a list of structures containing 3 std::unordered_set::const_iterator's.

Insertion of the points into the set will be approximately constant time and the insert returns a pair that contains the iterator where the point can be found.

Have a look here for more details on how insert works.

Here's the basic structure of the code (untested)

struct Point
{
    float x;
    float y;
    float z;
};

typedef std::unordered_set<Point, int, hashFunc, equalsFunc> pset;

// Note, see http://stackoverflow.com/questions/16792751/hashmap-for-2d3d-coordinates-i-e-vector-of-doubles for more details on how to store complex structures in unordered_sets

struct RefTriangle
{
   pset::const_iterator p[3];
};

pset allPoints;
std::list<RefTriangle> refTriangles

for (const Triangle& t : triangleList)
{
    RefTriangle rt;
    rt.p[0] = allPoints.insert(t.p1).first;
    rt.p[1] = allPoints.insert(t.p2).first;
    rt.p[2] = allPoints.insert(t.p3).first;
    refTriangles.push_back(rt);
}

In the end you'll have a set of unique points and a list of reference triangle objects that effectively have "pointers" to those points in the unique set.

cppguy
  • 3,611
  • 2
  • 21
  • 36