119class GridDetector:
120    """
121    Detects table grid intersections using morphological filtering and template matching.
122
123    This detector implements a multi-stage pipeline:
124
125    1. **Binarization**: Sauvola adaptive thresholding to handle varying lighting
126    2. **Morphological operations**: Dilation to connect broken rule segments
127    3. **Cross-kernel matching**: Template matching with a cross-shaped kernel to find
128       rule intersections where horizontal and vertical lines meet
129    4. **Grid growing**: Iterative point detection starting from a known seed point
130
131    The cross-kernel is designed to match the specific geometry of your table rules.
132    It should be sized so that after morphology, it aligns with actual corner shapes.
133
134    ## Tuning Guidelines
135
136    - **kernel_size**: Increase if you need more selectivity (fewer false positives)
137    - **cross_width/height**: Should match rule thickness after morphology
138    - **morph_size**: Increase to connect more broken lines, but this thickens rules
139    - **sauvola_k**: Increase to threshold more aggressively (remove noise)
140    - **search_region**: Increase for documents with more warping/distortion
141    - **distance_penalty**: Increase to prefer corners closer to expected positions
142
143    ## Visual Debugging
144
145    Set `visual=True` in methods to see intermediate results and tune parameters.
146    """
147
148    def __init__(
149        self,
150        kernel_size: int = 21,
151        cross_width: int = 6,
152        cross_height: Optional[int] = None,
153        morph_size: Optional[int] = None,
154        sauvola_k: float = 0.04,
155        sauvola_window: int = 15,
156        scale: float = 1.0,
157        search_region: int = 40,
158        distance_penalty: float = 0.4,
159        min_rows: int = 5,
160        grow_threshold: float = 0.3,
161        look_distance: int = 4,
162    ):
163        """
164        Args:
165            kernel_size (int): the size of the cross kernel
166                a larger kernel size often means that more penalty is applied, often leading
167                to more sparse results
168            cross_width (int): the width of one of the edges in the cross filter, should be
169                roughly equal to the width of the rules in the image after morphology is applied
170            cross_height (int | None): useful if the horizontal rules and vertical rules
171                have different sizes
172            morph_size (int | None): the size of the morphology operators that are applied before
173                the cross kernel. 'bridges the gaps' of broken-up lines
174            sauvola_k (float): threshold parameter for sauvola thresholding
175            sauvola_window (int): window_size parameter for sauvola thresholding
176            scale (float): image scale factor to do calculations on (useful for increasing calculation speed mostly)
177            search_region (int): area in which to search for a new max value in `find_nearest` etc.
178            distance_penalty (float): how much the point finding algorithm penalizes points that are further in the region [0, 1]
179            min_rows (int): minimum number of rows to find before stopping the table finding algorithm
180            grow_threshold (float): the threshold for accepting a new point when growing the table
181            look_distance (int): how many points away to look when calculating the median slope
182        """
183        self._validate_parameters(
184            kernel_size,
185            cross_width,
186            cross_height,
187            morph_size,
188            search_region,
189            sauvola_k,
190            sauvola_window,
191            distance_penalty,
192        )
193
194        self._kernel_size = kernel_size
195        self._cross_width = cross_width
196        self._cross_height = cross_width if cross_height is None else cross_height
197        self._morph_size = morph_size if morph_size is not None else cross_width
198        self._search_region = search_region
199        self._sauvola_k = sauvola_k
200        self._sauvola_window = sauvola_window
201        self._distance_penalty = distance_penalty
202        self._scale = scale
203        self._min_rows = min_rows
204        self._grow_threshold = grow_threshold
205        self._look_distance = look_distance
206
207        self._cross_kernel = self._create_cross_kernel()
208
209    def _validate_parameters(
210        self,
211        kernel_size: int,
212        cross_width: int,
213        cross_height: Optional[int],
214        morph_size: Optional[int],
215        search_region: int,
216        sauvola_k: float,
217        sauvola_window: int,
218        distance_penalty: float,
219    ) -> None:
220        """Validate initialization parameters."""
221        if kernel_size % 2 == 0:
222            raise ValueError("kernel_size must be odd")
223        if (
224            kernel_size <= 0
225            or cross_width <= 0
226            or search_region <= 0
227            or sauvola_window <= 0
228        ):
229            raise ValueError("Size parameters must be positive")
230        if cross_height is not None and cross_height <= 0:
231            raise ValueError("cross_height must be positive")
232        if morph_size is not None and morph_size <= 0:
233            raise ValueError("morph_size must be positive")
234        if not 0 <= distance_penalty <= 1:
235            raise ValueError("distance_penalty must be in [0, 1]")
236        if sauvola_k <= 0:
237            raise ValueError("sauvola_k must be positive")
238
239    def _create_gaussian_weights(self, region_size: int) -> NDArray:
240        """
241        Create a 2D Gaussian weight mask.
242
243        Args:
244            shape (tuple[int, int]): Shape of the region (height, width)
245            p (float): Minimum value at the edge = 1 - p
246
247        Returns:
248            NDArray: Gaussian weight mask
249        """
250        if self._distance_penalty == 0:
251            return np.ones((region_size, region_size), dtype=np.float32)
252
253        y = np.linspace(-1, 1, region_size)
254        x = np.linspace(-1, 1, region_size)
255        xv, yv = np.meshgrid(x, y)
256        dist_squared = xv**2 + yv**2
257
258        # Prevent log(0) when distance_penalty is 1
259        if self._distance_penalty >= 0.999:
260            sigma = 0.1  # Small sigma for very sharp peak
261        else:
262            sigma = np.sqrt(-1 / (2 * np.log(1 - self._distance_penalty)))
263
264        weights = np.exp(-dist_squared / (2 * sigma**2))
265
266        return weights.astype(np.float32)
267
268    def _create_cross_kernel(self) -> NDArray:
269        kernel = np.zeros((self._kernel_size, self._kernel_size), dtype=np.uint8)
270        center = self._kernel_size // 2
271
272        # Create horizontal bar
273        h_start = max(0, center - self._cross_height // 2)
274        h_end = min(self._kernel_size, center + (self._cross_height + 1) // 2)
275        kernel[h_start:h_end, :] = 255
276
277        # Create vertical bar
278        v_start = max(0, center - self._cross_width // 2)
279        v_end = min(self._kernel_size, center + (self._cross_width + 1) // 2)
280        kernel[:, v_start:v_end] = 255
281
282        return kernel
283
284    def _apply_morphology(self, binary: MatLike) -> MatLike:
285        # Define a horizontal kernel (adjust width as needed)
286        kernel_hor = cv.getStructuringElement(cv.MORPH_RECT, (self._morph_size, 1))
287        kernel_ver = cv.getStructuringElement(cv.MORPH_RECT, (1, self._morph_size))
288
289        # Apply dilation
290        dilated = cv.dilate(binary, kernel_hor, iterations=1)
291        dilated = cv.dilate(dilated, kernel_ver, iterations=1)
292
293        return dilated
294
295    def _apply_cross_matching(self, img: MatLike) -> MatLike:
296        """Apply cross kernel template matching."""
297        pad_y = self._cross_kernel.shape[0] // 2
298        pad_x = self._cross_kernel.shape[1] // 2
299
300        padded = cv.copyMakeBorder(
301            img, pad_y, pad_y, pad_x, pad_x, borderType=cv.BORDER_CONSTANT, value=0
302        )
303
304        filtered = cv.matchTemplate(padded, self._cross_kernel, cv.TM_SQDIFF_NORMED)
305        # Invert and normalize to 0-255 range
306        filtered = cv.normalize(1.0 - filtered, None, 0, 255, cv.NORM_MINMAX)
307        return filtered.astype(np.uint8)
308
309    def apply(self, img: MatLike, visual: bool = False) -> MatLike:
310        """
311        Apply the grid detection filter to the input image.
312
313        Args:
314            img (MatLike): the input image
315            visual (bool): whether to show intermediate steps
316
317        Returns:
318            MatLike: the filtered image, with high values (whiter pixels) at intersections of horizontal and vertical rules
319        """
320
321        if img is None or img.size == 0:
322            raise ValueError("Input image is empty or None")
323
324        binary = imu.sauvola(img, k=self._sauvola_k, window_size=self._sauvola_window)
325
326        if visual:
327            imu.show(binary, title="thresholded")
328
329        binary = self._apply_morphology(binary)
330
331        if visual:
332            imu.show(binary, title="dilated")
333
334        filtered = self._apply_cross_matching(binary)
335
336        return filtered
337
338    @log_calls(level=logging.DEBUG, include_return=True)
339    def find_nearest(
340        self, filtered: MatLike, point: Point, region: Optional[int] = None
341    ) -> Tuple[Point, float]:
342        """
343        Find the nearest 'corner match' in the image, along with its score [0,1]
344
345        Args:
346            filtered (MatLike): the filtered image (obtained through `apply`)
347            point (tuple[int, int]): the approximate target point (x, y)
348            region (None | int): alternative value for search region,
349                overwriting the `__init__` parameter `region`
350        """
351
352        if filtered is None or filtered.size == 0:
353            raise ValueError("Filtered image is empty or None")
354
355        region_size = region if region is not None else self._search_region
356        x, y = point
357
358        # Calculate crop boundaries
359        crop_x = max(0, x - region_size // 2)
360        crop_y = max(0, y - region_size // 2)
361        crop_width = min(region_size, filtered.shape[1] - crop_x)
362        crop_height = min(region_size, filtered.shape[0] - crop_y)
363
364        # Handle edge cases
365        if crop_width <= 0 or crop_height <= 0:
366            logger.warning(f"Point {point} is outside image bounds")
367            return point, 0.0
368
369        cropped = filtered[crop_y : crop_y + crop_height, crop_x : crop_x + crop_width]
370
371        if cropped.size == 0:
372            return point, 0.0
373
374        # Always apply Gaussian weighting by extending crop if needed
375        if cropped.shape[0] == region_size and cropped.shape[1] == region_size:
376            # Perfect size - apply weights directly
377            weights = self._create_gaussian_weights(region_size)
378            weighted = cropped.astype(np.float32) * weights
379        else:
380            # Extend crop to match region_size, apply weights, then restore
381            extended = np.zeros((region_size, region_size), dtype=cropped.dtype)
382
383            # Calculate offset to center the cropped region in extended array
384            offset_y = (region_size - cropped.shape[0]) // 2
385            offset_x = (region_size - cropped.shape[1]) // 2
386
387            # Place cropped region in center of extended array
388            extended[
389                offset_y : offset_y + cropped.shape[0],
390                offset_x : offset_x + cropped.shape[1],
391            ] = cropped
392
393            # Apply Gaussian weights to extended array
394            weights = self._create_gaussian_weights(region_size)
395            weighted_extended = extended.astype(np.float32) * weights
396
397            # Extract the original region back out
398            weighted = weighted_extended[
399                offset_y : offset_y + cropped.shape[0],
400                offset_x : offset_x + cropped.shape[1],
401            ]
402
403        best_idx = np.argmax(weighted)
404        best_y, best_x = np.unravel_index(best_idx, cropped.shape)
405
406        result_point = (
407            int(crop_x + best_x),
408            int(crop_y + best_y),
409        )
410        result_confidence = float(weighted[best_y, best_x]) / 255.0
411
412        return result_point, result_confidence
413
414    def find_table_points(
415        self,
416        img: MatLike | PathLike[str],
417        left_top: Point,
418        cell_widths: list[int],
419        cell_heights: list[int] | int,
420        visual: bool = False,
421        window: str = WINDOW,
422        goals_width: Optional[int] = None,
423        filtered: Optional[MatLike | PathLike[str]] = None,
424    ) -> "TableGrid":
425        """
426        Parse the image to a `TableGrid` structure that holds all of the
427        intersections between horizontal and vertical rules, starting near the `left_top` point
428
429        Args:
430            img (MatLike): the input image of a table
431            left_top (tuple[int, int]): the starting point of the algorithm
432            cell_widths (list[int]): the expected widths of the cells (based on a header template)
433            cell_heights (list[int]): the expected height of the rows of data.
434                The last value from this list is used until the image has no more vertical space.
435            visual (bool): whether to show intermediate steps
436            window (str): the name of the OpenCV window to use for visualization
437            goals_width (int | None): the width of the goal region when searching for the next point.
438                If None, defaults to 1.5 * search_region
439            filtered (MatLike | PathLike[str] | None): if provided, this image is used instead of
440                calculating the filtered image from scratch
441
442        Returns:
443            a TableGrid object
444        """
445
446        if goals_width is None:
447            goals_width = self._search_region * 3 // 2
448
449        if not cell_widths:
450            raise ValueError("cell_widths must contain at least one value")
451
452        if not isinstance(img, np.ndarray):
453            img = cv.imread(os.fspath(img))
454
455        if filtered is None:
456            filtered = self.apply(img, visual)
457        else:
458            if not isinstance(filtered, np.ndarray):
459                filtered = cv.imread(os.fspath(filtered))
460
461            filtered = ensure_gray(filtered)
462
463        if visual:
464            imu.show(filtered, window=window)
465
466        if isinstance(cell_heights, int):
467            cell_heights = [cell_heights]
468
469        left_top, confidence = self.find_nearest(
470            filtered, left_top, int(self._search_region * 3)
471        )
472
473        if confidence < 0.1:
474            logger.warning(
475                f"Low confidence for the starting point: {confidence} at {left_top}"
476            )
477
478        # resize all parameters according to scale
479        img = cv.resize(img, None, fx=self._scale, fy=self._scale)
480
481        if visual:
482            imu.push(img)
483
484        filtered = cv.resize(filtered, None, fx=self._scale, fy=self._scale)
485        cell_widths = [int(w * self._scale) for w in cell_widths]
486        cell_heights = [int(h * self._scale) for h in cell_heights]
487        left_top = (int(left_top[0] * self._scale), int(left_top[1] * self._scale))
488        self._search_region = int(self._search_region * self._scale)
489
490        img_gray = ensure_gray(img)
491        filtered_gray = ensure_gray(filtered)
492
493        table_grower = TableGrower(
494            img_gray,
495            filtered_gray,
496            cell_widths,  # pyright: ignore
497            cell_heights,  # pyright: ignore
498            left_top,
499            self._search_region,
500            self._distance_penalty,
501            self._look_distance,
502            self._grow_threshold,
503            self._min_rows,
504        )
505
506        def show_grower_progress(wait: bool = False):
507            img_orig = np.copy(img)
508            corners = table_grower.get_all_corners()
509            for y in range(len(corners)):
510                for x in range(len(corners[y])):
511                    if corners[y][x] is not None:
512                        img_orig = imu.draw_points(
513                            img_orig,
514                            [corners[y][x]],
515                            color=(0, 0, 255),
516                            thickness=30,
517                        )
518
519            edge = table_grower.get_edge_points()
520
521            for point, score in edge:
522                color = (100, int(clamp(score * 255, 0, 255)), 100)
523                imu.draw_point(img_orig, point, color=color, thickness=20)
524
525            imu.show(img_orig, wait=wait)
526
527        if visual:
528            threshold = self._grow_threshold
529            look_distance = self._look_distance
530
531            # python implementation of rust loops, for visualization purposes
532            # note this is a LOT slower
533            while table_grower.grow_point(img_gray, filtered_gray) is not None:
534                show_grower_progress()
535
536            show_grower_progress(True)
537
538            original_threshold = threshold
539
540            loops_without_change = 0
541
542            while not table_grower.is_table_complete():
543                loops_without_change += 1
544
545                if loops_without_change > 50:
546                    break
547
548                if table_grower.extrapolate_one(img_gray, filtered_gray) is not None:
549                    show_grower_progress()
550
551                    loops_without_change = 0
552
553                    grown = False
554                    while table_grower.grow_point(img_gray, filtered_gray) is not None:
555                        show_grower_progress()
556                        grown = True
557                        threshold = min(0.1 + 0.9 * threshold, original_threshold)
558                        table_grower.set_threshold(threshold)
559
560                    if not grown:
561                        threshold *= 0.9
562                        table_grower.set_threshold(threshold)
563
564                else:
565                    threshold *= 0.9
566                    table_grower.set_threshold(threshold)
567
568                    if table_grower.grow_point(img_gray, filtered_gray) is not None:
569                        show_grower_progress()
570                        loops_without_change = 0
571
572        else:
573            table_grower.grow_table(img_gray, filtered_gray)
574
575        table_grower.smooth_grid()
576        corners = table_grower.get_all_corners()
577        logger.info(
578            f"Table growth complete, found {len(corners)} rows and {len(corners[0])} columns"
579        )
580        # rescale corners back to original size
581        if self._scale != 1.0:
582            for y in range(len(corners)):
583                for x in range(len(corners[y])):
584                    if corners[y][x] is not None:
585                        corners[y][x] = (
586                            int(corners[y][x][0] / self._scale),  # pyright:ignore
587                            int(corners[y][x][1] / self._scale),  # pyright:ignore
588                        )
589
590        return TableGrid(corners)  # pyright: ignore
591
592    @log_calls(level=logging.DEBUG, include_return=True)
593    def _build_table_row(
594        self,
595        gray: MatLike,
596        filtered: MatLike,
597        start_point: Point,
598        cell_widths: List[int],
599        row_idx: int,
600        goals_width: int,
601        previous_row_points: Optional[List[Point]] = None,
602        visual: bool = False,
603    ) -> List[Point]:
604        """Build a single row of table points."""
605        row = [start_point]
606        current = start_point
607
608        for col_idx, width in enumerate(cell_widths):
609            next_point = self._find_next_column_point(
610                gray,
611                filtered,
612                current,
613                width,
614                goals_width,
615                visual,
616                previous_row_points,
617                col_idx,
618            )
619            if next_point is None:
620                logger.warning(
621                    f"Could not find point for row {row_idx}, col {col_idx + 1}"
622                )
623                return []  # Return empty list to signal failure
624            row.append(next_point)
625            current = next_point
626
627        return row
628
629    def _clamp_point_to_img(self, point: Point, img: MatLike) -> Point:
630        """Clamp a point to be within the image bounds."""
631        x = max(0, min(point[0], img.shape[1] - 1))
632        y = max(0, min(point[1], img.shape[0] - 1))
633        return (x, y)
634
635    @log_calls(level=logging.DEBUG, include_return=True)
636    def _find_next_column_point(
637        self,
638        gray: MatLike,
639        filtered: MatLike,
640        current: Point,
641        width: int,
642        goals_width: int,
643        visual: bool = False,
644        previous_row_points: Optional[List[Point]] = None,
645        current_col_idx: int = 0,
646    ) -> Optional[Point]:
647        """Find the next point in the current row."""
648
649        if previous_row_points is not None and current_col_idx + 1 < len(
650            previous_row_points
651        ):
652            # grow an astar path downwards from the previous row point that is
653            # above and to the right of current
654            # and ensure all points are within image bounds
655            bottom_right = [
656                self._clamp_point_to_img(
657                    (
658                        current[0] + width - goals_width // 2 + x,
659                        current[1] + goals_width,
660                    ),
661                    gray,
662                )
663                for x in range(goals_width)
664            ]
665            goals = self._astar(
666                gray, previous_row_points[current_col_idx + 1], bottom_right, "down"
667            )
668
669            if goals is None:
670                logger.warning(
671                    f"A* failed to find path going downwards from previous row's point at idx {current_col_idx + 1}"
672                )
673                return None
674        else:
675            goals = [
676                self._clamp_point_to_img(
677                    (current[0] + width, current[1] - goals_width // 2 + y), gray
678                )
679                for y in range(goals_width)
680            ]
681
682        path = self._astar(gray, current, goals, "right")
683
684        if path is None:
685            logger.warning(
686                f"A* failed to find path going rightward from {current} to goals"
687            )
688            return None
689
690        next_point, _ = self.find_nearest(filtered, path[-1], self._search_region)
691
692        # show the point and the search region on the image for debugging
693        if visual:
694            self._visualize_path_finding(
695                goals + path,
696                current,
697                next_point,
698                current,
699                path[-1],
700                self._search_region,
701            )
702
703        return next_point
704
705    @log_calls(level=logging.DEBUG, include_return=True)
706    def _find_next_row_start(
707        self,
708        gray: MatLike,
709        filtered: MatLike,
710        top_point: Point,
711        row_idx: int,
712        cell_heights: List[int],
713        goals_width: int,
714        visual: bool = False,
715    ) -> Optional[Point]:
716        """Find the starting point of the next row."""
717        if row_idx < len(cell_heights):
718            row_height = cell_heights[row_idx]
719        else:
720            row_height = cell_heights[-1]
721
722        if top_point[1] + row_height >= filtered.shape[0] - 10:  # Near bottom
723            return None
724
725        goals = [
726            (top_point[0] - goals_width // 2 + x, top_point[1] + row_height)
727            for x in range(goals_width)
728        ]
729
730        path = self._astar(gray, top_point, goals, "down")
731        if path is None:
732            return None
733
734        next_point, _ = self.find_nearest(
735            filtered, path[-1], region=self._search_region * 3 // 2
736        )
737
738        if visual:
739            self._visualize_path_finding(
740                path, top_point, next_point, top_point, path[-1], self._search_region
741            )
742
743        return next_point
744
745    def _visualize_grid(self, img: MatLike, points: List[List[Point]]) -> None:
746        """Visualize the detected grid points."""
747        all_points = [point for row in points for point in row]
748        drawn = imu.draw_points(img, all_points)
749        imu.show(drawn, wait=True)
750
751    def _visualize_path_finding(
752        self,
753        path: List[Point],
754        current: Point,
755        next_point: Point,
756        previous_row_target: Optional[Point] = None,
757        region_center: Optional[Point] = None,
758        region_size: Optional[int] = None,
759    ) -> None:
760        """Visualize the path finding process for debugging."""
761        global show_time
762
763        screen = imu.pop()
764
765        # if gray, convert to BGR
766        if len(screen.shape) == 2 or screen.shape[2] == 1:
767            debug_img = cv.cvtColor(screen, cv.COLOR_GRAY2BGR)
768        else:
769            debug_img = cast(MatLike, screen)
770
771        debug_img = imu.draw_points(debug_img, path, color=(200, 200, 0), thickness=2)
772        debug_img = imu.draw_points(
773            debug_img, [current], color=(0, 255, 0), thickness=3
774        )
775        debug_img = imu.draw_points(
776            debug_img, [next_point], color=(0, 0, 255), thickness=2
777        )
778
779        # Draw previous row target if available
780        if previous_row_target is not None:
781            debug_img = imu.draw_points(
782                debug_img, [previous_row_target], color=(255, 0, 255), thickness=2
783            )
784
785        # Draw search region if available
786        if region_center is not None and region_size is not None:
787            top_left = (
788                max(0, region_center[0] - region_size // 2),
789                max(0, region_center[1] - region_size // 2),
790            )
791            bottom_right = (
792                min(debug_img.shape[1], region_center[0] + region_size // 2),
793                min(debug_img.shape[0], region_center[1] + region_size // 2),
794            )
795            cv.rectangle(
796                debug_img,
797                top_left,
798                bottom_right,
799                color=(255, 0, 0),
800                thickness=2,
801                lineType=cv.LINE_AA,
802            )
803
804        imu.push(debug_img)
805
806        show_time += 1
807        if show_time % 10 != 1:
808            return
809
810        imu.show(debug_img, title="Next column point", wait=False)
811        # time.sleep(0.003)
812
813    @log_calls(level=logging.DEBUG, include_return=True)
814    def _astar(
815        self,
816        img: np.ndarray,
817        start: tuple[int, int],
818        goals: list[tuple[int, int]],
819        direction: str,
820    ) -> Optional[List[Point]]:
821        """
822        Find the best path between the start point and one of the goal points on the image
823        """
824
825        if not goals:
826            return None
827
828        if self._scale != 1.0:
829            img = cv.resize(img, None, fx=self._scale, fy=self._scale)
830            start = (int(start[0] * self._scale), int(start[1] * self._scale))
831            goals = [(int(g[0] * self._scale), int(g[1] * self._scale)) for g in goals]
832
833        # calculate bounding box with margin
834        all_points = goals + [start]
835        xs = [p[0] for p in all_points]
836        ys = [p[1] for p in all_points]
837
838        margin = 30
839        top_left = (max(0, min(xs) - margin), max(0, min(ys) - margin))
840        bottom_right = (
841            min(img.shape[1], max(xs) + margin),
842            min(img.shape[0], max(ys) + margin),
843        )
844
845        # check bounds
846        if (
847            top_left[0] >= bottom_right[0]
848            or top_left[1] >= bottom_right[1]
849            or top_left[0] >= img.shape[1]
850            or top_left[1] >= img.shape[0]
851        ):
852            return None
853
854        # transform coordinates to cropped image
855        start_local = (start[0] - top_left[0], start[1] - top_left[1])
856        goals_local = [(g[0] - top_left[0], g[1] - top_left[1]) for g in goals]
857
858        cropped = img[top_left[1] : bottom_right[1], top_left[0] : bottom_right[0]]
859
860        if cropped.size == 0:
861            return None
862
863        path = rust_astar(cropped, start_local, goals_local, direction)
864
865        if path is None:
866            return None
867
868        if self._scale != 1.0:
869            path = [(int(p[0] / self._scale), int(p[1] / self._scale)) for p in path]
870            top_left = (int(top_left[0] / self._scale), int(top_left[1] / self._scale))
871
872        return [(p[0] + top_left[0], p[1] + top_left[1]) for p in path]