xref: /aosp_15_r20/external/fonttools/Lib/fontTools/misc/arrayTools.py (revision e1fe3e4ad2793916b15cccdc4a7da52a7e1dd0e9) 
1"""Routines for calculating bounding boxes, point in rectangle calculations and
2so on.
3"""
4
5from fontTools.misc.roundTools import otRound
6from fontTools.misc.vector import Vector as _Vector
7import math
8import warnings
9
10
11def calcBounds(array):
12    """Calculate the bounding rectangle of a 2D points array.
13
14    Args:
15        array: A sequence of 2D tuples.
16
17    Returns:
18        A four-item tuple representing the bounding rectangle ``(xMin, yMin, xMax, yMax)``.
19    """
20    if not array:
21        return 0, 0, 0, 0
22    xs = [x for x, y in array]
23    ys = [y for x, y in array]
24    return min(xs), min(ys), max(xs), max(ys)
25
26
27def calcIntBounds(array, round=otRound):
28    """Calculate the integer bounding rectangle of a 2D points array.
29
30    Values are rounded to closest integer towards ``+Infinity`` using the
31    :func:`fontTools.misc.fixedTools.otRound` function by default, unless
32    an optional ``round`` function is passed.
33
34    Args:
35        array: A sequence of 2D tuples.
36        round: A rounding function of type ``f(x: float) -> int``.
37
38    Returns:
39        A four-item tuple of integers representing the bounding rectangle:
40        ``(xMin, yMin, xMax, yMax)``.
41    """
42    return tuple(round(v) for v in calcBounds(array))
43
44
45def updateBounds(bounds, p, min=min, max=max):
46    """Add a point to a bounding rectangle.
47
48    Args:
49        bounds: A bounding rectangle expressed as a tuple
50            ``(xMin, yMin, xMax, yMax), or None``.
51        p: A 2D tuple representing a point.
52        min,max: functions to compute the minimum and maximum.
53
54    Returns:
55        The updated bounding rectangle ``(xMin, yMin, xMax, yMax)``.
56    """
57    (x, y) = p
58    if bounds is None:
59        return x, y, x, y
60    xMin, yMin, xMax, yMax = bounds
61    return min(xMin, x), min(yMin, y), max(xMax, x), max(yMax, y)
62
63
64def pointInRect(p, rect):
65    """Test if a point is inside a bounding rectangle.
66
67    Args:
68        p: A 2D tuple representing a point.
69        rect: A bounding rectangle expressed as a tuple
70            ``(xMin, yMin, xMax, yMax)``.
71
72    Returns:
73        ``True`` if the point is inside the rectangle, ``False`` otherwise.
74    """
75    (x, y) = p
76    xMin, yMin, xMax, yMax = rect
77    return (xMin <= x <= xMax) and (yMin <= y <= yMax)
78
79
80def pointsInRect(array, rect):
81    """Determine which points are inside a bounding rectangle.
82
83    Args:
84        array: A sequence of 2D tuples.
85        rect: A bounding rectangle expressed as a tuple
86            ``(xMin, yMin, xMax, yMax)``.
87
88    Returns:
89        A list containing the points inside the rectangle.
90    """
91    if len(array) < 1:
92        return []
93    xMin, yMin, xMax, yMax = rect
94    return [(xMin <= x <= xMax) and (yMin <= y <= yMax) for x, y in array]
95
96
97def vectorLength(vector):
98    """Calculate the length of the given vector.
99
100    Args:
101        vector: A 2D tuple.
102
103    Returns:
104        The Euclidean length of the vector.
105    """
106    x, y = vector
107    return math.sqrt(x**2 + y**2)
108
109
110def asInt16(array):
111    """Round a list of floats to 16-bit signed integers.
112
113    Args:
114        array: List of float values.
115
116    Returns:
117        A list of rounded integers.
118    """
119    return [int(math.floor(i + 0.5)) for i in array]
120
121
122def normRect(rect):
123    """Normalize a bounding box rectangle.
124
125    This function "turns the rectangle the right way up", so that the following
126    holds::
127
128        xMin <= xMax and yMin <= yMax
129
130    Args:
131        rect: A bounding rectangle expressed as a tuple
132            ``(xMin, yMin, xMax, yMax)``.
133
134    Returns:
135        A normalized bounding rectangle.
136    """
137    (xMin, yMin, xMax, yMax) = rect
138    return min(xMin, xMax), min(yMin, yMax), max(xMin, xMax), max(yMin, yMax)
139
140
141def scaleRect(rect, x, y):
142    """Scale a bounding box rectangle.
143
144    Args:
145        rect: A bounding rectangle expressed as a tuple
146            ``(xMin, yMin, xMax, yMax)``.
147        x: Factor to scale the rectangle along the X axis.
148        Y: Factor to scale the rectangle along the Y axis.
149
150    Returns:
151        A scaled bounding rectangle.
152    """
153    (xMin, yMin, xMax, yMax) = rect
154    return xMin * x, yMin * y, xMax * x, yMax * y
155
156
157def offsetRect(rect, dx, dy):
158    """Offset a bounding box rectangle.
159
160    Args:
161        rect: A bounding rectangle expressed as a tuple
162            ``(xMin, yMin, xMax, yMax)``.
163        dx: Amount to offset the rectangle along the X axis.
164        dY: Amount to offset the rectangle along the Y axis.
165
166    Returns:
167        An offset bounding rectangle.
168    """
169    (xMin, yMin, xMax, yMax) = rect
170    return xMin + dx, yMin + dy, xMax + dx, yMax + dy
171
172
173def insetRect(rect, dx, dy):
174    """Inset a bounding box rectangle on all sides.
175
176    Args:
177        rect: A bounding rectangle expressed as a tuple
178            ``(xMin, yMin, xMax, yMax)``.
179        dx: Amount to inset the rectangle along the X axis.
180        dY: Amount to inset the rectangle along the Y axis.
181
182    Returns:
183        An inset bounding rectangle.
184    """
185    (xMin, yMin, xMax, yMax) = rect
186    return xMin + dx, yMin + dy, xMax - dx, yMax - dy
187
188
189def sectRect(rect1, rect2):
190    """Test for rectangle-rectangle intersection.
191
192    Args:
193        rect1: First bounding rectangle, expressed as tuples
194            ``(xMin, yMin, xMax, yMax)``.
195        rect2: Second bounding rectangle.
196
197    Returns:
198        A boolean and a rectangle.
199        If the input rectangles intersect, returns ``True`` and the intersecting
200        rectangle. Returns ``False`` and ``(0, 0, 0, 0)`` if the input
201        rectangles don't intersect.
202    """
203    (xMin1, yMin1, xMax1, yMax1) = rect1
204    (xMin2, yMin2, xMax2, yMax2) = rect2
205    xMin, yMin, xMax, yMax = (
206        max(xMin1, xMin2),
207        max(yMin1, yMin2),
208        min(xMax1, xMax2),
209        min(yMax1, yMax2),
210    )
211    if xMin >= xMax or yMin >= yMax:
212        return False, (0, 0, 0, 0)
213    return True, (xMin, yMin, xMax, yMax)
214
215
216def unionRect(rect1, rect2):
217    """Determine union of bounding rectangles.
218
219    Args:
220        rect1: First bounding rectangle, expressed as tuples
221            ``(xMin, yMin, xMax, yMax)``.
222        rect2: Second bounding rectangle.
223
224    Returns:
225        The smallest rectangle in which both input rectangles are fully
226        enclosed.
227    """
228    (xMin1, yMin1, xMax1, yMax1) = rect1
229    (xMin2, yMin2, xMax2, yMax2) = rect2
230    xMin, yMin, xMax, yMax = (
231        min(xMin1, xMin2),
232        min(yMin1, yMin2),
233        max(xMax1, xMax2),
234        max(yMax1, yMax2),
235    )
236    return (xMin, yMin, xMax, yMax)
237
238
239def rectCenter(rect):
240    """Determine rectangle center.
241
242    Args:
243        rect: Bounding rectangle, expressed as tuples
244            ``(xMin, yMin, xMax, yMax)``.
245
246    Returns:
247        A 2D tuple representing the point at the center of the rectangle.
248    """
249    (xMin, yMin, xMax, yMax) = rect
250    return (xMin + xMax) / 2, (yMin + yMax) / 2
251
252
253def rectArea(rect):
254    """Determine rectangle area.
255
256    Args:
257        rect: Bounding rectangle, expressed as tuples
258            ``(xMin, yMin, xMax, yMax)``.
259
260    Returns:
261        The area of the rectangle.
262    """
263    (xMin, yMin, xMax, yMax) = rect
264    return (yMax - yMin) * (xMax - xMin)
265
266
267def intRect(rect):
268    """Round a rectangle to integer values.
269
270    Guarantees that the resulting rectangle is NOT smaller than the original.
271
272    Args:
273        rect: Bounding rectangle, expressed as tuples
274            ``(xMin, yMin, xMax, yMax)``.
275
276    Returns:
277        A rounded bounding rectangle.
278    """
279    (xMin, yMin, xMax, yMax) = rect
280    xMin = int(math.floor(xMin))
281    yMin = int(math.floor(yMin))
282    xMax = int(math.ceil(xMax))
283    yMax = int(math.ceil(yMax))
284    return (xMin, yMin, xMax, yMax)
285
286
287def quantizeRect(rect, factor=1):
288    """
289    >>> bounds = (72.3, -218.4, 1201.3, 919.1)
290    >>> quantizeRect(bounds)
291    (72, -219, 1202, 920)
292    >>> quantizeRect(bounds, factor=10)
293    (70, -220, 1210, 920)
294    >>> quantizeRect(bounds, factor=100)
295    (0, -300, 1300, 1000)
296    """
297    if factor < 1:
298        raise ValueError(f"Expected quantization factor >= 1, found: {factor!r}")
299    xMin, yMin, xMax, yMax = normRect(rect)
300    return (
301        int(math.floor(xMin / factor) * factor),
302        int(math.floor(yMin / factor) * factor),
303        int(math.ceil(xMax / factor) * factor),
304        int(math.ceil(yMax / factor) * factor),
305    )
306
307
308class Vector(_Vector):
309    def __init__(self, *args, **kwargs):
310        warnings.warn(
311            "fontTools.misc.arrayTools.Vector has been deprecated, please use "
312            "fontTools.misc.vector.Vector instead.",
313            DeprecationWarning,
314        )
315
316
317def pairwise(iterable, reverse=False):
318    """Iterate over current and next items in iterable.
319
320    Args:
321        iterable: An iterable
322        reverse: If true, iterate in reverse order.
323
324    Returns:
325        A iterable yielding two elements per iteration.
326
327    Example:
328
329        >>> tuple(pairwise([]))
330        ()
331        >>> tuple(pairwise([], reverse=True))
332        ()
333        >>> tuple(pairwise([0]))
334        ((0, 0),)
335        >>> tuple(pairwise([0], reverse=True))
336        ((0, 0),)
337        >>> tuple(pairwise([0, 1]))
338        ((0, 1), (1, 0))
339        >>> tuple(pairwise([0, 1], reverse=True))
340        ((1, 0), (0, 1))
341        >>> tuple(pairwise([0, 1, 2]))
342        ((0, 1), (1, 2), (2, 0))
343        >>> tuple(pairwise([0, 1, 2], reverse=True))
344        ((2, 1), (1, 0), (0, 2))
345        >>> tuple(pairwise(['a', 'b', 'c', 'd']))
346        (('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a'))
347        >>> tuple(pairwise(['a', 'b', 'c', 'd'], reverse=True))
348        (('d', 'c'), ('c', 'b'), ('b', 'a'), ('a', 'd'))
349    """
350    if not iterable:
351        return
352    if reverse:
353        it = reversed(iterable)
354    else:
355        it = iter(iterable)
356    first = next(it, None)
357    a = first
358    for b in it:
359        yield (a, b)
360        a = b
361    yield (a, first)
362
363
364def _test():
365    """
366    >>> import math
367    >>> calcBounds([])
368    (0, 0, 0, 0)
369    >>> calcBounds([(0, 40), (0, 100), (50, 50), (80, 10)])
370    (0, 10, 80, 100)
371    >>> updateBounds((0, 0, 0, 0), (100, 100))
372    (0, 0, 100, 100)
373    >>> pointInRect((50, 50), (0, 0, 100, 100))
374    True
375    >>> pointInRect((0, 0), (0, 0, 100, 100))
376    True
377    >>> pointInRect((100, 100), (0, 0, 100, 100))
378    True
379    >>> not pointInRect((101, 100), (0, 0, 100, 100))
380    True
381    >>> list(pointsInRect([(50, 50), (0, 0), (100, 100), (101, 100)], (0, 0, 100, 100)))
382    [True, True, True, False]
383    >>> vectorLength((3, 4))
384    5.0
385    >>> vectorLength((1, 1)) == math.sqrt(2)
386    True
387    >>> list(asInt16([0, 0.1, 0.5, 0.9]))
388    [0, 0, 1, 1]
389    >>> normRect((0, 10, 100, 200))
390    (0, 10, 100, 200)
391    >>> normRect((100, 200, 0, 10))
392    (0, 10, 100, 200)
393    >>> scaleRect((10, 20, 50, 150), 1.5, 2)
394    (15.0, 40, 75.0, 300)
395    >>> offsetRect((10, 20, 30, 40), 5, 6)
396    (15, 26, 35, 46)
397    >>> insetRect((10, 20, 50, 60), 5, 10)
398    (15, 30, 45, 50)
399    >>> insetRect((10, 20, 50, 60), -5, -10)
400    (5, 10, 55, 70)
401    >>> intersects, rect = sectRect((0, 10, 20, 30), (0, 40, 20, 50))
402    >>> not intersects
403    True
404    >>> intersects, rect = sectRect((0, 10, 20, 30), (5, 20, 35, 50))
405    >>> intersects
406    1
407    >>> rect
408    (5, 20, 20, 30)
409    >>> unionRect((0, 10, 20, 30), (0, 40, 20, 50))
410    (0, 10, 20, 50)
411    >>> rectCenter((0, 0, 100, 200))
412    (50.0, 100.0)
413    >>> rectCenter((0, 0, 100, 199.0))
414    (50.0, 99.5)
415    >>> intRect((0.9, 2.9, 3.1, 4.1))
416    (0, 2, 4, 5)
417    """
418
419
420if __name__ == "__main__":
421    import sys
422    import doctest
423
424    sys.exit(doctest.testmod().failed)
425