[2021] Imperial College London - Principles of Programming - Q2 Mesh Partitioning
Question 2 Mesh partitioning
Simulations of fluids and solids are often conducted by discretising the domain of interest into a mesh of triangles. Each triangle has three vertices, and each vertex is usually a part of several triangles so that the mesh joins up. For example, the following is a mesh of the Great Lakes on the border between the US and Canada.
We can immediately see from this figure that this mesh is not connected: there are three distinct regions that are not linked. The objective in this question is to write a class which detects the disconnected parts of a mesh.
For the purposes of this exercise, a mesh is a set of v vertices and c triangles. The vertices are represented by an v x 2 array of floats containing the vertex locations: each row of this array is the 2-dimensional coordinates of a single vertex. The triangles are represented by a c x 3 array of ints representing the indices in the vertex list of the vertices making up each triangle. So if row 42 of the triangle array comprises 24, 0, 1004 then this means that triangle 42 is made up of vertices 24, 0, and 1004. One vertex may form part of several triangles, and this is how the mesh connects.
2 (a) (2 marks)
In the mesh_tools package, create a module mesh_tools.py containing a class Mesh. The constructor of this mesh should take two arguments points and triangles and should store them as attributes with the same names.
2 (b)
(i) (4 marks)
Create a class mesh_tools.mesh_tools.Adjacency. The constructor of this class should take a Mesh as input. The role of Adjacency is to record which vertices are adjacent. Two vertices are adjacent if they are both in the same triangle for some triangle in the mesh.
In the Adjacency constructor, store a sequence of v sets: one set per vertex. The i-th set in this sequence should contain the indices (numbers) of the vertices adjacent to the i-th vertex.
(ii) (2 marks)
Implement the __getitem__() special method on Adjacency, so that if a is an Adjacency then a[i] returns the set of vertices adjacent to the i-th vertex.
2 (c) (8 marks)
Implement a Mesh.partition() method which takes no arguments other than the object itself, and returns a v-long sequence of integers. That is, one number for each vertex in the mesh. If vertices i and j are in the same connected region of the mesh, they should have the same number. If they are in different connected regions they should have different numbers.
The implementation of this exercise is largely an exercise in set operations. The algorithm is as follows:
At the start, all vertices are in a set of unvisited vertices. There is also a set of vertices to visit next, which is empty.
While we still have unvisited vertices:
Move to the next connected region.
Move an arbitrary vertex from the unvisited set to the to-visit set.
While there are nodes in the to-visit set:
Take an arbitrary point p from the to-visit set.
Set the p-th entry of the output to the current connected region.
Add all neighbours of p that are unvisited to the to-visit set.
Remove all neighbours of p from the unvisited list.
A correct solution will have algorithmic complexity that is linear in c, the number of triangles in the mesh.
In addition to the tests, a plotting script is provided for you to check your work. Running the following code:
$ python plot_partition.py
should produce a figure similar to the following. Note that the colours may be different depending on which number your algorithm gave to each lake. Note also that if you have your editor in full screen mode, the figure may appear on another workspace.
2 (d)
(i) (2 marks)
Ensure that your code passes Flake8.
(ii) (2 marks)
Ensure that your code otherwise conforms to good programming style as we have learned in this course.
There is no need to write any docstrings in this exam.
Get the Solution to This Question
WeChat (微信)
WhatsApp
