Quick algorithm to find the common faces of polyhedrons

[ztdep]

*Dear friends:
    I need a quick algorithm to find the common faces of polyhedrons meshes for the finite volume computation. Each plolyhedron is recorded with the indexes of its six vertices(hexahedron) or four vertices(tetrahedron). Each polyhedron has only one common face with its neighboring polyhdrons.
    The common face can be obtained by a slow comparison procedure, if two faces have the same set of indexes, then it is a common face between these two polyhedron.But the mesh system is too large, it will need a long time to find all the common faces. 
    Could you please suggest me a quick algorithm to find all the faces. 
    Regards
  Your Sincerely*

[rubberman]

We don't do your homework for you. Do some Google searching - you'll soon find what you need online.

[ztdep]

No one let youdo homework, i find nothing . if you can not give any suggestions , just shut up! and goto
sleep

[mike_2000_17]

There are a few ways to solve this problem reasonably quick. They generally depend on how much memory your are willing to spend (i.e., the classic computer science lesson: memory-complexity can often offset time-complexity).

The "slow" method, as you described, is to go through all faces and then for each of them go through all the other faces to find a match. This algorithm has a time-complexity of O(N^2) where N is the number of faces. This is pretty much as slow as it can get, but requires no additional storage besides the storage for the mesh and for the output.

A better method hinges on the fact that the core operation that takes time is "looking for the match". If you are going to look through all faces for a potential match, this is O(N) and since you do that look-up N times, this gives you that O(N^2) complexity. However, you can build a search tree to accelerate the look-ups by using the fact that the matching face probably belongs to a polyhedra that is reasonably close to the one to which the first face belongs to. If you have a search tree that allows you to quickly obtain a small neighborhood of polyhedras, then that dramatically reduces the possibilities for a matching face. Typical search trees used for this kind of thing are called space partitioning trees (e.g., Kd-tree, octree, and many others). In general, you can resolve such nearest neighbor queries in O(log(N)) time-complexity. And since you do this operation N times, the overall complexity is O(N log(N)). Of course, you first need to construct the space partitioning tree, in general, that can be done in O(N log(N)) time-complexity too. Of course, this method also results in quite a bit of storage required to construct the tree structure.

An even better method (probably the best) uses the fact that you know that you will eventually go through all faces at least once, and that you are interested in all associations. So, there must be a way to do all the work in linear time, if you record the appropriate information along the way. For example, if you go through each polyhedra and for each of its vertices, you add (within the vertex) a reference (pointer) to that polyhedra, i.e., saying "this vertex belongs to that polyhedra, among others". Once you have gone through all the polyhedra once, you can go through all the faces, and for each face, you should find exactly two polyhedron (or just one, if on the boundary) that is common to all vertices of that face, giving you what you are looking for. This algorithm will perform in O(N) time, but will require quite a bit more storage (a list of pointers for each vertex).

if you can not give any suggestions , just shut up! and goto sleep

No need to be rude, or impatient.

[ztdep]

I tried to solve this problem by map<IndexPair, int> , the IndexPair record the vertices index of the face, and int record which cell the face is belong to .

In the IndexPair, the Index1, Index2, Index3 and Index4 is ordered by the indexes of the vertices of faces.if faces have three vertices, then the Index1 is set at a value of -1.
The problem is the defination of the < operator in the IndexPair, the code can work but it can not find all the faces in the mesh.
Could you please give me some advices with the < operator

class IndexPair
{
public:
    int Index1; 
    int Index2;
    int Index3;
     int Index4;

// the originIndex is the sequence of the input mesh file 
    int originIndex1;
    int originIndex2;
    int originIndex3;
    int originIndex4;

// the default constructor for the indexPair 
    IndexPair(const int i1, const int i2,const int i3):originIndex1(i1),originIndex2(i2),originIndex3(i3),originIndex4(-1)
    { 
        vector<int> temp(3);
        temp[0]=i1;temp[1]=i2;temp[2]=i3;

        for( int i=0;i<3;i++)
        {

            for( int j=i+1;j<3;j++){
                                                  if(temp[i]>temp[j]) {int t1=temp[i];temp[i]=temp[j];temp[j]=t1;}
                                                  if(temp[i]==temp[j])  {cout<<endl<<" the value in IndexPair should not have the same value "<<endl;  exit(1);}
                                                   }
        }

         Index1=-1; Index2=temp[0];Index3=temp[1];Index4=temp[2];

    }

    IndexPair(const int i1, const int i2,const int i3,const int i4):originIndex1(i1),originIndex2(i2),originIndex3(i3),originIndex4(i4)
    { 
        vector<int> temp(4);
        temp[0]=i1;temp[1]=i2;temp[2]=i3;temp[3]=i4;

        for( int i=0;i<4;i++)
        {

            for( int j=i+1;j<4;j++) {
                                                   if(temp[i]>temp[j]) {int t1=temp[i];temp[i]=temp[j];temp[j]=t1;}
                                                      if(temp[i]==temp[j])
                                                      {cout<<endl<<" the value in IndexPair should not have the same value "<<endl;  exit(1);}
                                                           }
        }
        Index1=temp[0]; Index2=temp[1];Index3=temp[2];Index4=temp[3];
    }

    bool operator< ( const IndexPair & aPair ) const      
    {  
        if(Index1<aPair.Index1) return true;
        else if(Index1==aPair.Index1) return Index2<aPair.Index2;
        else if(Index1==aPair.Index1&&Index2==aPair.Index2) return Index3<aPair.Index3;
        else if(Index1==aPair.Index1&&Index2==aPair.Index2&&Index3==aPair.Index3) return Index4<aPair.Index4;
        else return false;
    }



};