fizgrid.utils

  1import math, type_enforced, uuid
  2
  3
  4def unique_id():
  5    """
  6    Generates a unique identifier.
  7    """
  8    return str(uuid.uuid4())
  9
 10
 11@type_enforced.Enforcer(enabled=True)
 12class Shape:
 13    @staticmethod
 14    def circle(
 15        radius: int | float, num_points: int = 6, round_to: int = 2
 16    ) -> list[list]:
 17        """
 18        Returns a list of addative coordinates that form a circle around a given point.
 19
 20        Args:
 21
 22        - radius (int|float): Radius of the circle.
 23        - num_points (int): Number of points to generate around the circle.
 24            - Default: 6
 25            - This is used to determine the number of points to generate around the circle.
 26        - round_to (int): Number of decimal places to round to.
 27            - Default: 2
 28            - This is used to round the coordinates to a specific number of decimal places.
 29
 30        Returns:
 31
 32        - list[list]: A list of coordinates representing the circle.
 33            - Each coordinate is a list of two values [x, y].
 34            - The coordinates are relative to the center of the circle.
 35        """
 36        return [
 37            [
 38                round(
 39                    radius * math.cos(2 * math.pi / num_points * i), round_to
 40                ),
 41                round(
 42                    radius * math.sin(2 * math.pi / num_points * i), round_to
 43                ),
 44            ]
 45            for i in range(num_points)
 46        ]
 47
 48    @staticmethod
 49    def rectangle(
 50        x_len: float | int, y_len: float | int, round_to: int = 2
 51    ) -> list[list]:
 52        """
 53        Returns a list of addative coordinates that form a rectangle around a given point.
 54
 55        Args:
 56
 57        - x_len (float|int): Length of the rectangle along the x-axis.
 58        - y_len (float|int): Length of the rectangle along the y-axis.
 59        - round_to (int): Number of decimal places to round to.
 60            - Default: 2
 61            - This is used to round the coordinates to a specific number of decimal places.
 62
 63        Returns:
 64
 65        - list[list]: A list of coordinates representing the rectangle.
 66            - Each coordinate is a list of two values [x, y].
 67            - The coordinates are relative to the center of the rectangle.
 68        """
 69        return [
 70            [round(x_len / 2, round_to), round(y_len / 2, round_to)],
 71            [round(-x_len / 2, round_to), round(y_len / 2, round_to)],
 72            [round(-x_len / 2, round_to), round(-y_len / 2, round_to)],
 73            [round(x_len / 2, round_to), round(-y_len / 2, round_to)],
 74        ]
 75
 76    @staticmethod
 77    def rotate(
 78        radians: float | int, shape: list[list[float | int]], round_to: int = 2
 79    ) -> list[list[float | int]]:
 80        """
 81        Rotates a shape by a given angle in radians around its origin (0, 0).
 82        Args:
 83        - radians (float|int): The angle in radians to rotate the shape.
 84        - shape (list[list[float|int]]): The shape to rotate.
 85            - This is a list of coordinates representing the shape.
 86            - Each coordinate is a list of two values [x, y].
 87        Returns:
 88        - list[list[float|int]]: The rotated shape.
 89            - This is a list of coordinates representing the rotated shape.
 90            - Each coordinate is a list of two values [x, y].
 91        """
 92        return [
 93            [
 94                round(
 95                    coord[0] * math.cos(radians) - coord[1] * math.sin(radians),
 96                    round_to,
 97                ),
 98                round(
 99                    coord[0] * math.sin(radians) + coord[1] * math.cos(radians),
100                    round_to,
101                ),
102            ]
103            for coord in shape
104        ]
105
106    @staticmethod
107    def get_rotated_shape(
108        shape: list[list[float | int]],
109        x_shift: float | int,
110        y_shift: float | int,
111    ):
112        """
113        Rotates the shape to align with the direction of motion.
114
115        Args:
116
117        - shape (list[list[float|int]]): List of coordinates representing the shape's vertices relative to its center.
118        - x_shift (float|int): Total distance the shape moves along the x-axis during [t_start, t_end].
119        - y_shift (float|int): Total distance the shape moves along the y-axis during [t_start, t_end].
120
121        Returns:
122
123        - list[list[float|int]]: The rotated shape.
124            - This is a list of coordinates representing the rotated shape.
125            - Each coordinate is a list of two values [x, y].
126        """
127        if x_shift == 0 and y_shift == 0:
128            return shape
129        radians = math.atan2(y_shift, x_shift)
130        return Shape.rotate(radians=radians, shape=shape)
131
132
133class ShapeMoverUtils:
134    @staticmethod
135    def moving_segment_overlap_intervals(
136        seg_start: int | float,
137        seg_end: int | float,
138        t_start: int | float,
139        t_end: int | float,
140        shift: int | float,
141    ):
142        """
143        Calculates the time intervals during which a moving 1D line segment overlaps with each unit-length
144        integer-aligned range along the x-axis.
145
146        Args:
147
148        - seg_start (int|float): Initial position of the left end of the line segment.
149        - seg_end (int|float): Initial position of the right end of the line segment.
150        - t_start (int|float): Start time of the motion.
151        - t_end (int|float): End time of the motion.
152        - shift (int|float): Total distance the line segment moves along the x-axis during [t_start, t_end].
153
154        Returns:
155
156        - dict[int, tuplie(int|float,int|float)]: A dictionary mapping each integer `i` to the time interval [t_in, t_out]
157                                during which any part of the line overlaps the range [i, i+1).
158                                Only includes ranges with non-zero overlap duration.
159        """
160        duration = t_end - t_start
161        velocity = shift / duration if duration != 0 else 0
162
163        result = {}
164
165        final_start = seg_start + shift
166        final_end = seg_end + shift
167        global_min = min(seg_start, final_start)
168        global_max = max(seg_end, final_end)
169
170        for i in range(int(global_min) - 1, int(global_max) + 2):
171            if velocity == 0:
172                if seg_end > i and seg_start < i + 1 and t_start < t_end:
173                    result[i] = (t_start, t_end)
174                continue
175            # Solve for times when the line enters and exits overlap with [i, i+1)
176            t1 = (i - seg_end) / velocity + t_start
177            t2 = (i + 1 - seg_start) / velocity + t_start
178            entry_time = max(min(t1, t2), t_start)
179            exit_time = min(max(t1, t2), t_end)
180
181            if exit_time > entry_time:
182                result[i] = (entry_time, exit_time)
183
184        return result
185
186    @staticmethod
187    def moving_rectangle_overlap_intervals(
188        x_start: float | int,
189        x_end: float | int,
190        y_start: float | int,
191        y_end: float | int,
192        x_shift: float | int,
193        y_shift: float | int,
194        t_start: float | int,
195        t_end: float | int,
196    ):
197        """
198        Calculates the time intervals during which a moving rectangle overlaps with each unit-length
199        integer-aligned range along the x and y axes.
200
201        Args:
202
203        - x_start (float|int): Initial position of the left end of the rectangle along the x-axis.
204        - x_end (float|int): Initial position of the right end of the rectangle along the x-axis.
205        - y_start (float|int): Initial position of the bottom end of the rectangle along the y-axis.
206        - y_end (float|int): Initial position of the top end of the rectangle along the y-axis.
207        - x_shift (float|int): Total distance the rectangle moves along the x-axis during [t_start, t_end].
208        - y_shift (float|int): Total distance the rectangle moves along the y-axis during [t_start, t_end].
209        - t_start (float|int): Start time of the motion.
210        - t_end (float|int): End time of the motion.
211
212        Returns:
213
214        - dict[tuple(int,int),tuple(int|float,int|float)]: A dictionary mapping each integer (i,j) to the time interval [t_in, t_out]
215            during which any part of the rectangle overlaps the range [i, i+1) x [j, j+1).
216            Only includes ranges with non-zero overlap duration.
217
218        """
219        x_intervals = ShapeMoverUtils.moving_segment_overlap_intervals(
220            seg_start=x_start,
221            seg_end=x_end,
222            t_start=t_start,
223            t_end=t_end,
224            shift=x_shift,
225        )
226        y_intervals = ShapeMoverUtils.moving_segment_overlap_intervals(
227            seg_start=y_start,
228            seg_end=y_end,
229            t_start=t_start,
230            t_end=t_end,
231            shift=y_shift,
232        )
233        result = {}
234        for x_key, x_interval in x_intervals.items():
235            for y_key, y_interval in y_intervals.items():
236                # Only add intervals with time overlap
237                if (
238                    x_interval[1] > y_interval[0]
239                    and y_interval[1] > x_interval[0]
240                ):
241                    result[(x_key, y_key)] = (
242                        max(x_interval[0], y_interval[0]),
243                        min(x_interval[1], y_interval[1]),
244                    )
245
246        return result
247
248    @staticmethod
249    def argmin(lst):
250        return min(enumerate(lst), key=lambda x: x[1])[0]
251
252    @staticmethod
253    def argmax(lst):
254        return max(enumerate(lst), key=lambda x: x[1])[0]
255
256    @staticmethod
257    def find_extreme_orthogonal_vertices(
258        points: list[tuple[int | float, int | float]], slope: float | int
259    ):
260        """
261        Finds the points in a list that are the furthest apart in the direction
262        orthogonal to the given slope. This is useful for finding the extreme
263        points in a set of 2D coordinates that are orthogonal to a given line.
264
265        Args:
266
267        - points (list of tuples): A list of (x, y) coordinates.
268        - slope (float): The slope of the line.
269
270        Returns:
271
272        - tuple: The points with the minimum and maximum projections.
273        """
274        # Compute orthogonal slope
275        orthogonal = float("inf") if slope == 0 else -1 / slope
276        # Define direction projections (a normalized direction vector, but without the linear algebra)
277        # Handle vertical slope
278        if orthogonal == float("inf"):
279            x_proj = 0.0
280            y_proj = 1.0
281        else:
282            # Note: Technically normalized length is (1**2 + orthogonal**2)**.5, but we avoid the extra square for performance
283            length = (1 + orthogonal**2) ** 0.5
284            x_proj = 1.0 / length
285            y_proj = orthogonal / length
286        # Compute projections
287        projections = [x * x_proj + y * y_proj for x, y in points]
288        # Return the min and max projections
289        return (
290            points[ShapeMoverUtils.argmin(projections)],
291            points[ShapeMoverUtils.argmax(projections)],
292        )
293
294    @staticmethod
295    def find_extreme_orthogonal_vertices_simplified(
296        points: list[tuple[int | float, int | float]], slope: float | int
297    ):
298        """
299        A simplified version of the function `find_extreme_orthogonal_vertices`
300        that assumes the slope is never 0.
301
302        Finds the points in a list that are the furthest apart in the direction
303        orthogonal to the given slope. This is useful for finding the extreme
304        points in a set of 2D coordinates that are orthogonal to a given line.
305
306        Args:
307
308        - points (list of tuples): A list of (x, y) coordinates.
309        - slope (float): The slope of the line.
310            - Note: This should never be 0 or infinite for this function.
311
312        Returns:
313
314        - tuple: The points with the minimum and maximum projections.
315        """
316        # Compute orthogonal slope
317        orthogonal = -1 / slope
318        # Define direction projections (a normalized direction vector, but without the linear algebra)
319        # Note: Technically normalized length is (1**2 + orthogonal**2)**.5, but we avoid the extra square for performance
320        length = (1 + orthogonal**2) ** 0.5
321        projections = [
322            x * 1.0 / length + y * orthogonal / length for x, y in points
323        ]
324        # Return the min and max verticies
325        vertex_1 = points[ShapeMoverUtils.argmin(projections)]
326        vertex_2 = points[ShapeMoverUtils.argmax(projections)]
327        if slope < 0:
328            return vertex_1, vertex_2
329        else:
330            return vertex_2, vertex_1
331
332    @staticmethod
333    def remove_untouched_intervals(
334        intervals: dict[tuple[int, int], tuple[int | float, int | float]],
335        slope: float | int,
336        absolute_shape: list[tuple[int | float, int | float]],
337    ):
338        """
339        Removes unnecessary intervals from the dictionary of intervals.
340
341        Args:
342
343        - intervals (dict[tuple(int,int),tuple(int|float,int|float)]): A dictionary mapping each integer (i,j) to the time interval [t_in, t_out]
344            during which any part of the shape overlaps the range [i, i+1) x [j, j+1).
345        - slope (float|int): The slope of the line.
346        - absolute_shape (list(tuple[int|float, int|float])): A list of coordinates representing the shape's vertices relative to its center.
347
348        Returns:
349
350        - dict[tuple(int,int),tuple(int|float,int|float)]: A dictionary with unnecessary intervals removed.
351        """
352        min_vertex, max_vertex = (
353            ShapeMoverUtils.find_extreme_orthogonal_vertices_simplified(
354                points=absolute_shape, slope=slope
355            )
356        )
357        shape_min_intercept = min_vertex[1] - slope * min_vertex[0]
358        shape_max_intercept = max_vertex[1] - slope * max_vertex[0]
359
360        # Given the slope, determine which cell vertex to use for the max and min intercepts
361        # This is to ensure that the intervals are removed correctly
362        ltx_increment = 1 if slope < 0 else 0
363        gtx_increment = 0 if slope < 0 else 1
364
365        remove_keys = []
366        for x_cell, y_cell in intervals.keys():
367            cell_min_intercept = y_cell - (slope * (x_cell + gtx_increment))
368            cell_max_intercept = (y_cell + 1) - (
369                slope * (x_cell + ltx_increment)
370            )
371            # If the intercept ranges do not overlap, remove the interval
372            if not (
373                cell_min_intercept < shape_max_intercept
374                and shape_min_intercept < cell_max_intercept
375            ):
376                remove_keys.append((x_cell, y_cell))
377        for key in remove_keys:
378            del intervals[key]
379        return intervals
380
381    @staticmethod
382    def moving_shape_overlap_intervals(
383        x_coord: float | int,
384        y_coord: float | int,
385        x_shift: float | int,
386        y_shift: float | int,
387        t_start: float | int,
388        t_end: float | int,
389        shape: list[list[float | int]],
390        cell_density: int = 1,
391    ):
392        """
393        Calculates the time intervals during which a moving shape overlaps with each unit-length
394        integer-aligned range along the x and y axes.
395
396        Note: This converts each shape into a full bounding box rectangle and then uses the rectangle overlap function to calculate the intervals.
397
398        Args:
399
400        - x_coord (float|int): Initial x-coordinate of the shape's center.
401        - y_coord (float|int): Initial y-coordinate of the shape's center.
402        - x_shift (float|int): Total distance the shape moves along the x-axis during [t_start, t_end].
403        - y_shift (float|int): Total distance the shape moves along the y-axis during [t_start, t_end].
404        - t_start (float|int): Start time of the motion.
405        - t_end (float|int): End time of the motion.
406        - shape (list[list[float|int]]): List of coordinates representing the shape's vertices relative to its center.
407        - cell_density (int): The number of cells per unit of length.
408
409
410        Returns:
411
412        - dict[tuple(int,int),tuple(int|float,int|float)]: A dictionary mapping each integer (i,j) to the time interval [t_in, t_out]
413                                during which any part of the shape overlaps the range [i, i+1) x [j, j+1).
414                                Only includes ranges with non-zero overlap duration.
415        """
416        # Get the overlap intervals for a rectangle that bounds the shape in cell space
417        absolute_shape = [
418            [
419                (x_coord + coord[0]) * cell_density,
420                (y_coord + coord[1]) * cell_density,
421            ]
422            for coord in shape
423        ]
424        # Calculate the rectangle overlap intervals in cell space
425        rectangle_overlap_intervals = (
426            ShapeMoverUtils.moving_rectangle_overlap_intervals(
427                x_start=min([coord[0] for coord in absolute_shape]),
428                x_end=max([coord[0] for coord in absolute_shape]),
429                y_start=min([coord[1] for coord in absolute_shape]),
430                y_end=max([coord[1] for coord in absolute_shape]),
431                x_shift=x_shift * cell_density,
432                y_shift=y_shift * cell_density,
433                t_start=t_start,
434                t_end=t_end,
435            )
436        )
437        # If the shape is only moving vertically or horizontally, we can just return the rectangle overlap intervals
438        if x_shift == 0 or y_shift == 0:
439            return rectangle_overlap_intervals
440        # If the shape is moving diagonally, we should remove intervals that are never passed through by the shape
441        return ShapeMoverUtils.remove_untouched_intervals(
442            intervals=rectangle_overlap_intervals,
443            slope=y_shift / x_shift,
444            absolute_shape=absolute_shape,
445        )