prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  ensure_spacing function may be slow
  ## Description
  
  The `skimage._shared.coord.ensure_spacing` function introduced in #4760 may be slow when the number of input points is large.
  
  ## Way to reproduce
  ```python
  In [1]: import numpy as np
  
  In [2]: from skimage._shared.coord import ensure_spacing
  
  In [3]: for n in range(500, 10001, 500):
      ...:     print(f"n = {n}")
      ...:     x = np.random.rand(n, 2)
      ...:     %timeit ensure_spacing(x, 0.2)
      ...: 
  n = 500
  27.6 ms ± 857 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
  n = 1000
  64.7 ms ± 1.93 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
  n = 1500
  105 ms ± 2.27 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
  n = 2000
  158 ms ± 1.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
  n = 2500
  213 ms ± 7.32 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 3000
  299 ms ± 11.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 3500
  378 ms ± 3.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 4000
  428 ms ± 11.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 4500
  554 ms ± 14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 5000
  647 ms ± 9.42 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 5500
  777 ms ± 7.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 6000
  870 ms ± 13.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 6500
  1.03 s ± 9.56 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 7000
  1.17 s ± 12.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 7500
  1.33 s ± 28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 8000
  1.45 s ± 18.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 8500
  1.63 s ± 36.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 9000
  1.87 s ± 50.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 9500
  2.07 s ± 23.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  n = 10000
  2.29 s ± 51.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  ```
  
  
  </issue>
  <code>
  [start of skimage/_shared/coord.py]
  1 import numpy as np
  2 from scipy.spatial import cKDTree, distance
  3 
  4 
  5 def ensure_spacing(coord, spacing=1, p_norm=np.inf):
  6     """Returns a subset of coord where a minimum spacing is guaranteed.
  7 
  8     Parameters
  9     ----------
  10     coord : ndarray
  11         The coordinates of the considered points.
  12     spacing : float
  13         the maximum allowed spacing between the points.
  14     p_norm : float
  15         Which Minkowski p-norm to use. Should be in the range [1, inf].
  16         A finite large p may cause a ValueError if overflow can occur.
  17         ``inf`` corresponds to the Chebyshev distance and 2 to the
  18         Euclidean distance.
  19 
  20     Returns
  21     -------
  22     output : ndarray
  23         A subset of coord where a minimum spacing is guaranteed.
  24 
  25     """
  26 
  27     output = coord
  28     if len(coord):
  29         # Use KDtree to find the peaks that are too close to each other
  30         tree = cKDTree(coord)
  31 
  32         indices = tree.query_ball_point(coord, r=spacing, p=p_norm)
  33         rejected_peaks_indices = set()
  34         for idx, candidates in enumerate(indices):
  35             if idx not in rejected_peaks_indices:
  36                 # keep current point and the points at exactly spacing from it
  37                 candidates.remove(idx)
  38                 dist = distance.cdist([coord[idx]],
  39                                       coord[candidates],
  40                                       distance.minkowski,
  41                                       p=p_norm).reshape(-1)
  42                 candidates = [c for c, d in zip(candidates, dist)
  43                               if d < spacing]
  44 
  45                 # candidates.remove(keep)
  46                 rejected_peaks_indices.update(candidates)
  47 
  48         # Remove the peaks that are too close to each other
  49         output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)
  50 
  51     return output
  52
  [end of skimage/_shared/coord.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/skimage/_shared/coord.py b/skimage/_shared/coord.py
  --- a/skimage/_shared/coord.py
  +++ b/skimage/_shared/coord.py
  @@ -2,7 +2,7 @@
   from scipy.spatial import cKDTree, distance
   
   
  -def ensure_spacing(coord, spacing=1, p_norm=np.inf):
  +def _ensure_spacing(coord, spacing, p_norm):
       """Returns a subset of coord where a minimum spacing is guaranteed.
   
       Parameters
  @@ -24,28 +24,72 @@
   
       """
   
  -    output = coord
  -    if len(coord):
  -        # Use KDtree to find the peaks that are too close to each other
  -        tree = cKDTree(coord)
  -
  -        indices = tree.query_ball_point(coord, r=spacing, p=p_norm)
  -        rejected_peaks_indices = set()
  -        for idx, candidates in enumerate(indices):
  -            if idx not in rejected_peaks_indices:
  -                # keep current point and the points at exactly spacing from it
  -                candidates.remove(idx)
  -                dist = distance.cdist([coord[idx]],
  -                                      coord[candidates],
  -                                      distance.minkowski,
  -                                      p=p_norm).reshape(-1)
  -                candidates = [c for c, d in zip(candidates, dist)
  -                              if d < spacing]
  -
  -                # candidates.remove(keep)
  -                rejected_peaks_indices.update(candidates)
  -
  -        # Remove the peaks that are too close to each other
  -        output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)
  +    # Use KDtree to find the peaks that are too close to each other
  +    tree = cKDTree(coord)
  +
  +    indices = tree.query_ball_point(coord, r=spacing, p=p_norm)
  +    rejected_peaks_indices = set()
  +    for idx, candidates in enumerate(indices):
  +        if idx not in rejected_peaks_indices:
  +            # keep current point and the points at exactly spacing from it
  +            candidates.remove(idx)
  +            dist = distance.cdist([coord[idx]],
  +                                  coord[candidates],
  +                                  distance.minkowski,
  +                                  p=p_norm).reshape(-1)
  +            candidates = [c for c, d in zip(candidates, dist)
  +                          if d < spacing]
  +
  +            # candidates.remove(keep)
  +            rejected_peaks_indices.update(candidates)
  +
  +    # Remove the peaks that are too close to each other
  +    output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)
  +
  +    return output
  +
  +
  +def ensure_spacing(coords, spacing=1, p_norm=np.inf, min_split_size=50):
  +    """Returns a subset of coord where a minimum spacing is guaranteed.
  +
  +    Parameters
  +    ----------
  +    coord : array_like
  +        The coordinates of the considered points.
  +    spacing : float
  +        the maximum allowed spacing between the points.
  +    p_norm : float
  +        Which Minkowski p-norm to use. Should be in the range [1, inf].
  +        A finite large p may cause a ValueError if overflow can occur.
  +        ``inf`` corresponds to the Chebyshev distance and 2 to the
  +        Euclidean distance.
  +    min_split_size : int
  +        Minimum split size used to process ``coord`` by batch to save
  +        memory. If None, the memory saving strategy is not applied.
  +
  +    Returns
  +    -------
  +    output : array_like
  +        A subset of coord where a minimum spacing is guaranteed.
  +
  +    """
  +
  +    output = coords
  +    if len(coords):
  +
  +        coords = np.atleast_2d(coords)
  +        if min_split_size is None:
  +            batch_list = [coords]
  +        else:
  +            coord_count = len(coords)
  +            split_count = int(np.log2(coord_count / min_split_size)) + 1
  +            split_idx = np.cumsum(
  +                [coord_count // (2 ** i) for i in range(1, split_count)])
  +            batch_list = np.array_split(coords, split_idx)
  +
  +        output = np.zeros((0, coords.shape[1]), dtype=coords.dtype)
  +        for batch in batch_list:
  +            output = _ensure_spacing(np.vstack([output, batch]),
  +                                     spacing, p_norm)
   
       return output
  
verification_info: {"golden_diff": "diff --git a/skimage/_shared/coord.py b/skimage/_shared/coord.py\n--- a/skimage/_shared/coord.py\n+++ b/skimage/_shared/coord.py\n@@ -2,7 +2,7 @@\n from scipy.spatial import cKDTree, distance\n \n \n-def ensure_spacing(coord, spacing=1, p_norm=np.inf):\n+def _ensure_spacing(coord, spacing, p_norm):\n     \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n \n     Parameters\n@@ -24,28 +24,72 @@\n \n     \"\"\"\n \n-    output = coord\n-    if len(coord):\n-        # Use KDtree to find the peaks that are too close to each other\n-        tree = cKDTree(coord)\n-\n-        indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n-        rejected_peaks_indices = set()\n-        for idx, candidates in enumerate(indices):\n-            if idx not in rejected_peaks_indices:\n-                # keep current point and the points at exactly spacing from it\n-                candidates.remove(idx)\n-                dist = distance.cdist([coord[idx]],\n-                                      coord[candidates],\n-                                      distance.minkowski,\n-                                      p=p_norm).reshape(-1)\n-                candidates = [c for c, d in zip(candidates, dist)\n-                              if d < spacing]\n-\n-                # candidates.remove(keep)\n-                rejected_peaks_indices.update(candidates)\n-\n-        # Remove the peaks that are too close to each other\n-        output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n+    # Use KDtree to find the peaks that are too close to each other\n+    tree = cKDTree(coord)\n+\n+    indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n+    rejected_peaks_indices = set()\n+    for idx, candidates in enumerate(indices):\n+        if idx not in rejected_peaks_indices:\n+            # keep current point and the points at exactly spacing from it\n+            candidates.remove(idx)\n+            dist = distance.cdist([coord[idx]],\n+                                  coord[candidates],\n+                                  distance.minkowski,\n+                                  p=p_norm).reshape(-1)\n+            candidates = [c for c, d in zip(candidates, dist)\n+                          if d < spacing]\n+\n+            # candidates.remove(keep)\n+            rejected_peaks_indices.update(candidates)\n+\n+    # Remove the peaks that are too close to each other\n+    output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n+\n+    return output\n+\n+\n+def ensure_spacing(coords, spacing=1, p_norm=np.inf, min_split_size=50):\n+    \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n+\n+    Parameters\n+    ----------\n+    coord : array_like\n+        The coordinates of the considered points.\n+    spacing : float\n+        the maximum allowed spacing between the points.\n+    p_norm : float\n+        Which Minkowski p-norm to use. Should be in the range [1, inf].\n+        A finite large p may cause a ValueError if overflow can occur.\n+        ``inf`` corresponds to the Chebyshev distance and 2 to the\n+        Euclidean distance.\n+    min_split_size : int\n+        Minimum split size used to process ``coord`` by batch to save\n+        memory. If None, the memory saving strategy is not applied.\n+\n+    Returns\n+    -------\n+    output : array_like\n+        A subset of coord where a minimum spacing is guaranteed.\n+\n+    \"\"\"\n+\n+    output = coords\n+    if len(coords):\n+\n+        coords = np.atleast_2d(coords)\n+        if min_split_size is None:\n+            batch_list = [coords]\n+        else:\n+            coord_count = len(coords)\n+            split_count = int(np.log2(coord_count / min_split_size)) + 1\n+            split_idx = np.cumsum(\n+                [coord_count // (2 ** i) for i in range(1, split_count)])\n+            batch_list = np.array_split(coords, split_idx)\n+\n+        output = np.zeros((0, coords.shape[1]), dtype=coords.dtype)\n+        for batch in batch_list:\n+            output = _ensure_spacing(np.vstack([output, batch]),\n+                                     spacing, p_norm)\n \n     return output\n", "issue": "ensure_spacing function may be slow\n## Description\r\n\r\nThe `skimage._shared.coord.ensure_spacing` function introduced in #4760 may be slow when the number of input points is large.\r\n\r\n## Way to reproduce\r\n```python\r\nIn [1]: import numpy as np\r\n\r\nIn [2]: from skimage._shared.coord import ensure_spacing\r\n\r\nIn [3]: for n in range(500, 10001, 500):\r\n    ...:     print(f\"n = {n}\")\r\n    ...:     x = np.random.rand(n, 2)\r\n    ...:     %timeit ensure_spacing(x, 0.2)\r\n    ...: \r\nn = 500\r\n27.6 ms \u00b1 857 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 1000\r\n64.7 ms \u00b1 1.93 ms per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 1500\r\n105 ms \u00b1 2.27 ms per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 2000\r\n158 ms \u00b1 1.18 ms per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 2500\r\n213 ms \u00b1 7.32 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 3000\r\n299 ms \u00b1 11.9 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 3500\r\n378 ms \u00b1 3.05 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 4000\r\n428 ms \u00b1 11.7 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 4500\r\n554 ms \u00b1 14 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 5000\r\n647 ms \u00b1 9.42 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 5500\r\n777 ms \u00b1 7.05 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 6000\r\n870 ms \u00b1 13.2 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 6500\r\n1.03 s \u00b1 9.56 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 7000\r\n1.17 s \u00b1 12.8 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 7500\r\n1.33 s \u00b1 28 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 8000\r\n1.45 s \u00b1 18.5 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 8500\r\n1.63 s \u00b1 36.6 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 9000\r\n1.87 s \u00b1 50.4 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 9500\r\n2.07 s \u00b1 23.3 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 10000\r\n2.29 s \u00b1 51.3 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\n```\r\n\n", "before_files": [{"content": "import numpy as np\nfrom scipy.spatial import cKDTree, distance\n\n\ndef ensure_spacing(coord, spacing=1, p_norm=np.inf):\n    \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n\n    Parameters\n    ----------\n    coord : ndarray\n        The coordinates of the considered points.\n    spacing : float\n        the maximum allowed spacing between the points.\n    p_norm : float\n        Which Minkowski p-norm to use. Should be in the range [1, inf].\n        A finite large p may cause a ValueError if overflow can occur.\n        ``inf`` corresponds to the Chebyshev distance and 2 to the\n        Euclidean distance.\n\n    Returns\n    -------\n    output : ndarray\n        A subset of coord where a minimum spacing is guaranteed.\n\n    \"\"\"\n\n    output = coord\n    if len(coord):\n        # Use KDtree to find the peaks that are too close to each other\n        tree = cKDTree(coord)\n\n        indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n        rejected_peaks_indices = set()\n        for idx, candidates in enumerate(indices):\n            if idx not in rejected_peaks_indices:\n                # keep current point and the points at exactly spacing from it\n                candidates.remove(idx)\n                dist = distance.cdist([coord[idx]],\n                                      coord[candidates],\n                                      distance.minkowski,\n                                      p=p_norm).reshape(-1)\n                candidates = [c for c, d in zip(candidates, dist)\n                              if d < spacing]\n\n                # candidates.remove(keep)\n                rejected_peaks_indices.update(candidates)\n\n        # Remove the peaks that are too close to each other\n        output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n\n    return output\n", "path": "skimage/_shared/coord.py"}]}