Quadratic split in Python
Guttman's split that picks the pair of entries wasting the most area as seeds, then assigns the rest greedily.
- File
quadratic_split.py, 82 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/quadratic-split/. The authors are listed in prov/4EXTW1.jsonl.
"""Guttman's quadratic split of an overflowing R-tree node.
Rectangles are (xmin, ymin, xmax, ymax). The input is a list of at least 2
rectangles and a minimum fill m with 1 <= m <= len(rects) // 2. The output
is a pair of lists of indices into the input.
"""
from __future__ import annotations
from typing import List, Tuple
Rect = Tuple[float, float, float, float]
def area(r: Rect) -> float:
return (r[2] - r[0]) * (r[3] - r[1])
def union(a: Rect, b: Rect) -> Rect:
return (min(a[0], b[0]), min(a[1], b[1]), max(a[2], b[2]), max(a[3], b[3]))
def waste(a: Rect, b: Rect) -> float:
return area(union(a, b)) - area(a) - area(b)
def pick_seeds(rects: List[Rect]) -> Tuple[int, int]:
"""The pair (i, j), i < j, of largest waste; the first such pair on ties."""
best, bi, bj = None, 0, 1
for i in range(len(rects)): # @line L1
for j in range(i + 1, len(rects)):
d = waste(rects[i], rects[j])
if best is None or d > best:
best, bi, bj = d, i, j
return bi, bj # @line L2
def quadratic_split(rects: List[Rect], m: int) -> Tuple[List[int], List[int]]:
n = len(rects)
if n < 2 or not 1 <= m <= n // 2:
raise ValueError("need at least 2 rectangles and 1 <= m <= n // 2")
i, j = pick_seeds(rects)
g1, g2 = [i], [j]
r1, r2 = rects[i], rects[j]
rest = [k for k in range(n) if k != i and k != j]
while rest: # @line L3
if len(g1) + len(rest) == m: # @line L4
g1.extend(rest)
break
if len(g2) + len(rest) == m:
g2.extend(rest)
break
pick, diff = 0, -1.0
for t, k in enumerate(rest): # @line L5
d1 = area(union(r1, rects[k])) - area(r1)
d2 = area(union(r2, rects[k])) - area(r2)
if abs(d1 - d2) > diff: # @line L6
pick, diff = t, abs(d1 - d2)
k = rest.pop(pick)
d1 = area(union(r1, rects[k])) - area(r1)
d2 = area(union(r2, rects[k])) - area(r2)
if (d1, area(r1), len(g1)) <= (d2, area(r2), len(g2)): # @line L7
g1.append(k)
r1 = union(r1, rects[k])
else:
g2.append(k)
r2 = union(r2, rects[k])
return g1, g2 # @line L8
def mbr(rects: List[Rect]) -> Rect:
r = rects[0]
for s in rects[1:]:
r = union(r, s)
return r
def split_cost(rects: List[Rect], g1: List[int], g2: List[int]) -> float:
"""Total area of the two group rectangles, the measure Guttman minimizes."""
return area(mbr([rects[k] for k in g1])) + area(mbr([rects[k] for k in g2]))
test_quadratic_split.py 68 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/quadratic-split/. The authors are listed in prov/4EXTW1.jsonl.
import itertools
import random
import pytest
from quadratic_split import pick_seeds, quadratic_split, split_cost, waste
# a, b, c, d, e of the page example
RECTS = [(0, 0, 2, 2), (1, 5, 3, 7), (6, 0, 8, 1), (7, 6, 9, 9), (2, 1, 3, 3)]
def test_page_example():
w = {(i, j): waste(RECTS[i], RECTS[j]) for i in range(5) for j in range(i + 1, 5)}
assert w[(0, 3)] == 71 and max(w.values()) == 71
assert pick_seeds(RECTS) == (0, 3)
g1, g2 = quadratic_split(RECTS, 2)
assert g1 == [0, 4, 1] and g2 == [3, 2] # {a, e, b} and {d, c}
assert split_cost(RECTS, g1, g2) == 21 + 27
def test_edge_cases():
assert quadratic_split([(0, 0, 1, 1), (5, 5, 6, 6)], 1) == ([0], [1])
same = [(0, 0, 1, 1)] * 5
g1, g2 = quadratic_split(same, 2)
assert sorted(g1 + g2) == list(range(5)) and min(len(g1), len(g2)) >= 2
pts = [(i, i, i, i) for i in range(6)] # zero-area rectangles
g1, g2 = quadratic_split(pts, 3)
assert len(g1) == 3 and len(g2) == 3
with pytest.raises(ValueError):
quadratic_split(RECTS, 3)
with pytest.raises(ValueError):
quadratic_split(RECTS[:1], 1)
def best_cost(rects, m):
n = len(rects)
best = None
for size in range(m, n - m + 1):
for g1 in itertools.combinations(range(n), size):
g2 = [k for k in range(n) if k not in g1]
c = split_cost(rects, list(g1), g2)
best = c if best is None or c < best else best
return best
def test_random_against_brute_force():
rng = random.Random(4)
worse = 0
for _ in range(600):
n = rng.randint(2, 9)
m = rng.randint(1, n // 2)
rects = []
for _ in range(n):
x, y = rng.randint(0, 20), rng.randint(0, 20)
rects.append((x, y, x + rng.randint(0, 6), y + rng.randint(0, 6)))
g1, g2 = quadratic_split(rects, m)
assert sorted(g1 + g2) == list(range(n))
assert len(g1) >= m and len(g2) >= m
i, j = pick_seeds(rects)
assert g1[0] == i and g2[0] == j
assert waste(rects[i], rects[j]) == max(
waste(rects[a], rects[b]) for a in range(n) for b in range(a + 1, n))
opt = best_cost(rects, m)
assert split_cost(rects, g1, g2) >= opt
worse += split_cost(rects, g1, g2) > opt
assert worse > 0 # the heuristic is not optimal
What the next level needs
- the tests did not run in this build