2025, Nov 03 15:02
Как упорядочить вершины многоугольника по внутренней полилинии
Как упорядочить граничные точки в многоугольник без самопересечений с помощью внутренней полилинии: локальные координаты, векторизация NumPy, на Python.
Упорядочить набор граничных точек в один многоугольник без самопересечений просто, когда фигура выпуклая, и заметно сложнее — когда нет. В нашей задаче у вас есть ещё и направляющая полилиния, проведённая внутри облака точек. Именно она ключевая: по ней можно задать локальную систему координат для каждой точки и получить детерминированный, воспроизводимый порядок обхода, который соблюдает внутреннее ограничение и проходит по каждой вершине ровно один раз.
Постановка задачи
Следующая программа иллюстрирует сценарий: произвольный штрих сглаживается до полилинии, для наглядности отображаются выборки нормалей, а отдельный набор перетаскиваемых точек представляет вершины многоугольника, которые нужно упорядочить. Наивная сортировка по углу не работает для вогнутых форм, а выпуклая оболочка или alpha shape могут пропустить точки. Цель — найти надёжный порядок, использующий внутреннюю линию.
import pygame
import numpy as np
from scipy.interpolate import splprep, splev
import sys
import random
# Настройка Pygame
pygame.init()
surface = pygame.display.set_mode((1000, 1000))
pygame.display.set_caption("Smoothed Curve with Draggable Points")
ticker = pygame.time.Clock()
# Цвета
COL_BG = (255, 255, 255)
COL_STROKE = (0, 0, 255)
COL_CURVE = (255, 0, 0)
COL_NORMAL = (0, 200, 0)
COL_POINT = (0, 0, 0)
is_tracing = False
stroke_pts = []
curve_pts = []
derivs = []
# Параметры точек
PT_R = 6
PICK_R = 10
class Handle:
def __init__(self, pos):
self.x, self.y = pos
self._drag = False
def xy(self):
return (int(self.x), int(self.y))
def hit_test(self, mx, my):
return (self.x - mx)**2 + (self.y - my)**2 <= PICK_R**2
def begin_drag(self):
self._drag = True
def end_drag(self):
self._drag = False
def move_to(self, mx, my):
if self._drag:
self.x, self.y = mx, my
# Черновое тестовое расположение точек.
anchors = [Handle(t) for t in [
(159, 459),(133, 193),(286, 481),(241, 345),(411, 404),
(280, 349),(352, 471),(395, 361),(85, 390),(203, 321),
(41, 281),(58, 348),(175, 275),(75, 185),(385, 443),
(44, 219),(148, 229),(215, 477),(338, 339),(122, 430)
]]
def take_every(seq, step=2):
return seq[::step]
def fit_curve(trace, smoothness=150):
if len(trace) < 4:
return [], []
trace = take_every(trace, step=2)
x, y = zip(*trace)
try:
tck, u = splprep([x, y], s=100.0, k=3)
u_new = np.linspace(0, 1, smoothness)
# Вычисление точек кривой
x_vals, y_vals = splev(u_new, tck)
# Производные: dx/du, dy/du
dx_du, dy_du = splev(u_new, tck, der=1)
slopes = np.array(dy_du) / np.array(dx_du)
return list(zip(x_vals, y_vals)), list(zip(dx_du, dy_du))
except:
return [], []
def render_normals(surf, curve, tangents, spacing=10, length=30):
for i in range(0, len(curve), spacing):
x, y = curve[i]
dx, dy = tangents[i]
nx, ny = -dy, dx
norm = np.hypot(nx, ny)
if norm == 0:
continue
nx /= norm
ny /= norm
x1 = x - nx * length / 2
y1 = y - ny * length / 2
x2 = x + nx * length / 2
y2 = y + ny * length / 2
pygame.draw.line(surf, COL_NORMAL, (x1, y1), (x2, y2), 2)
def spawn_anchors(n=20, w=800, h=600):
return [Handle((random.randint(0, w), random.randint(0, h))) for _ in range(n)]
# Главный цикл
active_handle = None
go = True
while go:
surface.fill(COL_BG)
mx, my = pygame.mouse.get_pos()
for event in pygame.event.get():
if event.type == pygame.QUIT:
go = False
elif event.type == pygame.MOUSEBUTTONDOWN:
is_tracing = True
stroke_pts = []
curve_pts = []
derivs = []
# Проверка перетаскиваемой точки
for h in anchors:
if h.hit_test(mx, my):
active_handle = h
h.begin_drag()
is_tracing = False
break
elif event.type == pygame.MOUSEBUTTONUP:
is_tracing = False
if active_handle:
active_handle.end_drag()
active_handle = None
else:
curve_pts, derivs = fit_curve(stroke_pts)
elif event.type == pygame.MOUSEMOTION:
if active_handle:
active_handle.move_to(mx, my)
elif is_tracing:
stroke_pts.append((mx, my))
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_p:
anchors = spawn_anchors()
if event.key == pygame.K_l:
for h in anchors: print(f"({h.x}, {h.y})")
# Рисуем опорные точки
for h in anchors:
pygame.draw.circle(surface, COL_POINT, h.xy(), PT_R)
# Рисуем исходный штрих
if len(stroke_pts) > 1:
pygame.draw.lines(surface, COL_STROKE, False, stroke_pts, 1)
# Рисуем сглаженную кривую
if len(curve_pts) > 1:
pygame.draw.lines(surface, COL_CURVE, False, curve_pts, 3)
# Рисуем нормали
if curve_pts and derivs:
render_normals(surface, curve_pts, derivs)
pygame.display.flip()
ticker.tick(60)
pygame.quit()
sys.exit()Почему сортировка по углу и оболочки здесь не работают
Подходы на основе углов сортируют точки по полярному углу вокруг центроида или выбранного начала. Для многих вогнутых форм это ведёт к самопересечениям: угловой обход перескакивает через фигуру. Выпуклая оболочка по определению отбрасывает внутренние точки. Варианты в духе concave hull/alphashape зависят от параметра и могут законно игнорировать точки, что нарушает жёсткое требование: многоугольник обязан проходить через все заданные вершины. Ситуацию меняет наличие внутренней линии. Если известно, что эта полилиния и граница не должны пересекаться, задачу можно «распрямить» вдоль этой линии.
Ключевая идея
Используйте внутреннюю полилинию, чтобы задать для каждой вершины двумерную локальную систему координат. Для каждой пары соседних точек на полилинии берём сегмент и его середину. Для каждой граничной вершины ищем ближайшую середину сегмента и строим простой локальный базис, выровненный по этому сегменту: одна ось примерно параллельна сегменту, другая — примерно перпендикулярна ему. Проецируем вершину в этот базис и получаем две величины: продольную координату вдоль сегмента и знаковое смещение, показывающее, по какую сторону сегмента лежит точка. Эти значения объединяем в ключ сортировки так, чтобы точки по разные стороны полилинии обходились в противоположных продольных направлениях, сшивая всё в единый порядок по периметру. На практике полезно предварительно проредить внутреннюю полилинию до разумного числа точек.
Решение: векторизованное упорядочивание на NumPy
Реализация ниже принимает два входа: неупорядоченные граничные вершины и внутреннюю полилинию. На выходе — порядок индексов для многоугольника и диагностические массивы, показывающие, к середине какого сегмента «привязана» каждая вершина.
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.collections import LineCollection
def order_vertices(
verts: np.ndarray, guide: np.ndarray,
) -> tuple[
np.ndarray, # порядок индексов
np.ndarray, # середины сегментов
np.ndarray, # назначенная середина сегмента для каждой вершины
]:
# Последовательные пары сегментов вдоль направляющей
seg_pairs = np.lib.stride_tricks.sliding_window_view(guide, window_shape=2, axis=0)
midpts = seg_pairs.mean(axis=-1)
# Локальные системы для сегмента: направление вдоль и нормаль
frame = np.einsum(
'ijk,k,jmn->imn',
seg_pairs,
(-1e-4, +1e-4),
(
((1, 0),
(0, -1)),
((0, 1),
(1, 0)),
),
)
# Ближайшая середина сегмента для каждой вершины
delta = verts[:, np.newaxis] - midpts[np.newaxis]
near_idx = np.vecdot(delta, delta, axis=-1).argmin(axis=-1)
attach_midpts = midpts[near_idx]
# Проекция в локальные координаты (s, t)
s, t = np.einsum('ik,ijk->ji', verts - attach_midpts, frame[near_idx])
leftside = t > 0
# Сортировка по стороне, затем по индексу сегмента, затем по продольной координате.
# На одной стороне инвертируем направление для согласованной ориентации.
sort_keys = np.stack((s, near_idx, leftside))
sort_keys[:2, ~leftside] *= -1
return np.lexsort(sort_keys), midpts, attach_midpts
def visualize(
verts: np.ndarray, guide: np.ndarray, ordering: np.ndarray,
midpts: np.ndarray, attach_midpts: np.ndarray,
) -> plt.Figure:
fig, ax = plt.subplots()
ax.scatter(*verts.T)
ax.scatter(*midpts.T)
ax.plot(*guide.T)
ax.add_collection(LineCollection(
np.stack((attach_midpts, verts), axis=1)[ordering],
edgecolors='blue', alpha=0.2,
))
for o, (vx, vy) in enumerate(verts[ordering]):
ax.text(vx + 5, vy + 5, str(o))
return fig
def example_run() -> None:
# Пример данных
verts = np.array((
(159, 459), (133, 193), (286, 481), (241, 345),
(411, 404), (280, 349), (352, 471), (395, 361),
( 85, 390), (203, 321), ( 41, 281), ( 58, 348),
(175, 275), ( 75, 185), (385, 443), ( 44, 219),
(148, 229), (215, 477), (338, 339), (122, 430),
))
guide = np.array((
( 94, 209),
(117, 329),
(200, 400),
(287, 419),
(375, 387),
))
ordering, midpts, attach_midpts = order_vertices(verts=verts, guide=guide)
visualize(
verts=verts, guide=guide, ordering=ordering,
midpts=midpts, attach_midpts=attach_midpts,
)
plt.show()
if __name__ == '__main__':
example_run()Как это удовлетворяет ограничениям
Метод не опирается на выпуклость и не отбрасывает вершины. Внутренняя полилиния служит «каркасом», снимая двусмысленность, из‑за которой в вогнутых формах возникают самопересечения. Каждая вершина привязывается к одному сегменту направляющей через ближайшую середину и упорядочивается согласованно по обе стороны направляющей. На практике направляющая с небольшим числом точек делает привязку к сегментам и сортировку чище и стабильнее.
Почему это полезно знать
Когда у вас есть дополнительная информация — например, внутренняя линия, согласованная с внешней границей, — она может превратить кажущуюся комбинаторной задачу упорядочивания в простое преобразование координат и сортировку. Такой приём встречается в задачах следования по контуру, извлечения изолиний и реконструкции путей, где важны воспроизводимость, отсутствие подгоняемых параметров и сохранение всех данных.
Итоги
Если в данных есть полилиния внутри фигуры, подстройте порядок именно под неё. Проредите направляющую до удобного числа вершин, вычислите локальный базис для каждого сегмента, спроецируйте каждую граничную точку, получив продольную позицию и знаковое расстояние, и отсортируйте по ключу, учитывающему сторону. В результате вы получите аккуратный порядок вершин многоугольника, согласованный с внутренним ограничением и охватывающий все точки.
Статья основана на вопросе на StackOverflow от Leo и ответе Reinderien.