Core Mesh Data Structures in C++

Partition

Many graph and mesh processing algorithms, such as those that compute connected components of a graph or mesh, require a data structure to maintain a partition of a finite set. A partition of a set is a family of disjoint subsets of the set called parts, whose union is equal to the whole set. 

 class Partition {
   public:
             Partition(const int N);
     void    reset(const int N);
     int     getNumberOfElements()          const;
     int     getNumberOfParts()             const;
     int     find(const int i);
     int     join(const int i, const int j);
     int     getSize(const int i)           const;
 }

The constructor Partition(N) creates a partition of the set of integers {0,1,...,N-1} into singletons {0},{1},...,{N-1}. At any particular time the partition is composed of a certain number of parts. The method find(i) returns the part index of the part which contains the element i and the method size(i) returns the number of elements in the part which contains the elementi. If the element i is out of range 0≤i<N, then the method find(i) returns the value -1, and the method size(i) returns 0.

If the elements i and j are in the range 0≤i,j<N and they belong to different parts, then the method join(i,j) joins the two parts into a single one, and returns the part index of the new part. The two previous part indices should be regarded as no longer valid, although one of the two may be reused for the new part in a particular implementation. If either one of the two elements i and j is out of range, or the two elements belong to the same part, then the method join(i,j) returns the value -1.

The method getNumberOfElements() returns the number of elements of the underlying set, i.e., the parameter N passed to the constructor. The method getNumberOfParts() returns the current number of parts in the partition. The method reset(N) resets the partition to the set of singletons {0},{1},...,{N-1}, and allows the number of elements to be changed.

SplittablePartition

 class SplittablePartition : public Partition {
   public:
             SplittablePartition(const int N);
     void    split(const int i);
 }

The Partition data structure does not allow any part of the partition to be split. Parts can only be joined. The SplittablePartition(N) has an additional method split(i) which splits the part containing the element i, if the element is within the range 0≤i<N. It is an error to call this method with the element out of range, but it is safe for the method not to do anything in that case.

Next : Polygon Mesh

Core Mesh | Faces | Edges | Graph | HalfEdges | Partition | PolygonMesh | Queues