fizgrid.utils

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