Центроид и bounding box

Урок про две незаменимые в ГИС операции: нахождение центра полигона (центроид) и его ограничивающего прямоугольника (bounding box).

Центроид — геометрический центр («центр масс») фигуры. Bounding box — наименьший прямоугольник со сторонами по осям, целиком содержащий фигуру.

Эти две операции встречаются повсюду. Центроид нужен, чтобы поставить подпись региона ровно по центру или взять «представительную точку» района для расчётов. Bounding box — это четыре числа $(x_{min}, y_{min}, x_{max}, y_{max})$, и он лежит в основе быстрых пространственных фильтров: прежде чем запускать дорогую проверку «точка в полигоне» для тысяч объектов, дёшево отсекают те, чьи прямоугольники даже не пересекаются.

Bounding box: четыре числа

Самое простое: bounding box набора точек — это минимумы и максимумы по каждой оси.

def bounding_box(points):
    xs = [p[0] for p in points]
    ys = [p[1] for p in points]
    return (min(xs), min(ys), max(xs), max(ys))

pts = [(1, 2), (5, 1), (3, 7), (-2, 4)]
xmin, ymin, xmax, ymax = bounding_box(pts)
print(f"bbox = ({xmin}, {ymin}, {xmax}, {ymax})")
print(f"ширина = {xmax - xmin}, высота = {ymax - ymin}")

Вывод:

bbox = (-2, 1, 5, 7)
ширина = 7, высота = 6

Центроид полигона

Наивная идея «среднее всех вершин» неверна: если на одной стороне вершин гуще, центр сместится к ним. Правильный центроид полигона учитывает площадь и считается по формуле, родственной шнуровке. Обозначим перекрёстное произведение ребра $c_i = x_i y_{i+1} - x_{i+1} y_i$, площадь со знаком $A = \frac{1}{2}\sum c_i$. Тогда:

$C_x = \frac{1}{6A}\sum (x_i + x_{i+1})\,c_i, \qquad C_y = \frac{1}{6A}\sum (y_i + y_{i+1})\,c_i$

def centroid(poly):
    n = len(poly)
    a = 0.0
    cx = 0.0
    cy = 0.0
    for i in range(n):
        x0, y0 = poly[i]
        x1, y1 = poly[(i + 1) % n]
        cross = x0 * y1 - x1 * y0
        a += cross
        cx += (x0 + x1) * cross
        cy += (y0 + y1) * cross
    a *= 0.5
    cx /= (6 * a)
    cy /= (6 * a)
    return cx, cy

square = [(0, 0), (4, 0), (4, 4), (0, 4)]
print(centroid(square))

# Несимметричный треугольник
tri = [(0, 0), (6, 0), (0, 3)]
cx, cy = centroid(tri)
print(f"({cx:.2f}, {cy:.2f})")

Вывод:

(2.0, 2.0)
(2.00, 1.00)

Центр квадрата — ровно $(2, 2)$, как и ждали. Для треугольника центроид совпадает со средним вершин $(\frac{0+6+0}{3}, \frac{0+0+3}{3}) = (2, 1)$ — для треугольника эти формулы дают одно и то же, но для произвольного полигона только взвешенная по площади формула верна.

Как работает под капотом

Bounding box незаменим как «грубый фильтр» в пространственных индексах: R-дерево хранит именно прямоугольники объектов и по ним за логарифмическое время находит кандидатов, после чего точную геометрию проверяют лишь для немногих выживших. Пересечение двух bounding box проверяется одним выражением: прямоугольники не пересекаются, если один целиком левее, правее, выше или ниже другого. Центроид же может оказаться вне фигуры — например, у полумесяца или подковы; если нужна точка гарантированно внутри (для подписи), берут не центроид, а «point on surface» — это отдельная операция в shapely.

Частые ошибки

Считать центроид средним вершин. Верно лишь для треугольника; для прочих полигонов нужна взвешенная по площади формула.
Ждать, что центроид всегда внутри. У вогнутых фигур он может выпасть наружу; для подписи берите point-on-surface.
Считать bounding box достаточным для попадания. Он только грубый фильтр-кандидат, а не точная проверка.

Две операции, которые держат производительность

Может показаться, что центроид и bounding box — мелочь рядом с «настоящим» анализом, но именно они часто определяют, работает система быстро или еле ползёт. Bounding box — это четыре числа, которые сравниваются за наносекунды, и на этом стоит вся пирамида пространственных индексов: прежде чем запускать дорогую проверку пересечения сложных полигонов, база за копейки отбрасывает пары, чьи прямоугольники даже не соприкасаются. На больших данных такой грубый отсев убирает 99% кандидатов, и точную геометрию считают лишь для горстки выживших. Без этого приёма любой серьёзный пространственный запрос упёрся бы в квадратичную сложность и встал.

Центроид же — рабочая «представительная точка» полигона. Им подписывают регионы на карте, к нему привязывают агрегированную статистику района, от него считают расстояния, когда возиться со всей геометрией дорого. Но важно помнить про его коварство: у вогнутых фигур — подковы, серпа, страны с глубоким заливом — центр масс может оказаться вне самого контура, в «дырке» или в море. Если точка нужна гарантированно внутри (скажем, чтобы поставить метку, которая не повиснет за пределами области), берут не центроид, а специальную операцию point-on-surface, которая всегда возвращает точку на теле фигуры. Знание этой разницы избавляет от загадочных «подписей в океане» на готовой карте.

Итог

Bounding box — четыре числа (min/max по осям), основа быстрых фильтров.
Центроид полигона считают взвешенно по площади, а не как среднее вершин.
Центроид может оказаться вне вогнутой фигуры.
R-дерево использует bounding box объектов для быстрого поиска кандидатов.