PropertyTopomesh Data Structure

The central data structure in CellComplex is a representation of cellular complexes implemented as incidence graphs, in an class called PropertyTopomesh. Cell complexes are seen as boundary representations consisting of a collection of topological elements of dimension 0 up to 3, where each higher-dimension element is defined by the set of its lower-dimension boundary elements. In PropertyTopomesh those elements are called wisps.

  • A wisp of dimension 0 is a vertex, and, as the lowest possible dimension, it is the only one without boundaries.

Note

Instead it is defined by its spatial position, that is generally sufficient for the geometrical embedding of the whole cellular complex.

  • A wisp of dimension 1 is an edge and is generally defined by exactly 2 boundary vertices.

  • Wisps of dimension 2 are faces and require at least 3 boundary edges. If all faces have exactly 3 edges, the PropertyTopomesh forms a triangular mesh.

  • Finally, cells correspond to the wisps of dimension 3.

Note

Even though they conceptually represent entities of geometrical dimension 3, in a number of cases where the complex is a 2-manifold, cells may be defined as sets of faces.

Wisps : a pre-built example

The hexagon_topomesh function creates a simple 2D-embedded cellcomplex, consisting of one hexagonal cell represented as a triangular mesh.

1
2
3
from cellcomplex.property_topomesh.example_topomesh import hexagon_topomesh

topomesh = hexagon_topomesh()

(Source code, png, hires.png, pdf)

../_images/property_topomesh-1.png

In a PropertyTopomesh, wisps are represented by unique integer IDs at each dimension. The methods nb_wisps and wisps allow to access respectively the number of elements and the list of their IDs at each dimension.

1
2
3
4
print(topomesh.nb_wisps(0),"Vertices :",list(topomesh.wisps(0)))
print(topomesh.nb_wisps(1),"Edges :",list(topomesh.wisps(1)))
print(topomesh.nb_wisps(2),"Faces :",list(topomesh.wisps(2)))
print(topomesh.nb_wisps(3),"Cells :",list(topomesh.wisps(3)))

7 Vertices : [0, 1, 2, 3, 4, 5, 6]
12 Edges : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
6 Faces : [0, 1, 2, 3, 4, 5]
1 Cells : [0]

The whole topology of the complex relies on the boundary relationships between its wisps. The topology relationships can be displayed as a graph showing the incidence (edges) between wisps (vertices) of contiguous dimensions.

(Source code, png, hires.png, pdf)

../_images/property_topomesh-2.png

The whole geometry of the complex is then determined only by the spatial position assigned to each wisp of dimension 0. It is defined as a Python dictionary pairing each ID of a wisp of dimension 0 to a NumPy array representing a point in a 3-dimensional space. This dictionary is stored within the data structure as a property defined on the dimension 0, named 'barycenter'.

1
print(topomesh.wisp_property('barycenter',0))

{0: [0.        0.         0.       ],
 1: [1.        0.         0.       ],
 2: [0.5       0.8660254  0.       ],
 3: [-0.5      0.8660254  0.       ],
 4: [-1.       0.         0        ],
 5: [-0.5      -0.8660254 0.       ],
 6: [ 0.5      -0.8660254 0.       ]}

Note

The property is not an instance of dict, but uses a custom implementation based on NumPy arrays called array_dict.

Neighbor relationship(s)

The incidence relationship accessible through regions and borders makes a connection between elements of different topological dimensions. However, it is often useful to look for elements of the same dimension that are adjacent to each other. This is what the neighbor relationship is about.

But whether two wisps of a given dimension can be considered neighbors is not necessarily uniquely defined. In the case of dimension 0 for instance, we generally consider two vertices to be neighbors if they are linked together by an edge (i.e. an element of dimension 1). This corresponds to the concept of region_neighbors where the neighborhood relationship is defined as the borders of the regions. In other terms, it requires going up one level in the incidence graph before going down one level to link two elements.

1
2
3
4
5
from cellcomplex.property_topomesh.example_topomesh import square_grid_topomesh

topomesh = square_grid_topomesh(1)

print(list(topomesh.region_neighbors(0,3)))

[0, 4, 6]

(Source code, png, hires.png, pdf)

../_images/property_topomesh-7.png

However if we apply the same logic to edges, or even faces the results might be surprising. For instance here, all the faces have 0 region_neighbors, since each face corresponds to a unique cell at dimension 3. They don’t have shared regions, so they don’t have neighbors defined by their common regions.

1
2
for f in topomesh.wisps(2):
    print("Face "+str(f)+": "+str(topomesh.nb_region_neighbors(2,0))+" neighbors")

Face 0: 0 neighbors
Face 1: 0 neighbors
Face 2: 0 neighbors
Face 3: 0 neighbors

In this case, it is more appropriate to look for the wisps of the same dimension that have at least one border in common with the considered wisp. In other terms, to go down one level in the incidence graph before going up one level to connect two neighbors. This is what the border_neighbors method does.

1
print(list(topomesh.border_neighbors(2,0)))

[1, 2]

Note

If you wanted to find the faces that share at least one vertex with the considered face, you would need to go one level further in the adjacency graph. This offset functionality is not supported in the region_neighbors and border_neighbors methods.

Neighbor relationships are implicitly contained in the incidence graph structure that is at the core of PropertyTopomesh, but it requires a small computation at each call. Instead, it might be more efficient to pre-compute all neighbors once to perform more efficiently. The way to do it is illustrated along with other tools to simplify topology-based computations in the Topology Analysis example page

Properties

The data structure contains the geometry and topology of the cells of the complex, and also offers the possibility to assign any number of properties to each of its topological elements (vertices, edges, faces or cells) under the form of dictionaries pairing wisp IDs and property values.

The following code assigns a new scalar property to faces. The method update_wisp_property inputs a property name, a dimension and a dictionary and in this case assigns a random value (between 0 and 1) to each face element of the hexagon cellcomplex.

1
2
3
4
5
6
import numpy as np

from cellcomplex.property_topomesh.example_topomesh import hexagon_topomesh

topomesh = hexagon_topomesh()
topomesh.update_wisp_property('random',2,dict(zip(topomesh.wisps(2),np.random.rand(topomesh.nb_wisps(2)))))

(Source code, png, hires.png, pdf)

../_images/property_topomesh-8.png

Note

Properties can be of any type, however it is recommended that for a given property, all wisps share the same property type.

The functions in CellComplex will generally support:

  • Scalar properties (either int or float)

  • Vector properties as 1d NumPy arrays

  • Tensor properties as 2d square NumPy arrays

  • Categorial properties as strings

The method wisp_property returns an array_dict instance that makes it possible to modify the values stored in the structure, using the IDs of the wisps as keys of the dictionary.

1
2
3
for w in topomesh.wisps(2):
    topomesh.wisp_property('random',2)[w] = 1
print(topomesh.wisp_property('random',2))

{0: 1.0,
 1: 1.0,
 2: 1.0,
 3: 1.0,
 4: 1.0,
 5: 1.0}

Properties are useful to store a number of useful data on the topological elements of the complex, for instance topological information that we don’t want to recompute (neighbor IDs, face vertices,…) of geometrical information that can be computed using topology and vertex positions. There is a whole module named property_topomesh_analysis that provides tools to compute useful properties on cell complexes. Most of them are presented in the Geometry Analysis example page of this documentation.