Coverage for trimesh/grouping.py: 94%
251 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-10-02 20:54 +0000
1"""
2grouping.py
3-------------
5Functions for grouping values and rows.
6"""
8import numpy as np
10from . import util
11from .constants import log, tol
12from .typed import ArrayLike, Integer, NDArray, Number, Sequence
14try:
15 from scipy.spatial import cKDTree
16except BaseException as E:
17 # wrapping just ImportError fails in some cases
18 # will raise the error when someone tries to use KDtree
19 from . import exceptions
21 cKDTree = exceptions.ExceptionWrapper(E)
24def merge_vertices(
25 mesh,
26 merge_tex: bool | None = None,
27 merge_norm: bool | None = None,
28 digits_vertex: Integer | None = None,
29 digits_norm: Integer | None = None,
30 digits_uv: Integer | None = None,
31):
32 """
33 Removes duplicate vertices, grouped by position and
34 optionally texture coordinate and normal.
36 Parameters
37 -------------
38 mesh : Trimesh object
39 Mesh to merge vertices on
40 merge_tex : bool
41 If True textured meshes with UV coordinates will
42 have vertices merged regardless of UV coordinates
43 merge_norm : bool
44 If True, meshes with vertex normals will have
45 vertices merged ignoring different normals
46 digits_vertex : None or int
47 Number of digits to consider for vertex position
48 digits_norm : int
49 Number of digits to consider for unit normals
50 digits_uv : int
51 Number of digits to consider for UV coordinates
52 """
53 # no vertices so exit early
54 if len(mesh.vertices) == 0:
55 return
56 if merge_tex is None:
57 merge_tex = False
58 if merge_norm is None:
59 merge_norm = False
60 if digits_norm is None:
61 digits_norm = 2
62 if digits_uv is None:
63 digits_uv = 4
64 if digits_vertex is None:
65 # use tol.merge if digit precision not passed
66 digits_vertex = util.decimal_to_digits(tol.merge)
68 # if we have a ton of unreferenced vertices it will
69 # make the unique_rows call super slow so cull first
70 if hasattr(mesh, "faces") and len(mesh.faces) > 0:
71 referenced = np.zeros(len(mesh.vertices), dtype=bool)
72 referenced[mesh.faces] = True
73 else:
74 # this is used for geometry without faces
75 referenced = np.ones(len(mesh.vertices), dtype=bool)
77 # collect vertex attributes into sequence we can stack
78 stacked = [mesh.vertices * (10**digits_vertex)]
80 # UV texture visuals require us to update the
81 # vertices and normals differently
82 if (
83 not merge_tex
84 and mesh.visual.defined
85 and mesh.visual.kind == "texture"
86 and mesh.visual.uv is not None
87 and len(mesh.visual.uv) == len(mesh.vertices)
88 ):
89 # get an array with vertices and UV coordinates
90 # converted to integers at requested precision
91 stacked.append(mesh.visual.uv * (10**digits_uv))
93 # check to see if we have vertex normals
94 normals = mesh._cache["vertex_normals"]
95 if not merge_norm and np.shape(normals) == mesh.vertices.shape:
96 stacked.append(normals * (10**digits_norm))
98 # stack collected vertex properties and round to integer
99 stacked = np.column_stack(stacked).round().astype(np.int64)
101 # check unique rows of referenced vertices
102 u, i = unique_rows(stacked[referenced], keep_order=True)
104 # construct an inverse using the subset
105 inverse = np.zeros(len(mesh.vertices), dtype=np.int64)
106 inverse[referenced] = i
107 # get the vertex mask
108 mask = np.nonzero(referenced)[0][u]
109 # run the update including normals and UV coordinates
110 mesh.update_vertices(mask=mask, inverse=inverse)
113def group(values, min_len: Integer | None = None, max_len: Integer | None = None):
114 """
115 Return the indices of values that are identical
117 Parameters
118 ----------
119 values : (n,) int
120 Values to group
121 min_len : int
122 The shortest group allowed
123 All groups will have len >= min_length
124 max_len : int
125 The longest group allowed
126 All groups will have len <= max_length
128 Returns
129 ----------
130 groups : sequence
131 Contains indices to form groups
132 IE [0,1,0,1] returns [[0,2], [1,3]]
133 """
134 original = np.asanyarray(values)
136 # save the sorted order and then apply it
137 order = original.argsort()
138 values = original[order]
140 # find the indexes which are duplicates
141 if values.dtype.kind == "f":
142 # for floats in a sorted array, neighbors are not duplicates
143 # if the difference between them is greater than approximate zero
144 nondupe = np.greater(np.abs(np.diff(values)), tol.zero)
145 else:
146 # for ints and strings we can check exact non- equality
147 # for all other types this will only work if they defined
148 # an __eq__
149 nondupe = values[1:] != values[:-1]
151 dupe_idx = np.append(0, np.nonzero(nondupe)[0] + 1)
153 # start with a mask that marks everything as ok
154 dupe_ok = np.ones(len(dupe_idx), dtype=bool)
156 # calculate the length of each group from their index
157 dupe_len = np.diff(np.concatenate((dupe_idx, [len(values)])))
159 # cull by length if requested
160 if min_len is not None or max_len is not None:
161 if min_len is not None:
162 dupe_ok &= dupe_len >= min_len
163 if max_len is not None:
164 dupe_ok &= dupe_len <= max_len
166 groups = [order[i : (i + j)] for i, j in zip(dupe_idx[dupe_ok], dupe_len[dupe_ok])]
167 return groups
170def hashable_rows(
171 data: ArrayLike, digits: Integer | None = None, allow_int: bool = True
172) -> NDArray:
173 """
174 We turn our array into integers based on the precision
175 given by digits and then put them in a hashable format.
177 Parameters
178 ---------
179 data : (n, m) array
180 Input data
181 digits : int or None
182 How many digits to add to hash if data is floating point
183 If None, tol.merge will be used
185 Returns
186 ---------
187 hashable : (n,)
188 May return as a `np.void` or a `np.uint64`
189 """
190 # if there is no data return immediately
191 if len(data) == 0:
192 return np.array([], dtype=np.uint64)
194 # get array as integer to precision we care about
195 as_int = float_to_int(data, digits=digits)
197 # if it is flat integers already return
198 if len(as_int.shape) == 1:
199 return as_int
201 # rows without any columns are all identical: return a constant per row
202 # rather than dividing by the column count below
203 if as_int.shape[1] == 0:
204 return np.zeros(len(as_int), dtype=np.uint64)
206 # if array is 2D and smallish, we can try bitbanging
207 # this is significantly faster than the custom dtype
208 if allow_int and len(as_int.shape) == 2 and as_int.shape[1] <= 4:
209 # can we pack the whole row into a single 64 bit integer
210 precision = int(np.floor(64 / as_int.shape[1]))
212 # get the extreme values of the data set
213 d_min, d_max = as_int.min(), as_int.max()
214 # since we are quantizing the data down we need every value
215 # to fit in a partial integer so we have to check against extrema
216 threshold = (2 ** (precision - 1)) - 1
218 # if the data is within the range of our precision threshold
219 if d_max < threshold and d_min > -threshold:
220 # the resulting package
221 hashable = np.zeros(len(as_int), dtype=np.uint64)
222 # offset to the middle of the unsigned integer range
223 # this array should contain only positive values
224 bitbang = (as_int.T + (threshold + 1)).astype(np.uint64)
225 # loop through each column and bitwise xor to combine
226 # make sure as_int is int64 otherwise bit offset won't work
227 for offset, column in enumerate(bitbang):
228 # will modify hashable in place
229 np.bitwise_xor(hashable, column << (offset * precision), out=hashable)
230 return hashable
232 # reshape array into magical data type that is weird but works with unique
233 dtype = np.dtype((np.void, as_int.dtype.itemsize * as_int.shape[1]))
234 # make sure result is contiguous and flat
235 result = np.ascontiguousarray(as_int).view(dtype).reshape(-1)
236 result.flags["WRITEABLE"] = False
238 return result
241def float_to_int(data, digits: Integer | None = None) -> NDArray[np.int64]:
242 """
243 Given a numpy array of float/bool/int, return as integers.
245 Parameters
246 -------------
247 data : (n, d) float, int, or bool
248 Input data
249 digits : float or int
250 Precision for float conversion
252 Returns
253 -------------
254 as_int : (n, d) int
255 Data as integers
256 """
257 # convert to any numpy array
258 data = np.asanyarray(data)
260 # we can early-exit if we've been passed data that is already
261 # an integer, unsigned integer, boolean, or empty
262 if data.dtype == np.int64:
263 return data
264 elif data.dtype.kind in "iub" or data.size == 0:
265 return data.astype(np.int64)
266 elif data.dtype.kind != "f":
267 # if it's not a floating point try to make it one
268 data = data.astype(np.float64)
270 if digits is None:
271 # get digits from `tol.merge`
272 digits = util.decimal_to_digits(tol.merge)
273 elif not isinstance(digits, (int, np.integer)):
274 raise TypeError(f"Digits must be `None` or `int`, not `{type(digits)}`")
276 # multiply by requested power of ten
277 # then subtract small epsilon to avoid "go either way" rounding
278 # then do the rounding and convert to integer
279 return np.round((data * 10**digits) - 1e-6).astype(np.int64)
282def unique_ordered(
283 data: ArrayLike, return_index: bool = False, return_inverse: bool = False
284):
285 """
286 Returns the same as np.unique, but ordered as per the
287 first occurrence of the unique value in data.
289 Examples
290 ---------
291 In [1]: a = [0, 3, 3, 4, 1, 3, 0, 3, 2, 1]
293 In [2]: np.unique(a)
294 Out[2]: array([0, 1, 2, 3, 4])
296 In [3]: trimesh.grouping.unique_ordered(a)
297 Out[3]: array([0, 3, 4, 1, 2])
298 """
299 # uniques are the values, sorted
300 # index is the value in the original `data`
301 # i.e. `data[index] == unique`
302 # inverse is how to re-construct `data` from `unique`
303 # i.e. `unique[inverse] == data`
304 unique, index, inverse = np.unique(data, return_index=True, return_inverse=True)
306 # we want to maintain the original index order
307 order = index.argsort()
309 if not return_index and not return_inverse:
310 return unique[order]
312 # collect return values
313 # start with the unique values in original order
314 result = [unique[order]]
315 # the new index values
316 if return_index:
317 # re-order the index in the original array
318 result.append(index[order])
319 if return_inverse:
320 # create the new inverse from the order of the order
321 result.append(order.argsort()[inverse])
323 return result
326def unique_bincount(
327 values: ArrayLike,
328 minlength: Integer = 0,
329 return_inverse: bool = False,
330 return_counts: bool = False,
331):
332 """
333 For arrays of integers find unique values using bin counting.
334 Roughly 10x faster for correct input than np.unique
336 Parameters
337 --------------
338 values : (n,) int
339 Values to find unique members of
340 minlength : int
341 Maximum value that will occur in values (values.max())
342 return_inverse : bool
343 If True, return an inverse such that unique[inverse] == values
344 return_counts : bool
345 If True, also return the number of times each
346 unique item appears in values
348 Returns
349 ------------
350 unique : (m,) int
351 Unique values in original array
352 inverse : (n,) int, optional
353 An array such that unique[inverse] == values
354 Only returned if return_inverse is True
355 counts : (m,) int, optional
356 An array holding the counts of each unique item in values
357 Only returned if return_counts is True
358 """
359 values = np.asanyarray(values)
360 if len(values.shape) != 1 or values.dtype.kind != "i":
361 raise ValueError("input must be 1D integers!")
363 try:
364 # count the number of occurrences of each value
365 counts = np.bincount(values, minlength=minlength)
366 except TypeError:
367 # casting failed on 32 bit windows
368 log.warning("casting failed, falling back!")
369 # fall back to numpy unique
370 return np.unique(
371 values, return_inverse=return_inverse, return_counts=return_counts
372 )
374 # which bins are occupied at all
375 # counts are integers so this works
376 unique_bin = counts.astype(bool)
378 # which values are unique
379 # indexes correspond to original values
380 unique = np.where(unique_bin)[0]
381 ret = (unique,)
383 if return_inverse:
384 # find the inverse to reconstruct original
385 inverse = (np.cumsum(unique_bin) - 1)[values]
386 ret += (inverse,)
388 if return_counts:
389 unique_counts = counts[unique]
390 ret += (unique_counts,)
392 if len(ret) == 1:
393 return ret[0]
394 return ret
397def merge_runs(data: ArrayLike, digits: Integer | None = None):
398 """
399 Merge duplicate sequential values. This differs from unique_ordered
400 in that values can occur in multiple places in the sequence, but
401 only consecutive repeats are removed
403 Parameters
404 -----------
405 data: (n,) float or int
407 Returns
408 --------
409 merged: (m,) float or int
411 Examples
412 ---------
413 In [1]: a
414 Out[1]:
415 array([-1, -1, -1, 0, 0, 1, 1, 2, 0,
416 3, 3, 4, 4, 5, 5, 6, 6, 7,
417 7, 8, 8, 9, 9, 9])
419 In [2]: trimesh.grouping.merge_runs(a)
420 Out[2]: array([-1, 0, 1, 2, 0, 3, 4, 5, 6, 7, 8, 9])
421 """
422 if digits is None:
423 epsilon = tol.merge
424 else:
425 epsilon = 10 ** (-digits)
427 data = np.asanyarray(data)
428 mask = np.zeros(len(data), dtype=bool)
429 mask[0] = True
430 mask[1:] = np.abs(data[1:] - data[:-1]) > epsilon
432 return data[mask]
435def unique_float(
436 data,
437 return_index: bool = False,
438 return_inverse: bool = False,
439 digits: Integer | None = None,
440):
441 """
442 Identical to the numpy.unique command, except evaluates floating point
443 numbers, using a specified number of digits.
445 If digits isn't specified, the library default TOL_MERGE will be used.
446 """
447 data = np.asanyarray(data)
448 as_int = float_to_int(data, digits)
449 _junk, unique, inverse = np.unique(as_int, return_index=True, return_inverse=True)
451 if (not return_index) and (not return_inverse):
452 return data[unique]
454 result = [data[unique]]
456 if return_index:
457 result.append(unique)
458 if return_inverse:
459 result.append(inverse)
460 return tuple(result)
463def unique_rows(data, digits=None, keep_order=False):
464 """
465 Returns indices of unique rows. It will return the
466 first occurrence of a row that is duplicated:
467 [[1,2], [3,4], [1,2]] will return [0,1]
469 Parameters
470 ---------
471 data : (n, m) array
472 Floating point data
473 digits : int or None
474 How many digits to consider
476 Returns
477 --------
478 unique : (j,) int
479 Index in data which is a unique row
480 inverse : (n,) int
481 Array to reconstruct original
482 Example: data[unique][inverse] == data
483 """
484 # get rows hashable so we can run unique function on it
485 rows = hashable_rows(data, digits=digits)
487 # we are throwing away the first value which is the
488 # garbage row-hash and only returning index and inverse
489 if keep_order:
490 # keeps order of original occurrence
491 return unique_ordered(rows, return_index=True, return_inverse=True)[1:]
492 # returns values sorted by row-hash but since our row-hash
493 # were pretty much garbage the sort order isn't meaningful
494 return np.unique(rows, return_index=True, return_inverse=True)[1:]
497def unique_value_in_row(data, unique=None):
498 """
499 For a 2D array of integers find the position of a
500 value in each row which only occurs once.
502 If there are more than one value per row which
503 occur once, the last one is returned.
505 Parameters
506 ----------
507 data : (n, d) int
508 Data to check values
509 unique : (m,) int
510 List of unique values contained in data.
511 Generated from np.unique if not passed
513 Returns
514 ---------
515 result : (n, d) bool
516 With one or zero True values per row.
519 Examples
520 -------------------------------------
521 In [0]: r = np.array([[-1, 1, 1],
522 [-1, 1, -1],
523 [-1, 1, 1],
524 [-1, 1, -1],
525 [-1, 1, -1]], dtype=np.int8)
527 In [1]: unique_value_in_row(r)
528 Out[1]:
529 array([[ True, False, False],
530 [False, True, False],
531 [ True, False, False],
532 [False, True, False],
533 [False, True, False]], dtype=bool)
535 In [2]: unique_value_in_row(r).sum(axis=1)
536 Out[2]: array([1, 1, 1, 1, 1])
538 In [3]: r[unique_value_in_row(r)]
539 Out[3]: array([-1, 1, -1, 1, 1], dtype=int8)
540 """
541 if unique is None:
542 unique = np.unique(data)
543 data = np.asanyarray(data)
544 result = np.zeros_like(data, dtype=bool, subok=False)
545 for value in unique:
546 test = np.equal(data, value)
547 test_ok = test.sum(axis=1) == 1
548 result[test_ok] = test[test_ok]
549 return result
552def group_rows(data, require_count=None, digits=None):
553 """
554 Returns index groups of duplicate rows, for example:
555 [[1,2], [3,4], [1,2]] will return [[0,2], [1]]
558 Note that using require_count allows numpy advanced
559 indexing to be used in place of looping and
560 checking hashes and is ~10x faster.
563 Parameters
564 ----------
565 data : (n, m) array
566 Data to group
567 require_count : None or int
568 Only return groups of a specified length, eg:
569 require_count = 2
570 [[1,2], [3,4], [1,2]] will return [[0,2]]
571 digits : None or int
572 If data is floating point how many decimals
573 to consider, or calculated from tol.merge
575 Returns
576 ----------
577 groups : sequence (*,) int
578 Indices from in indicating identical rows.
579 """
581 # start with getting a sortable format
582 hashable = hashable_rows(data, digits=digits)
584 # if there isn't a constant column size use more complex logic
585 if require_count is None:
586 return group(hashable)
588 # record the order of the rows so we can get the original indices back
589 order = hashable.argsort()
590 # but for now, we want our hashes sorted
591 hashable = hashable[order]
592 # this is checking each neighbour for equality, example:
593 # example: hashable = [1, 1, 1]; dupe = [0, 0]
594 dupe = hashable[1:] != hashable[:-1]
595 # we want the first index of a group, so we can slice from that location
596 # example: hashable = [0 1 1]; dupe = [1,0]; dupe_idx = [0,1]
597 dupe_idx = np.append(0, np.nonzero(dupe)[0] + 1)
598 # if you wanted to use this one function to deal with non- regular groups
599 # you could use: np.array_split(dupe_idx)
600 # this is roughly 3x slower than using the group_dict method above.
601 start_ok = np.diff(np.concatenate((dupe_idx, [len(hashable)]))) == require_count
602 groups = np.tile(dupe_idx[start_ok].reshape((-1, 1)), require_count) + np.arange(
603 require_count
604 )
605 groups_idx = order[groups]
607 if require_count == 1:
608 return groups_idx.reshape(-1)
609 return groups_idx
612def boolean_rows(
613 a: ArrayLike, b: ArrayLike, operation=np.intersect1d
614) -> NDArray[np.int64]:
615 """
616 Find the rows in two arrays which occur in both rows.
618 Parameters
619 ---------
620 a: (n, d) int
621 Array with row vectors
622 b: (m, d) int
623 Array with row vectors
624 operation : function
625 Numpy boolean set operation function:
626 -np.intersect1d
627 -np.setdiff1d
629 Returns
630 --------
631 shared : (p, d) int64
632 Array containing requested rows in both a and b
633 """
634 a = np.asanyarray(a, dtype=np.int64)
635 b = np.asanyarray(b, dtype=np.int64)
637 av = a.view([("", a.dtype)] * a.shape[1]).ravel()
638 bv = b.view([("", b.dtype)] * b.shape[1]).ravel()
639 return operation(av, bv).view(a.dtype).reshape(-1, a.shape[1])
642def group_vectors(vectors, angle=1e-4, include_negative=False):
643 """
644 Group vectors based on an angle tolerance, with the option to
645 include negative vectors.
647 Parameters
648 -----------
649 vectors : (n,3) float
650 Direction vector
651 angle : float
652 Group vectors closer than this angle in radians
653 include_negative : bool
654 If True consider the same:
655 [0,0,1] and [0,0,-1]
657 Returns
658 ------------
659 new_vectors : (m,3) float
660 Direction vector
661 groups : (m,) sequence of int
662 Indices of source vectors
663 """
665 vectors = np.asanyarray(vectors, dtype=np.float64)
666 angle = float(angle)
668 if include_negative:
669 vectors = util.vector_hemisphere(vectors)
671 spherical = util.vector_to_spherical(vectors)
672 angles, groups = group_distance(spherical, angle)
673 new_vectors = util.spherical_to_vector(angles)
674 return new_vectors, groups
677def group_distance(
678 values: ArrayLike, distance: Number
679) -> tuple[NDArray[np.float64], Sequence]:
680 """
681 Find non-overlapping groups of points where no two points in a
682 group are farther than 2*distance apart.
684 Parameters
685 ---------
686 values : (n, d) float
687 Points of dimension d
688 distance : float
689 Max distance between points in a cluster
691 Returns
692 ----------
693 unique : (m, d) float
694 Median value of each group
695 groups : (m) sequence of int
696 Indexes of points that make up a group
698 """
699 values = np.asanyarray(values, dtype=np.float64)
701 consumed = np.zeros(len(values), dtype=bool)
702 tree = cKDTree(values)
704 # (n, d) set of values that are unique
705 unique = []
706 # (n) sequence of indices in values
707 groups = []
709 for index, value in enumerate(values):
710 if consumed[index]:
711 continue
712 group = np.array(tree.query_ball_point(value, distance), dtype=np.int64)
713 group = group[~consumed[group]]
714 consumed[group] = True
715 unique.append(np.median(values[group], axis=0))
716 groups.append(group)
717 return np.array(unique), groups
720def clusters(points, radius):
721 """
722 Find clusters of points which have neighbours closer than radius
724 Parameters
725 ---------
726 points : (n, d) float
727 Points of dimension d
728 radius : float
729 Max distance between points in a cluster
731 Returns
732 ----------
733 groups : (m,) sequence of int
734 Indices of points in a cluster
736 """
737 from . import graph
739 tree = cKDTree(points)
741 # some versions return pairs as a set of tuples
742 pairs = tree.query_pairs(r=radius, output_type="ndarray")
743 # group connected components
744 groups = graph.connected_components(pairs)
746 return groups
749def blocks(data, min_len=2, max_len=np.inf, wrap=False, digits=None, only_nonzero=False):
750 """
751 Find the indices in an array of contiguous blocks
752 of equal values.
754 Parameters
755 ------------
756 data : (n,) array
757 Data to find blocks on
758 min_len : int
759 The minimum length group to be returned
760 max_len : int
761 The maximum length group to be retuurned
762 wrap : bool
763 Combine blocks on both ends of 1D array
764 digits : None or int
765 If dealing with floats how many digits to consider
766 only_nonzero : bool
767 Only return blocks of non- zero values
769 Returns
770 ---------
771 blocks : (m) sequence of (*,) int
772 Indices referencing data
773 """
774 data = float_to_int(data, digits=digits)
776 # keep an integer range around so we can slice
777 arange = np.arange(len(data))
778 arange.flags["WRITEABLE"] = False
780 nonzero = arange[1:][data[1:] != data[:-1]]
781 infl = np.zeros(len(nonzero) + 2, dtype=int)
782 infl[-1] = len(data)
783 infl[1:-1] = nonzero
785 # the length of each chunk
786 infl_len = infl[1:] - infl[:-1]
788 # check the length of each group
789 infl_ok = np.logical_and(infl_len >= min_len, infl_len <= max_len)
791 if only_nonzero:
792 # check to make sure the values of each contiguous block
793 # are True by checking the first value of each block
794 infl_ok = np.logical_and(infl_ok, data[infl[:-1]])
796 # inflate start/end indexes into full ranges of values
797 blocks = [arange[infl[i] : infl[i + 1]] for i, ok in enumerate(infl_ok) if ok]
799 if wrap:
800 # wrap only matters if first and last points are the same
801 if data[0] != data[-1]:
802 return blocks
803 # if we are only grouping nonzero things and
804 # the first and last point are zero we can exit
805 if only_nonzero and not bool(data[0]):
806 return blocks
808 # if all values are True or False we can exit
809 if len(blocks) == 1 and len(blocks[0]) == len(data):
810 return blocks
812 # so now first point equals last point, so the cases are:
813 # - first and last point are in a block: combine two blocks
814 # - first OR last point are in block: add other point to block
815 # - neither are in a block: check if combined is eligible block
817 # first point is in a block
818 first = len(blocks) > 0 and blocks[0][0] == 0
819 # last point is in a block
820 last = len(blocks) > 0 and blocks[-1][-1] == (len(data) - 1)
822 # CASE: first and last point are BOTH in block: combine blocks
823 if first and last:
824 blocks[0] = np.append(blocks[-1], blocks[0])
825 blocks.pop()
826 else:
827 # combined length
828 combined = infl_len[0] + infl_len[-1]
829 # exit if lengths aren't OK
830 if combined < min_len or combined > max_len:
831 return blocks
832 # new block combines both ends
833 new_block = np.append(
834 np.arange(infl[-2], infl[-1]), np.arange(infl[0], infl[1])
835 )
836 # we are in a first OR last situation now
837 if first:
838 # first was already in a block so replace it with combined
839 blocks[0] = new_block
840 elif last:
841 # last was already in a block so replace with superset
842 blocks[-1] = new_block
843 else:
844 # both are false
845 # combined length generated new block
846 blocks.append(new_block)
848 return blocks
851def group_min(groups, data):
852 """
853 Given a list of groups find the minimum element of data
854 within each group
856 Parameters
857 -----------
858 groups : (n,) sequence of (q,) int
859 Indexes of each group corresponding to each element in data
860 data : (m,)
861 The data that groups indexes reference
863 Returns
864 -----------
865 minimums : (n,)
866 Minimum value of data per group
868 """
869 # sort with major key groups, minor key data
870 order = np.lexsort((data, groups))
871 groups = groups[order] # this is only needed if groups is unsorted
872 data = data[order]
873 # construct an index which marks borders between groups
874 index = np.zeros(len(groups), "bool")
875 index[0] = True
876 index[1:] = groups[1:] != groups[:-1]
877 return data[index]