Discrete Morse Theory
I used Python to implement the algorithm mentioned in the previous chapter. The used version is python 3.8.2. To represent a topological space as simplical complex we use Ply files.

Ply files

PLY is a computer file format known as the Polygon File Format or the Stanford Triangle Format. It describes a graphical object. Every PLY-file describes only one object. The source of these objects can be created manually or by modeling programs like Blender Every object consists of elements. Example of elements are vertices, edges and faces. Every element have properties. For example vertices elements have properties like position expressed by X, Y and Z and can have property color expressed by RGB. There are two versions of the Ply file format, one in ASCII, the other in binary The PLY format is NOT intended to be a general scene description language, a shading language or a catch-all modeling format. This means that it includes no transformation matrices, object instantiation, modeling hierarchies, or object sub-parts. A typical PLY object definition is simply a list of (x,y,z) triples for vertices and a list of faces that are described by indices into the list of vertices. This is the structure of a typical PLY file:
Vertex List
Face List
(lists of other elements)
A header describes the elements of the object. It begins always with the word ”PLY” and the second line tells whether the file is binary or ASCII. Then in the header, the file describes each element of the object and the properties of this element. For example, to include the vertices element we begin with element name with how many such elements are in the object after that we include a list of the various properties associated with the element. The header ends with ”end header”. After the header, we include a list of elements for each element type, presented in the order described in the header. Usually, the vertex element list comes after the header. Every line in this list describes a vertex with its property. The vertices are indexed according to the order they appear in the list. The face element list comes usually after the vertex element list. Every line in the face element list describes a face and it begins with the number of vertices of the faces. Then, the indices to the vertices appear. If one wants to write a comment in the header , one should write the word ”comment” at the start of a line . Everything from there until the end of the line should then be ignored. To see how a PLY file, we look at the following figure
To show the object described by the PLY file, we use Meshlab , which is an open source system for processing and editing 3D triangular meshes. For coloring a mesh, there are many options. One of these (which we use) is to color a mesh by its vertices. A face in the mesh gets its color by linear interpolation between the vertices. So if we open the last PLY file by Meshlab, we get the following result

Implementation of ProcessLowerStar

The input of the algorithm is a simplicial complex and a scalar value defined on the vertices fo the simplicial complex. The simplicial complex is defined in PLY by vertices and faces, where the vertices are 0-simplices, faces 2-simplices and the 1-simplices are the edges of the faces. The scalar values are the color of the vertices. We convert the RGB value to grayscale value by this formula grayscale = 0.2989 ∗ R + 0.5870 ∗ G + 0.1140 ∗ B . The algorithm should iterate over every vertex and find the lower star set and then add cells to discrete vector field or critical cells. Our implementation differs slightly from the algorithm by finding first the lower star for every vertex and then build discrete vector field or critical cells. That is because of the nature of the PLY file: as we see in the previous section all vertices are defined first in the file and then the faces, so it is not possible to know to which face every vertex belong to until the last face. The modification does not affect the results as the order of processing lower star is irrelevant. To build the lower star set, we first read the vertices and find the RGB values for every vertex. Then we convert the RGB to grayscale by the previous formula . Then we store the grayscale value in dictionary for every vertex. We name every vertex with its index in PLY file. After reading the vertices, we read the faces. Here, we build the lower star for the vertex. Since the faces in PLY file defined by their vertices defined by the indices (We store the indices and the values in dictionary), we find the value for every vertex and for the vertex with the maximal value we store in the dictionary the faces and the the edges. After reading all vertices and faces, our dictionary will contain the lower star set for every vertex. The Algorithm return of a list of critical cells and a dictionary of discrete vector field, where the keys of the dictionary are the tail of arrows and the values of the dictionary are the head of arrows. We use the output to show the critical cells. We write a new PLY file of our object with critical cells marked. If a 0-simplex is critical(meaning it is a minimum), we give it a red color. If an edge is critical (meaning it is a saddle ), we give its two vertices a green color. If a triangle is critical (meaning it is a maximum), we give its 3 vertices a blue color. If a vertex happens to be a minimum and element from a saddle we give it a yellow color. The next table cover the color meaning for a vertex.
Red Minimum
Green Saddle
Blue Maximum
Yellow Minimum and Saddle
Magenta Minimum and Maximum
Cyan Saddle and Maximum
Violet minimum, saddle and maximum