| 1 | """Classes implementing general 2D geometrical mesh of triangles. |
|---|
| 2 | |
|---|
| 3 | Ole Nielsen, Stephen Roberts, Duncan Gray, Christopher Zoppou |
|---|
| 4 | Geoscience Australia, 2004 |
|---|
| 5 | """ |
|---|
| 6 | |
|---|
| 7 | from general_mesh import General_Mesh |
|---|
| 8 | |
|---|
| 9 | class Mesh(General_Mesh): |
|---|
| 10 | """Collection of triangular elements (purely geometric) |
|---|
| 11 | |
|---|
| 12 | A triangular element is defined in terms of three vertex ids, |
|---|
| 13 | ordered counter clock-wise, |
|---|
| 14 | each corresponding to a given coordinate set. |
|---|
| 15 | Vertices from different elements can point to the same |
|---|
| 16 | coordinate set. |
|---|
| 17 | |
|---|
| 18 | Coordinate sets are implemented as an N x 2 Numeric array containing |
|---|
| 19 | x and y coordinates. |
|---|
| 20 | |
|---|
| 21 | |
|---|
| 22 | To instantiate: |
|---|
| 23 | Mesh(coordinates, triangles) |
|---|
| 24 | |
|---|
| 25 | where |
|---|
| 26 | |
|---|
| 27 | coordinates is either a list of 2-tuples or an Mx2 Numeric array of |
|---|
| 28 | floats representing all x, y coordinates in the mesh. |
|---|
| 29 | |
|---|
| 30 | triangles is either a list of 3-tuples or an Nx3 Numeric array of |
|---|
| 31 | integers representing indices of all vertices in the mesh. |
|---|
| 32 | Each vertex is identified by its index i in [0, M-1]. |
|---|
| 33 | |
|---|
| 34 | |
|---|
| 35 | Example: |
|---|
| 36 | a = [0.0, 0.0] |
|---|
| 37 | b = [0.0, 2.0] |
|---|
| 38 | c = [2.0,0.0] |
|---|
| 39 | e = [2.0, 2.0] |
|---|
| 40 | |
|---|
| 41 | points = [a, b, c, e] |
|---|
| 42 | triangles = [ [1,0,2], [1,2,3] ] #bac, bce |
|---|
| 43 | mesh = Mesh(points, triangles) |
|---|
| 44 | |
|---|
| 45 | #creates two triangles: bac and bce |
|---|
| 46 | |
|---|
| 47 | |
|---|
| 48 | Mesh takes the optional third argument boundary which is a |
|---|
| 49 | dictionary mapping from (element_id, edge_id) to boundary tag. |
|---|
| 50 | The default value is None which will assign the defualt_boundary_tag |
|---|
| 51 | as specified in config.py to all boundary edges. |
|---|
| 52 | """ |
|---|
| 53 | |
|---|
| 54 | #FIXME: Maybe rename coordinates to points (as in a poly file) |
|---|
| 55 | #But keep 'vertex_coordinates' |
|---|
| 56 | |
|---|
| 57 | #FIXME: Put in check for angles less than a set minimum |
|---|
| 58 | |
|---|
| 59 | def __init__(self, coordinates, triangles, boundary = None): |
|---|
| 60 | """ |
|---|
| 61 | Build triangles from x,y coordinates (sequence of 2-tuples or |
|---|
| 62 | Mx2 Numeric array of floats) and triangles (sequence of 3-tuples |
|---|
| 63 | or Nx3 Numeric array of non-negative integers). |
|---|
| 64 | """ |
|---|
| 65 | |
|---|
| 66 | from Numeric import array, zeros, Int, Float, maximum, sqrt, sum |
|---|
| 67 | |
|---|
| 68 | General_Mesh.__init__(self,coordinates, triangles) |
|---|
| 69 | |
|---|
| 70 | N = self.number_of_elements |
|---|
| 71 | |
|---|
| 72 | #Allocate space for geometric quantities |
|---|
| 73 | self.centroid_coordinates = zeros((N, 2), Float) |
|---|
| 74 | |
|---|
| 75 | self.radii = zeros(N, Float) |
|---|
| 76 | |
|---|
| 77 | self.neighbours = zeros((N, 3), Int) |
|---|
| 78 | self.neighbour_edges = zeros((N, 3), Int) |
|---|
| 79 | self.number_of_boundaries = zeros(N, Int) |
|---|
| 80 | self.surrogate_neighbours = zeros((N, 3), Int) |
|---|
| 81 | |
|---|
| 82 | #Get x,y coordinates for all triangles and store |
|---|
| 83 | V = self.vertex_coordinates |
|---|
| 84 | |
|---|
| 85 | #Initialise each triangle |
|---|
| 86 | for i in range(N): |
|---|
| 87 | #if i % (N/10) == 0: print '(%d/%d)' %(i, N) |
|---|
| 88 | |
|---|
| 89 | x0 = V[i, 0]; y0 = V[i, 1] |
|---|
| 90 | x1 = V[i, 2]; y1 = V[i, 3] |
|---|
| 91 | x2 = V[i, 4]; y2 = V[i, 5] |
|---|
| 92 | |
|---|
| 93 | #Compute centroid |
|---|
| 94 | centroid = array([(x0 + x1 + x2)/3, (y0 + y1 + y2)/3]) |
|---|
| 95 | self.centroid_coordinates[i] = centroid |
|---|
| 96 | |
|---|
| 97 | #Midpoints |
|---|
| 98 | m0 = array([(x1 + x2)/2, (y1 + y2)/2]) |
|---|
| 99 | m1 = array([(x0 + x2)/2, (y0 + y2)/2]) |
|---|
| 100 | m2 = array([(x1 + x0)/2, (y1 + y0)/2]) |
|---|
| 101 | |
|---|
| 102 | #The radius is the distance from the centroid of |
|---|
| 103 | #a triangle to the midpoint of the side of the triangle |
|---|
| 104 | #closest to the centroid |
|---|
| 105 | d0 = sqrt(sum( (centroid-m0)**2 )) |
|---|
| 106 | d1 = sqrt(sum( (centroid-m1)**2 )) |
|---|
| 107 | d2 = sqrt(sum( (centroid-m2)**2 )) |
|---|
| 108 | |
|---|
| 109 | self.radii[i] = min(d0, d1, d2) |
|---|
| 110 | |
|---|
| 111 | #Initialise Neighbours (-1 means that it is a boundary neighbour) |
|---|
| 112 | self.neighbours[i, :] = [-1, -1, -1] |
|---|
| 113 | |
|---|
| 114 | #Initialise edge ids of neighbours |
|---|
| 115 | #In case of boundaries this slot is not used |
|---|
| 116 | self.neighbour_edges[i, :] = [-1, -1, -1] |
|---|
| 117 | |
|---|
| 118 | |
|---|
| 119 | #Build neighbour structure |
|---|
| 120 | self.build_neighbour_structure() |
|---|
| 121 | |
|---|
| 122 | #Build vertex list |
|---|
| 123 | self.build_vertexlist() |
|---|
| 124 | |
|---|
| 125 | #Build surrogate neighbour structure |
|---|
| 126 | self.build_surrogate_neighbour_structure() |
|---|
| 127 | |
|---|
| 128 | #Build boundary dictionary mapping (id, edge) to symbolic tags |
|---|
| 129 | self.build_boundary_dictionary(boundary) |
|---|
| 130 | |
|---|
| 131 | #Update boundary indices |
|---|
| 132 | self.build_boundary_structure() |
|---|
| 133 | |
|---|
| 134 | |
|---|
| 135 | def __repr__(self): |
|---|
| 136 | return 'Mesh: %d triangles, %d elements, %d boundary segments'\ |
|---|
| 137 | %(self.coordinates.shape[0], len(self), len(self.boundary)) |
|---|
| 138 | |
|---|
| 139 | |
|---|
| 140 | def build_neighbour_structure(self): |
|---|
| 141 | """Update all registered triangles to point to their neighbours. |
|---|
| 142 | |
|---|
| 143 | Also, keep a tally of the number of boundaries for each triangle |
|---|
| 144 | |
|---|
| 145 | Postconditions: |
|---|
| 146 | neighbours and neighbour_edges is populated |
|---|
| 147 | number_of_boundaries integer array is defined. |
|---|
| 148 | """ |
|---|
| 149 | |
|---|
| 150 | #Step 1: |
|---|
| 151 | #Build dictionary mapping from segments (2-tuple of points) |
|---|
| 152 | #to left hand side edge (facing neighbouring triangle) |
|---|
| 153 | |
|---|
| 154 | N = self.number_of_elements |
|---|
| 155 | neighbourdict = {} |
|---|
| 156 | for i in range(N): |
|---|
| 157 | |
|---|
| 158 | #Register all segments as keys mapping to current triangle |
|---|
| 159 | #and segment id |
|---|
| 160 | a = self.triangles[i, 0] |
|---|
| 161 | b = self.triangles[i, 1] |
|---|
| 162 | c = self.triangles[i, 2] |
|---|
| 163 | neighbourdict[a,b] = (i, 2) #(id, edge) |
|---|
| 164 | neighbourdict[b,c] = (i, 0) #(id, edge) |
|---|
| 165 | neighbourdict[c,a] = (i, 1) #(id, edge) |
|---|
| 166 | |
|---|
| 167 | |
|---|
| 168 | #Step 2: |
|---|
| 169 | #Go through triangles again, but this time |
|---|
| 170 | #reverse direction of segments and lookup neighbours. |
|---|
| 171 | for i in range(N): |
|---|
| 172 | a = self.triangles[i, 0] |
|---|
| 173 | b = self.triangles[i, 1] |
|---|
| 174 | c = self.triangles[i, 2] |
|---|
| 175 | |
|---|
| 176 | self.number_of_boundaries[i] = 3 |
|---|
| 177 | if neighbourdict.has_key((b,a)): |
|---|
| 178 | self.neighbours[i, 2] = neighbourdict[b,a][0] |
|---|
| 179 | self.neighbour_edges[i, 2] = neighbourdict[b,a][1] |
|---|
| 180 | self.number_of_boundaries[i] -= 1 |
|---|
| 181 | |
|---|
| 182 | if neighbourdict.has_key((c,b)): |
|---|
| 183 | self.neighbours[i, 0] = neighbourdict[c,b][0] |
|---|
| 184 | self.neighbour_edges[i, 0] = neighbourdict[c,b][1] |
|---|
| 185 | self.number_of_boundaries[i] -= 1 |
|---|
| 186 | |
|---|
| 187 | if neighbourdict.has_key((a,c)): |
|---|
| 188 | self.neighbours[i, 1] = neighbourdict[a,c][0] |
|---|
| 189 | self.neighbour_edges[i, 1] = neighbourdict[a,c][1] |
|---|
| 190 | self.number_of_boundaries[i] -= 1 |
|---|
| 191 | |
|---|
| 192 | |
|---|
| 193 | |
|---|
| 194 | def build_vertexlist(self): |
|---|
| 195 | """Build vertexlist index by vertex ids and for each entry (point id) |
|---|
| 196 | build a list of (triangles, vertex_id) pairs that use the point |
|---|
| 197 | as vertex. |
|---|
| 198 | |
|---|
| 199 | Preconditions: |
|---|
| 200 | self.coordinates and self.triangles are defined |
|---|
| 201 | |
|---|
| 202 | Postcondition: |
|---|
| 203 | self.vertexlist is build |
|---|
| 204 | """ |
|---|
| 205 | |
|---|
| 206 | vertexlist = [None]*len(self.coordinates) |
|---|
| 207 | for i in range(self.number_of_elements): |
|---|
| 208 | |
|---|
| 209 | a = self.triangles[i, 0] |
|---|
| 210 | b = self.triangles[i, 1] |
|---|
| 211 | c = self.triangles[i, 2] |
|---|
| 212 | |
|---|
| 213 | #Register the vertices v as lists of |
|---|
| 214 | #(triangle_id, vertex_id) tuples associated with them |
|---|
| 215 | #This is used for smoothing |
|---|
| 216 | for vertex_id, v in enumerate([a,b,c]): |
|---|
| 217 | if vertexlist[v] is None: |
|---|
| 218 | vertexlist[v] = [] |
|---|
| 219 | |
|---|
| 220 | vertexlist[v].append( (i, vertex_id) ) |
|---|
| 221 | |
|---|
| 222 | self.vertexlist = vertexlist |
|---|
| 223 | |
|---|
| 224 | |
|---|
| 225 | def build_surrogate_neighbour_structure(self): |
|---|
| 226 | """Build structure where each triangle edge points to its neighbours |
|---|
| 227 | if they exist. Otherwise point to the triangle itself. |
|---|
| 228 | |
|---|
| 229 | The surrogate neighbour structure is useful for computing gradients |
|---|
| 230 | based on centroid values of neighbours. |
|---|
| 231 | |
|---|
| 232 | Precondition: Neighbour structure is defined |
|---|
| 233 | Postcondition: |
|---|
| 234 | Surrogate neighbour structure is defined: |
|---|
| 235 | surrogate_neighbours: i0, i1, i2 where all i_k >= 0 point to |
|---|
| 236 | triangles. |
|---|
| 237 | |
|---|
| 238 | """ |
|---|
| 239 | |
|---|
| 240 | N = self.number_of_elements |
|---|
| 241 | for i in range(N): |
|---|
| 242 | #Find all neighbouring volumes that are not boundaries |
|---|
| 243 | for k in range(3): |
|---|
| 244 | if self.neighbours[i, k] < 0: |
|---|
| 245 | self.surrogate_neighbours[i, k] = i #Point this triangle |
|---|
| 246 | else: |
|---|
| 247 | self.surrogate_neighbours[i, k] = self.neighbours[i, k] |
|---|
| 248 | |
|---|
| 249 | |
|---|
| 250 | |
|---|
| 251 | def build_boundary_dictionary(self, boundary = None): |
|---|
| 252 | """Build or check the dictionary of boundary tags. |
|---|
| 253 | self.boundary is a dictionary of tags, |
|---|
| 254 | keyed by volume id and edge: |
|---|
| 255 | { (id, edge): tag, ... } |
|---|
| 256 | |
|---|
| 257 | Postconditions: |
|---|
| 258 | self.boundary is defined. |
|---|
| 259 | """ |
|---|
| 260 | |
|---|
| 261 | from config import default_boundary_tag |
|---|
| 262 | |
|---|
| 263 | if boundary is None: |
|---|
| 264 | boundary = {} |
|---|
| 265 | for vol_id in range(self.number_of_elements): |
|---|
| 266 | for edge_id in range(0, 3): |
|---|
| 267 | if self.neighbours[vol_id, edge_id] < 0: |
|---|
| 268 | boundary[(vol_id, edge_id)] = default_boundary_tag |
|---|
| 269 | else: |
|---|
| 270 | #Check that all keys in given boundary exist |
|---|
| 271 | for vol_id, edge_id in boundary.keys(): |
|---|
| 272 | msg = 'Segment (%d, %d) does not exist' %(vol_id, edge_id) |
|---|
| 273 | a, b = self.neighbours.shape |
|---|
| 274 | assert vol_id < a and edge_id < b, msg |
|---|
| 275 | |
|---|
| 276 | msg = 'Segment (%d, %d) is not a boundary' %(vol_id, edge_id) |
|---|
| 277 | assert self.neighbours[vol_id, edge_id] < 0, msg |
|---|
| 278 | |
|---|
| 279 | #Check that all boundary segments are assigned a value |
|---|
| 280 | for vol_id in range(self.number_of_elements): |
|---|
| 281 | for edge_id in range(0, 3): |
|---|
| 282 | if self.neighbours[vol_id, edge_id] < 0: |
|---|
| 283 | if not boundary.has_key( (vol_id, edge_id) ): |
|---|
| 284 | msg = 'WARNING: Given boundary does not contain ' |
|---|
| 285 | msg += 'tags for edge (%d, %d). '\ |
|---|
| 286 | %(vol_id, edge_id) |
|---|
| 287 | msg += 'Assigning default tag (%s).'\ |
|---|
| 288 | %default_boundary_tag |
|---|
| 289 | |
|---|
| 290 | #FIXME: Print only as per verbosity |
|---|
| 291 | #print msg |
|---|
| 292 | boundary[ (vol_id, edge_id) ] =\ |
|---|
| 293 | default_boundary_tag |
|---|
| 294 | |
|---|
| 295 | |
|---|
| 296 | |
|---|
| 297 | self.boundary = boundary |
|---|
| 298 | |
|---|
| 299 | |
|---|
| 300 | def build_boundary_structure(self): |
|---|
| 301 | """Traverse boundary and |
|---|
| 302 | enumerate neighbour indices from -1 and |
|---|
| 303 | counting down. |
|---|
| 304 | |
|---|
| 305 | Precondition: |
|---|
| 306 | self.boundary is defined. |
|---|
| 307 | Post condition: |
|---|
| 308 | neighbour array has unique negative indices for boundary |
|---|
| 309 | boundary_segments array imposes an ordering on segments |
|---|
| 310 | (not otherwise available from the dictionary) |
|---|
| 311 | """ |
|---|
| 312 | |
|---|
| 313 | if self.boundary is None: |
|---|
| 314 | msg = 'Boundary dictionary must be defined before ' |
|---|
| 315 | msg += 'building boundary structure' |
|---|
| 316 | raise msg |
|---|
| 317 | |
|---|
| 318 | |
|---|
| 319 | self.boundary_segments = self.boundary.keys() |
|---|
| 320 | self.boundary_segments.sort() |
|---|
| 321 | |
|---|
| 322 | index = -1 |
|---|
| 323 | for id, edge in self.boundary_segments: |
|---|
| 324 | self.neighbours[id, edge] = index |
|---|
| 325 | index -= 1 |
|---|
| 326 | |
|---|
| 327 | |
|---|
| 328 | def get_boundary_tags(self): |
|---|
| 329 | """Return list of available boundary tags |
|---|
| 330 | """ |
|---|
| 331 | |
|---|
| 332 | tags = {} |
|---|
| 333 | for v in self.boundary.values(): |
|---|
| 334 | tags[v] = 1 |
|---|
| 335 | |
|---|
| 336 | return tags.keys() |
|---|
| 337 | |
|---|
| 338 | |
|---|
| 339 | |
|---|
| 340 | def check_integrity(self): |
|---|
| 341 | """Check that triangles are internally consistent e.g. |
|---|
| 342 | that area corresponds to edgelengths, that vertices |
|---|
| 343 | are arranged in a counter-clockwise order, etc etc |
|---|
| 344 | Neighbour structure will be checked by class Mesh |
|---|
| 345 | """ |
|---|
| 346 | |
|---|
| 347 | from config import epsilon |
|---|
| 348 | from math import pi |
|---|
| 349 | from util import anglediff |
|---|
| 350 | |
|---|
| 351 | N = self.number_of_elements |
|---|
| 352 | |
|---|
| 353 | #Get x,y coordinates for all vertices for all triangles |
|---|
| 354 | V = self.get_vertex_coordinates() |
|---|
| 355 | |
|---|
| 356 | #Check each triangle |
|---|
| 357 | for i in range(N): |
|---|
| 358 | x0 = V[i, 0]; y0 = V[i, 1] |
|---|
| 359 | x1 = V[i, 2]; y1 = V[i, 3] |
|---|
| 360 | x2 = V[i, 4]; y2 = V[i, 5] |
|---|
| 361 | |
|---|
| 362 | #Check that area hasn't been compromised |
|---|
| 363 | area = self.areas[i] |
|---|
| 364 | ref = abs((x1*y0-x0*y1)+(x2*y1-x1*y2)+(x0*y2-x2*y0))/2 |
|---|
| 365 | msg = 'Wrong area for vertex coordinates: %f %f %f %f %f %f'\ |
|---|
| 366 | %(x0,y0,x1,y1,x2,y2) |
|---|
| 367 | assert abs((area - ref)/area) < epsilon, msg |
|---|
| 368 | |
|---|
| 369 | #Check that points are arranged in counter clock-wise order |
|---|
| 370 | v0 = [x1-x0, y1-y0] |
|---|
| 371 | v1 = [x2-x1, y2-y1] |
|---|
| 372 | v2 = [x0-x2, y0-y2] |
|---|
| 373 | |
|---|
| 374 | a0 = anglediff(v1, v0) |
|---|
| 375 | a1 = anglediff(v2, v1) |
|---|
| 376 | a2 = anglediff(v0, v2) |
|---|
| 377 | |
|---|
| 378 | msg = '''Vertices (%s,%s), (%s,%s), (%s,%s) are not arranged |
|---|
| 379 | in counter clockwise order''' %(x0, y0, x1, y1, x2, y2) |
|---|
| 380 | assert a0 < pi and a1 < pi and a2 < pi, msg |
|---|
| 381 | |
|---|
| 382 | #Check that normals are orthogonal to edge vectors |
|---|
| 383 | #Note that normal[k] lies opposite vertex k |
|---|
| 384 | |
|---|
| 385 | normal0 = self.normals[i, 0:2] |
|---|
| 386 | normal1 = self.normals[i, 2:4] |
|---|
| 387 | normal2 = self.normals[i, 4:6] |
|---|
| 388 | |
|---|
| 389 | for u, v in [ (v0, normal2), (v1, normal0), (v2, normal1) ]: |
|---|
| 390 | assert u[0]*v[0] + u[1]*v[1] < epsilon |
|---|
| 391 | |
|---|
| 392 | |
|---|
| 393 | #Check that all vertices have been registered |
|---|
| 394 | for v in self.vertexlist: |
|---|
| 395 | msg = 'Some points do not belong to an element.\n' |
|---|
| 396 | msg += 'Make sure all points appear as element vertices!' |
|---|
| 397 | if v is None: |
|---|
| 398 | print 'WARNING (mesh.py): %s' %msg |
|---|
| 399 | break |
|---|
| 400 | |
|---|
| 401 | #Should this warning be an exception? |
|---|
| 402 | #assert v is not None, msg |
|---|
| 403 | |
|---|
| 404 | |
|---|
| 405 | #Check integrity of neighbour structure |
|---|
| 406 | for i in range(N): |
|---|
| 407 | for v in self.triangles[i, :]: |
|---|
| 408 | #Check that all vertices have been registered |
|---|
| 409 | assert self.vertexlist[v] is not None |
|---|
| 410 | |
|---|
| 411 | #Check that this triangle is listed with at least one vertex |
|---|
| 412 | assert (i, 0) in self.vertexlist[v] or\ |
|---|
| 413 | (i, 1) in self.vertexlist[v] or\ |
|---|
| 414 | (i, 2) in self.vertexlist[v] |
|---|
| 415 | |
|---|
| 416 | |
|---|
| 417 | |
|---|
| 418 | #Check neighbour structure |
|---|
| 419 | for k, neighbour_id in enumerate(self.neighbours[i,:]): |
|---|
| 420 | |
|---|
| 421 | #Assert that my neighbour's neighbour is me |
|---|
| 422 | #Boundaries need not fulfill this |
|---|
| 423 | if neighbour_id >= 0: |
|---|
| 424 | edge = self.neighbour_edges[i, k] |
|---|
| 425 | assert self.neighbours[neighbour_id, edge] == i |
|---|
| 426 | |
|---|
| 427 | |
|---|
| 428 | |
|---|
| 429 | #Check that all boundaries have |
|---|
| 430 | # unique, consecutive, negative indices |
|---|
| 431 | L = len(self.boundary) |
|---|
| 432 | for i in range(L): |
|---|
| 433 | id, edge = self.boundary_segments[i] |
|---|
| 434 | assert self.neighbours[id, edge] == -i-1 |
|---|
| 435 | |
|---|
| 436 | |
|---|
| 437 | #NOTE: This assert doesn't hold true if there are internal boundaries |
|---|
| 438 | #FIXME: Look into this further. |
|---|
| 439 | #for id, edge in self.boundary: |
|---|
| 440 | # assert self.neighbours[id,edge] < 0 |
|---|
| 441 | |
|---|
| 442 | #FIXME: May get rid of |
|---|
| 443 | def rectangular_mesh(m, n, len1=1.0, len2=1.0, origin = (0.0, 0.0)): |
|---|
| 444 | from mesh_factory import rectangular |
|---|
| 445 | points, triangles, boundary = rectangular(m, n, len1, len2, origin) |
|---|
| 446 | |
|---|
| 447 | return Mesh(points, triangles, boundary) |
|---|
| 448 | |
|---|
| 449 | |
|---|
| 450 | #FIXME: Get oblique and contracting and circular meshes from Chris |
|---|
| 451 | |
|---|
