FULLSTACK ENGINEERING / TECHNICAL CASE 001

ПУТЬ
ЕСТЬ?

Павел Абушкин

Иногда кратчайший путь к ответу — вообще не искать путь. Вместо пикселей и догадок — топология, точная арифметика и проверяемый код.

01 / Математика02 / Визуализация03 / Доказательства
~ N²Проверок геометрии
O(N)Доп. память
2000Макс. препятствий
КЛЮЧЕВАЯ ИДЕЯЕсть связь ВЕРХ ↔ НИЗ → нет пути ЛЕВО ↔ ПРАВО↘
ИНЖЕНЕРНЫЙ ПОДХОД / ПАВЕЛ АБУШКИН

НЕ ИСКАТЬ
ПУТЬ.
ДОКАЗАТЬ
ВОЗМОЖНОСТЬ.

Я перевёл задачу поиска маршрута в проверку связности препятствий. Вместо перебора траекторий алгоритм выясняет, появилась ли непрерывная цепочка кругов от верхней границы прямоугольника до нижней.

Важны не только скорость и верный ответ, но и граничные случаи: касания, внешние центры и пересечения за пределами прямоугольника. Поэтому геометрические проверки выполняются точно, а четыре алгоритма можно сравнить на одних данных.

01 / МОДЕЛЬИз геометрии — в граф
02 / ТОЧНОСТЬЦелые числа, без epsilon
03 / ПРОВЕРКАТесты и воспроизводимые сценарии
ПРОВЕРИТЬ РЕШЕНИЕ ВЖИВУЮ
01 / INTERACTIVE EXPERIMENT

ГЕОМЕТРИЯ В ДВИЖЕНИИ.

Перетаскивайте круги, меняйте радиусы, переключайте алгоритмы и наблюдайте, как вычисление превращается в доказательство.

LIVE GEOMETRY ENGINE / 10 × 10
RECT [0, 0, 10, 10]
Волна от касания · Круги можно перемещать
Y ↑
Препятствие Граф Пример пути
ПРЕДИКАТ: ТОЧНЫЙ
ПОШАГОВЫЙ РАЗБОР

Исходные координаты и круги.

01 / 04

Важно: True/False рассчитывается точной целочисленной геометрией. Линия найденного маршрута — дополнительная дискретная иллюстрация (A* + проверка отрезков), а не часть доказательства; узкая допустимая дорожка может не отобразиться на сетке.

02 / FOUR VALID STRATEGIES

НЕ ОДИН АЛГОРИТМ.

Четыре способа анализа одной геометрической задачи — от обхода графа до пространственного отсечения. Переключатели выполняют реальный код.

01 / PREFERRED↗

DISJOINT
SET UNION

Связываем пересекающиеся части кругов и границы TOP/BOTTOM. Ранний выход, если они оказались в одной компоненте.

Время O(N² α(N)) АмортизированноПамять O(N)
02 / TRAVERSAL→

BREADTH
FIRST SEARCH

Начинаем со всех кругов, касающихся верхней стороны, и проверяем достижимость нижней. Перебор соседей — по запросу.

Время O(N²)Память O(N)
03 / TRAVERSAL↘

DEPTH
FIRST SEARCH

Тот же геометрический граф, но поиск в глубину. Удобно для сравнения порядка исследования и проверки связности.

Время O(N²)Память O(N)
04 / SPATIAL PRUNING⌁

SWEEP
LINE

Сортируем круги по X и отбрасываем пары с заведомо несовместимыми проекциями. На оставшихся работает тот же точный предикат и DSU.

Время O(N² α(N))Память O(N)
WHY IT WORKS / 01

ТОПОЛОГИЯ,
НЕ ПОДБОР ТОЧЕК.

Для конечного набора замкнутых дисков в прямоугольнике отсутствие пути от левой стороны к правой эквивалентно существованию связной цепочки препятствий от верхней стороны до нижней.

⌁
WHY IT WORKS / 02

ПЕРЕСЕЧЕНИЕ
ТОЛЬКО ВНУТРИ.

Два полных круга могут касаться за пределами области. Поэтому проверяем не просто distance ≤ r₁ + r₂, а непустоту D₁ ∩ D₂ ∩ R с целочисленными сравнениями — без округления и epsilon.

DISK ∩ DISK ∩ RECT ≠ ∅
03 / INSPECT THE IMPLEMENTATION

КОД БЕЗ ФОКУСОВ.

Python с произвольной точностью целых; TypeScript и JavaScript с BigInt. Исходный код можно копировать и запускать отдельно.

python/pathfinding.pySTRICT GEOMETRY / OPEN SOURCE
04 / VERIFY, DON'T TRUST

ТЕСТИРУЕМ ГРАНИЦЫ.

Проверяются исходные примеры и случаи, в которых наивные реализации обычно ломаются: касания, нулевой радиус, внешние центры и большие числа.

BROWSER ACCEPTANCE SUITE
0 / 0
ПРОЕКТ СОБРАН КАК ИССЛЕДОВАНИЕ

НЕ ПРОСТО TRUE / FALSE.
А ПОЧЕМУ.

НАВЕРХ ↑

РЕДАКТОР ВХОДНЫХ ДАННЫХ

Введите координаты прямоугольника и массив кругов. Только целые числа (для визуального редактора — безопасный диапазон JavaScript).