-
-
Notifications
You must be signed in to change notification settings - Fork 7.5k
/
_tritools.py
263 lines (228 loc) · 10.3 KB
/
_tritools.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
"""
Tools for triangular grids.
"""
import numpy as np
from matplotlib import _api
from matplotlib.tri import Triangulation
class TriAnalyzer:
"""
Define basic tools for triangular mesh analysis and improvement.
A TriAnalyzer encapsulates a `.Triangulation` object and provides basic
tools for mesh analysis and mesh improvement.
Attributes
----------
scale_factors
Parameters
----------
triangulation : `~matplotlib.tri.Triangulation`
The encapsulated triangulation to analyze.
"""
def __init__(self, triangulation):
_api.check_isinstance(Triangulation, triangulation=triangulation)
self._triangulation = triangulation
@property
def scale_factors(self):
"""
Factors to rescale the triangulation into a unit square.
Returns
-------
(float, float)
Scaling factors (kx, ky) so that the triangulation
``[triangulation.x * kx, triangulation.y * ky]``
fits exactly inside a unit square.
"""
compressed_triangles = self._triangulation.get_masked_triangles()
node_used = (np.bincount(np.ravel(compressed_triangles),
minlength=self._triangulation.x.size) != 0)
return (1 / np.ptp(self._triangulation.x[node_used]),
1 / np.ptp(self._triangulation.y[node_used]))
def circle_ratios(self, rescale=True):
"""
Return a measure of the triangulation triangles flatness.
The ratio of the incircle radius over the circumcircle radius is a
widely used indicator of a triangle flatness.
It is always ``<= 0.5`` and ``== 0.5`` only for equilateral
triangles. Circle ratios below 0.01 denote very flat triangles.
To avoid unduly low values due to a difference of scale between the 2
axis, the triangular mesh can first be rescaled to fit inside a unit
square with `scale_factors` (Only if *rescale* is True, which is
its default value).
Parameters
----------
rescale : bool, default: True
If True, internally rescale (based on `scale_factors`), so that the
(unmasked) triangles fit exactly inside a unit square mesh.
Returns
-------
masked array
Ratio of the incircle radius over the circumcircle radius, for
each 'rescaled' triangle of the encapsulated triangulation.
Values corresponding to masked triangles are masked out.
"""
# Coords rescaling
if rescale:
(kx, ky) = self.scale_factors
else:
(kx, ky) = (1.0, 1.0)
pts = np.vstack([self._triangulation.x*kx,
self._triangulation.y*ky]).T
tri_pts = pts[self._triangulation.triangles]
# Computes the 3 side lengths
a = tri_pts[:, 1, :] - tri_pts[:, 0, :]
b = tri_pts[:, 2, :] - tri_pts[:, 1, :]
c = tri_pts[:, 0, :] - tri_pts[:, 2, :]
a = np.hypot(a[:, 0], a[:, 1])
b = np.hypot(b[:, 0], b[:, 1])
c = np.hypot(c[:, 0], c[:, 1])
# circumcircle and incircle radii
s = (a+b+c)*0.5
prod = s*(a+b-s)*(a+c-s)*(b+c-s)
# We have to deal with flat triangles with infinite circum_radius
bool_flat = (prod == 0.)
if np.any(bool_flat):
# Pathologic flow
ntri = tri_pts.shape[0]
circum_radius = np.empty(ntri, dtype=np.float64)
circum_radius[bool_flat] = np.inf
abc = a*b*c
circum_radius[~bool_flat] = abc[~bool_flat] / (
4.0*np.sqrt(prod[~bool_flat]))
else:
# Normal optimized flow
circum_radius = (a*b*c) / (4.0*np.sqrt(prod))
in_radius = (a*b*c) / (4.0*circum_radius*s)
circle_ratio = in_radius/circum_radius
mask = self._triangulation.mask
if mask is None:
return circle_ratio
else:
return np.ma.array(circle_ratio, mask=mask)
def get_flat_tri_mask(self, min_circle_ratio=0.01, rescale=True):
"""
Eliminate excessively flat border triangles from the triangulation.
Returns a mask *new_mask* which allows to clean the encapsulated
triangulation from its border-located flat triangles
(according to their :meth:`circle_ratios`).
This mask is meant to be subsequently applied to the triangulation
using `.Triangulation.set_mask`.
*new_mask* is an extension of the initial triangulation mask
in the sense that an initially masked triangle will remain masked.
The *new_mask* array is computed recursively; at each step flat
triangles are removed only if they share a side with the current mesh
border. Thus, no new holes in the triangulated domain will be created.
Parameters
----------
min_circle_ratio : float, default: 0.01
Border triangles with incircle/circumcircle radii ratio r/R will
be removed if r/R < *min_circle_ratio*.
rescale : bool, default: True
If True, first, internally rescale (based on `scale_factors`) so
that the (unmasked) triangles fit exactly inside a unit square
mesh. This rescaling accounts for the difference of scale which
might exist between the 2 axis.
Returns
-------
array of bool
Mask to apply to encapsulated triangulation.
All the initially masked triangles remain masked in the
*new_mask*.
Notes
-----
The rationale behind this function is that a Delaunay
triangulation - of an unstructured set of points - sometimes contains
almost flat triangles at its border, leading to artifacts in plots
(especially for high-resolution contouring).
Masked with computed *new_mask*, the encapsulated
triangulation would contain no more unmasked border triangles
with a circle ratio below *min_circle_ratio*, thus improving the
mesh quality for subsequent plots or interpolation.
"""
# Recursively computes the mask_current_borders, true if a triangle is
# at the border of the mesh OR touching the border through a chain of
# invalid aspect ratio masked_triangles.
ntri = self._triangulation.triangles.shape[0]
mask_bad_ratio = self.circle_ratios(rescale) < min_circle_ratio
current_mask = self._triangulation.mask
if current_mask is None:
current_mask = np.zeros(ntri, dtype=bool)
valid_neighbors = np.copy(self._triangulation.neighbors)
renum_neighbors = np.arange(ntri, dtype=np.int32)
nadd = -1
while nadd != 0:
# The active wavefront is the triangles from the border (unmasked
# but with a least 1 neighbor equal to -1
wavefront = (np.min(valid_neighbors, axis=1) == -1) & ~current_mask
# The element from the active wavefront will be masked if their
# circle ratio is bad.
added_mask = wavefront & mask_bad_ratio
current_mask = added_mask | current_mask
nadd = np.sum(added_mask)
# now we have to update the tables valid_neighbors
valid_neighbors[added_mask, :] = -1
renum_neighbors[added_mask] = -1
valid_neighbors = np.where(valid_neighbors == -1, -1,
renum_neighbors[valid_neighbors])
return np.ma.filled(current_mask, True)
def _get_compressed_triangulation(self):
"""
Compress (if masked) the encapsulated triangulation.
Returns minimal-length triangles array (*compressed_triangles*) and
coordinates arrays (*compressed_x*, *compressed_y*) that can still
describe the unmasked triangles of the encapsulated triangulation.
Returns
-------
compressed_triangles : array-like
the returned compressed triangulation triangles
compressed_x : array-like
the returned compressed triangulation 1st coordinate
compressed_y : array-like
the returned compressed triangulation 2nd coordinate
tri_renum : int array
renumbering table to translate the triangle numbers from the
encapsulated triangulation into the new (compressed) renumbering.
-1 for masked triangles (deleted from *compressed_triangles*).
node_renum : int array
renumbering table to translate the point numbers from the
encapsulated triangulation into the new (compressed) renumbering.
-1 for unused points (i.e. those deleted from *compressed_x* and
*compressed_y*).
"""
# Valid triangles and renumbering
tri_mask = self._triangulation.mask
compressed_triangles = self._triangulation.get_masked_triangles()
ntri = self._triangulation.triangles.shape[0]
if tri_mask is not None:
tri_renum = self._total_to_compress_renum(~tri_mask)
else:
tri_renum = np.arange(ntri, dtype=np.int32)
# Valid nodes and renumbering
valid_node = (np.bincount(np.ravel(compressed_triangles),
minlength=self._triangulation.x.size) != 0)
compressed_x = self._triangulation.x[valid_node]
compressed_y = self._triangulation.y[valid_node]
node_renum = self._total_to_compress_renum(valid_node)
# Now renumbering the valid triangles nodes
compressed_triangles = node_renum[compressed_triangles]
return (compressed_triangles, compressed_x, compressed_y, tri_renum,
node_renum)
@staticmethod
def _total_to_compress_renum(valid):
"""
Parameters
----------
valid : 1D bool array
Validity mask.
Returns
-------
int array
Array so that (`valid_array` being a compressed array
based on a `masked_array` with mask ~*valid*):
- For all i with valid[i] = True:
valid_array[renum[i]] = masked_array[i]
- For all i with valid[i] = False:
renum[i] = -1 (invalid value)
"""
renum = np.full(np.size(valid), -1, dtype=np.int32)
n_valid = np.sum(valid)
renum[valid] = np.arange(n_valid, dtype=np.int32)
return renum