.. toctree:: :maxdepth: 2 .. _examples-property-topomesh: ################################################################################ PropertyTopomesh Data Structure ################################################################################ The central data structure in :mod:`CellComplex ` is a representation of cellular complexes implemented as incidence graphs, in an class called :class:`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 :class:`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 :class:`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 :func:`hexagon_topomesh ` function creates a simple 2D-embedded cellcomplex, consisting of one hexagonal cell represented as a triangular mesh. .. code-block:: python :linenos: from cellcomplex.property_topomesh.example_topomesh import hexagon_topomesh topomesh = hexagon_topomesh() .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh.example_topomesh import hexagon_topomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = hexagon_topomesh() figure = plt.figure(0) figure.clf() figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,2,color='g') mpl_draw_topomesh(topomesh,figure,1,color='b') mpl_draw_topomesh(topomesh,figure,0,color='m') figure.gca().axis('off') figure.tight_layout() In a :class:`PropertyTopomesh `, ``wisps`` are represented by unique integer IDs at each dimension. The methods :func:`nb_wisps ` and :func:`wisps ` allow to access respectively the number of elements and the list of their IDs at each dimension. .. code-block:: python :linenos: 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))) .. code-block:: bash 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. .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh.example_topomesh import hexagon_topomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = hexagon_topomesh() figure = plt.figure(0) figure.clf() figure.add_subplot(1,2,1) figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,2,color='g',plot_ids=True) mpl_draw_topomesh(topomesh,figure,1,color='b',plot_ids=True) mpl_draw_topomesh(topomesh,figure,0,color='m',plot_ids=True) figure.gca().axis('off') figure.add_subplot(1,2,2) figure.gca().axis('equal') mpl_draw_incidence_graph(topomesh,figure,plot_ids=True) figure.gca().axis('off') figure.set_size_inches(10,5) figure.tight_layout() 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'``. .. code-block:: python :linenos: print(topomesh.wisp_property('barycenter',0)) .. code-block:: bash {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 :class:`dict `, but uses a custom implementation based on NumPy arrays called :class:`array_dict `. .. _examples-property-topomesh-link: ************************* Link, borders and regions ************************* In this section, we will see how to create a cell complex from scratch by defining explicitly all the boundary relationships between the topological elements. When a :class:`PropertyTopomesh ` is created, it comes as an empty structure containing no ``wisp`` of any dimension. The first step consists then in adding new elements using the :func:`add_wisp ` function, that takes a *dimension* and an optional ID argument. In any case the ID of the new element is returned. Then in the case of vertices, it is necessary to assign a ``'barycenter'`` property to the newly created ``wisps``. .. code-block:: python :linenos: from cellcomplex.property_topomesh import PropertyTopomesh topomesh = PropertyTopomesh() topomesh.add_wisp(0,0) topomesh.add_wisp(0,1) topomesh.add_wisp(0,2) topomesh.add_wisp(0,3) topomesh.update_wisp_property('barycenter',0,{0:[-1,-1,0],1:[1,-1,0],2:[-1,1,0],3:[1,1,0]}) .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh import PropertyTopomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = PropertyTopomesh() topomesh.add_wisp(0,0) topomesh.add_wisp(0,1) topomesh.add_wisp(0,2) topomesh.add_wisp(0,3) topomesh.update_wisp_property('barycenter',0,{0:[-1,-1,0],1:[1,-1,0],2:[-1,1,0],3:[1,1,0]}) figure = plt.figure() figure.clf() figure.add_subplot(1,2,1) figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,0,color='m',plot_ids=True) figure.gca().axis('off') figure.add_subplot(1,2,2) figure.gca().axis('equal') mpl_draw_incidence_graph(topomesh,figure,plot_ids=True) figure.gca().axis('off') figure.set_size_inches(10,5) figure.tight_layout() The :func:`link ` method allows to define the boundary relationships by assigning to the id of a ``wisp`` of dimension *d* the id of a ``wisp`` of dimension *d-1* that forms its boundary. Let's first add a new ``wisp`` of dimension 1 and then ``link`` it to two ``wisps`` of dimension 0 in order to create an edge. .. code-block:: python :linenos: eid = topomesh.add_wisp(1) topomesh.link(1,eid,0) topomesh.link(1,eid,1) .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh import PropertyTopomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = PropertyTopomesh() topomesh.add_wisp(0,0) topomesh.add_wisp(0,1) topomesh.add_wisp(0,2) topomesh.add_wisp(0,3) topomesh.update_wisp_property('barycenter',0,{0:[-1,-1,0],1:[1,-1,0],2:[-1,1,0],3:[1,1,0]}) eid = topomesh.add_wisp(1) topomesh.link(1,eid,0) topomesh.link(1,eid,1) figure = plt.figure() figure.clf() figure.add_subplot(1,2,1) figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,1,color='b',plot_ids=True) mpl_draw_topomesh(topomesh,figure,0,color='m',plot_ids=True) figure.gca().axis('off') figure.add_subplot(1,2,2) figure.gca().axis('equal') mpl_draw_incidence_graph(topomesh,figure,plot_ids=True) figure.gca().axis('off') figure.set_size_inches(10,5) figure.tight_layout() The basic method that allows to access the boundary relationship of a cell complex is the method :func:`borders ` that inputs a dimension and a ``wisp`` ID and yields the list of all ``wisp`` IDs of immediately inferior dimension that form the boundary of the considered element. Obviously, the method raises an error when the dimension is equal to 0. For example this call lists the vertex IDs that form the boundary of the edge element (dimension **1**) of ID **0**. .. code-block:: python :linenos: print(list(topomesh.borders(1,0))) .. code-block:: bash [0, 1] To complete the topological structure, one must explicitly add all the necessary elements and call :func:`link ` so that all necessary connections are made. .. note:: For the structure to be valid, all the ``wisps`` of dimension 1 should have 2 borders of dimenson 0. .. code-block:: python :linenos: topomesh.add_wisp(1,1) topomesh.add_wisp(1,2) topomesh.add_wisp(1,3) topomesh.add_wisp(1,4) topomesh.link(1,1,0) topomesh.link(1,1,2) topomesh.link(1,2,1) topomesh.link(1,2,2) topomesh.link(1,3,1) topomesh.link(1,3,3) topomesh.link(1,4,2) topomesh.link(1,4,3) .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh import PropertyTopomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = PropertyTopomesh() topomesh.add_wisp(0,0) topomesh.add_wisp(0,1) topomesh.add_wisp(0,2) topomesh.add_wisp(0,3) topomesh.update_wisp_property('barycenter',0,{0:[-1,-1,0],1:[1,-1,0],2:[-1,1,0],3:[1,1,0]}) topomesh.add_wisp(1,0) topomesh.add_wisp(1,1) topomesh.add_wisp(1,2) topomesh.add_wisp(1,3) topomesh.add_wisp(1,4) topomesh.link(1,0,0) topomesh.link(1,0,1) topomesh.link(1,1,0) topomesh.link(1,1,2) topomesh.link(1,2,1) topomesh.link(1,2,2) topomesh.link(1,3,1) topomesh.link(1,3,3) topomesh.link(1,4,2) topomesh.link(1,4,3) figure = plt.figure() figure.clf() figure.add_subplot(1,2,1) figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,1,color='b',plot_ids=True) mpl_draw_topomesh(topomesh,figure,0,color='m',plot_ids=True) figure.gca().axis('off') figure.add_subplot(1,2,2) figure.gca().axis('equal') mpl_draw_incidence_graph(topomesh,figure,plot_ids=True) figure.gca().axis('off') figure.set_size_inches(10,5) figure.tight_layout() At this state, the complex is only formed by a collection of edges and vertices. To create faces, we have to add new elements of dimension 2, and link them to the **edges** that define their boundaries. In the same way, to create a cell element, we have to create a ``wisp`` of topological dimension 3 and define the set of faces that constitute its boundary. .. note:: Unlike several other mesh representations, the link between faces and their vertices is not direct. It is only through the boundary relationship between faces and edges **and** between edges and vertices that we can access the vertices of a face. .. code-block:: python :linenos: topomesh.add_wisp(2,0) topomesh.add_wisp(2,1) topomesh.link(2,0,0) topomesh.link(2,0,1) topomesh.link(2,0,2) topomesh.link(2,1,2) topomesh.link(2,1,3) topomesh.link(2,1,4) topomesh.add_wisp(3,0) topomesh.link(3,0,0) topomesh.link(3,0,1) .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh import PropertyTopomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = PropertyTopomesh() topomesh.add_wisp(0,0) topomesh.add_wisp(0,1) topomesh.add_wisp(0,2) topomesh.add_wisp(0,3) topomesh.update_wisp_property('barycenter',0,{0:[-1,-1,0],1:[1,-1,0],2:[-1,1,0],3:[1,1,0]}) topomesh.add_wisp(1,0) topomesh.add_wisp(1,1) topomesh.add_wisp(1,2) topomesh.add_wisp(1,3) topomesh.add_wisp(1,4) topomesh.link(1,0,0) topomesh.link(1,0,1) topomesh.link(1,1,0) topomesh.link(1,1,2) topomesh.link(1,2,1) topomesh.link(1,2,2) topomesh.link(1,3,1) topomesh.link(1,3,3) topomesh.link(1,4,2) topomesh.link(1,4,3) topomesh.add_wisp(2,0) topomesh.add_wisp(2,1) topomesh.link(2,0,0) topomesh.link(2,0,1) topomesh.link(2,0,2) topomesh.link(2,1,2) topomesh.link(2,1,3) topomesh.link(2,1,4) topomesh.add_wisp(3,0) topomesh.link(3,0,0) topomesh.link(3,0,1) figure = plt.figure() figure.clf() figure.add_subplot(1,2,1) figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,2,color='g',plot_ids=True) mpl_draw_topomesh(topomesh,figure,1,color='b',plot_ids=True) mpl_draw_topomesh(topomesh,figure,0,color='m',plot_ids=True) figure.gca().axis('off') figure.add_subplot(1,2,2) figure.gca().axis('equal') mpl_draw_incidence_graph(topomesh,figure,plot_ids=True) figure.gca().axis('off') figure.set_size_inches(10,5) figure.tight_layout() Conversely to the :func:`borders ` method, the :func:`regions ` method makes it possible to access the IDs of the ``wisps`` of which a given ``wisp`` is a boundary. The method can not be called on ``wisps`` of highest dimension (in that case 3). Here for instance, the edge 0 only has one **region**, the triangular face with ID 0, whereas the edge 2 has two, faces 0 and 1. .. code-block:: python :linenos: print(list(topomesh.regions(1,0))) print(list(topomesh.regions(1,2))) .. code-block:: bash [0] [0, 1] Both the :func:`regions ` and :func:`borders ` methods may take a third argument that represent the offset of the relationship. The **borders** of a ``wisp`` of dimension *d* with an offset *o* are the ``wisps`` of dimension *d-o* that are part of its boundary (respectively *d+o* for the **regions**). .. code-block:: python :linenos: print(list(topomesh.borders(2,0,2))) .. code-block:: bash [0, 1, 2] The construction of a complex :class:`PropertyTopomesh ` using these primitives is a tedious task. Fortunately, :mod:`CellComplex ` comes with a number of pre-built functions to facilitate the construction of complexes, but all of them rely on the methods :func:`add_wisp ` and :func:`link ` to build the complex. Some examples can be found in :ref:`examples-creation`. In any case, the :func:`borders ` and :func:`regions ` methods are very useful tools to perform traversals on a cell complex. ************************ Neighbor relationship(s) ************************ The incidence relationship accessible through :func:`regions ` and :func:`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 :func:`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. .. code-block:: python :linenos: from cellcomplex.property_topomesh.example_topomesh import square_grid_topomesh topomesh = square_grid_topomesh(1) print(list(topomesh.region_neighbors(0,3))) .. code-block:: bash [0, 4, 6] .. plot:: import matplotlib.pyplot as plt from cellcomplex.property_topomesh.example_topomesh import square_grid_topomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = square_grid_topomesh(1) figure = plt.figure(0) figure.clf() figure.add_subplot(1,2,1) figure.gca().axis('equal') mpl_draw_topomesh(topomesh,figure,2,color='g',plot_ids=True) mpl_draw_topomesh(topomesh,figure,1,color='b',plot_ids=True) mpl_draw_topomesh(topomesh,figure,0,color='m',plot_ids=True) figure.gca().axis('off') figure.add_subplot(1,2,2) figure.gca().axis('equal') mpl_draw_incidence_graph(topomesh,figure,plot_ids=True) figure.gca().axis('off') figure.set_size_inches(10,5) figure.tight_layout() 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. .. code-block:: python :linenos: for f in topomesh.wisps(2): print("Face "+str(f)+": "+str(topomesh.nb_region_neighbors(2,0))+" neighbors") .. code-block:: bash 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 :func:`border_neighbors ` method does. .. code-block:: python :linenos: print(list(topomesh.border_neighbors(2,0))) .. code-block:: bash [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 :func:`region_neighbors ` and :func:`border_neighbors ` methods. Neighbor relationships are implicitly contained in the incidence graph structure that is at the core of :class:`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 :ref:`examples-topology` 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 :func:`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. .. code-block:: python :linenos: 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))))) .. plot:: import numpy as np import matplotlib.pyplot as plt from cellcomplex.property_topomesh.example_topomesh import hexagon_topomesh from cellcomplex.property_topomesh.utils.matplotlib_tools import mpl_draw_topomesh, mpl_draw_incidence_graph topomesh = hexagon_topomesh() topomesh.update_wisp_property('random',2,dict(zip(topomesh.wisps(2),np.random.rand(topomesh.nb_wisps(2))))) figure = plt.figure(0) figure.clf() figure.gca().axis('equal') col = mpl_draw_topomesh(topomesh,figure,2,property_name='random',colormap='viridis',intensity_range=(0,1)) mpl_draw_topomesh(topomesh,figure,1,color='k') mpl_draw_topomesh(topomesh,figure,0,color='k') figure.colorbar(col) figure.gca().axis('off') figure.tight_layout() .. 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 :mod:`CellComplex ` will generally support: * *Scalar* properties (either :class:`int ` or :class:`float `) * *Vector* properties as 1d :class:`NumPy arrays ` * *Tensor* properties as 2d square :class:`NumPy arrays ` * *Categorial* properties as :class:`strings ` The method :func:`wisp_property ` returns an :class:`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. .. code-block:: python :linenos: for w in topomesh.wisps(2): topomesh.wisp_property('random',2)[w] = 1 print(topomesh.wisp_property('random',2)) .. code-block:: bash {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 :mod:`property_topomesh_analysis ` that provides tools to compute useful properties on cell complexes. Most of them are presented in the :ref:`examples-analysis` example page of this documentation.