Pull to refresh

Comments 46

Пока задачи такой не вставало, но за статью спасибо. Вдруг когда-нибудь понадобится.
не помню где, не помню когда, слышал что такая задача решается следующим образом:
из точки провести прямую и посчитать количество пересечений с границей многоугольника.
если количество пересечений четное — точка вне многоугольника.
провести луч (вероятно вы хотели написать)
Все правильно, нужно провести луч и посчитать количество пересечений, единственное, что может быть сложным — аккуратно отследить и правильно обработать все возможные случаи пересечения, а их, на сколько я помню, 5 штук.
Если вершины многоугольника заданы целочисленными координатами (или заданы по какой-то сетке), то достаточно сместить на пол-клетки исходную точку, и проводить луч уже от такой новой точки. Тогда не придется рассматривать различные случаи когда луч проходит по одной или нескольким граням многоугольника. Здесь есть еще пара нюансов в виде того, что такой проход надо делать два раза (X+0.5, X-0.5), но в целом имплементировать и тестить гораздо проще.
Не всегда все задано так, как вы говорите.
Такая реализация — наиболее простая.
Например, вы могли (бы) услышать про такой алгоритм из поста выше — цитирую: «запуск луча из заданной точки и подсчет числа его пересечений со сторонами многоугольника», там же чуть ниже объясняется основной недостаток этого алгоритма — его линейность…
кроме недостатков, наверное, у такого метода есть и достоинства, ведь так?
иначе выглядит безальтернативно, и значит тема могла бы быть раскрыта лучше.
ну если проще, было бы здорово обзор возможных подходов в качестве вступления.
тогда можно было бы использовать статью как начальную точку отсчета при выборе инструмента
Было бы здорово, я согласен, но это требует существенно большего времени на подготовку и написание. Основной же тезис данного поста — чисто математическая задача при больших количествах параметров становится объектом теории алгоритмов.
Конечно, достоинства есть — это универсальность и простота. Ситуация примерно такая, как с поиском числа в массиве. Есть универсальный метод последовательного поиска — работает медленно (на больших массивах), но всегда, а есть двоичный поиск — работает быстро, но только на упорядоченных массивах.
На правах оффтопа -> а еще есть хеш-тейблы, которые работают еще быстрее, с высокой вероятностью за одну итерацию, но в отличие от двоичного поиска, ищут только совпадения, не могут найти ближайшее меньшее/большее.
Основное достоинство — метод с лучом работает для произвольного многоугольника, а описанный в статье — для выпуклого.
Если многоугольник задан обходом вершин в известном направлении, то достаточно найти ближайшую к началу луча сторону, с которой этот луч пересекается. и посмотреть, в какую сторону она идет — вверх или вниз.
UFO just landed and posted this here
Все-таки многоугольник — это ломаная линия, поэтому он обычно задается именно последовательностью точек, а не набором отрезков. Максимум плохого здесь — эта линия может быть неверно ориентирована (по часовой), но эта проблема легко решается не более чем за линейное время.
Вообще говоря можно и без бинпоиска за O(N). Для _выпуклого_ многоугольника надо просто проверить, чтобы точка лежала по одинаковую сторону от каждой стороны (то бишь, N векторных произведений посчитать).

Луч уместно применять, только когда многоугольник невыпуклый, имхо, потому что там без чисел с плавающей точкой не обойтись (?).
Нет, можно обойтись целочисленной арифметикой (при условии, что координаты являются целыми), используя функцию типа intersect, определенную выше. Главная проблема там — учет всяких граничных состояний, но тоже все решается целочисленно.
А не проще ли подсчитать сумму углов? Если она равна 360° то точка внутри, если 0°, то снаружи.
Можно и так, но это 1) опять-таки будет линейно, 2) требует применения тригонометрических функций, которые в отличие от арифметики вычисляются очень и очень долго.
В книге Никулина Е. А. «Компьютерная геометрия и алгоритмы машинной графики» приведен угловой тест с использованием октантов, отпадает необходимость использования тригонометрических функций.
Странно, что в начале задачи дается задача в общем виде, потом говорится, что задача в общем виде решается за O(log2n), потом дается частное решение в случае выпуклого полигона. Нас где-то обманули.

В общем случае, для такого алгоритма требуется предварительная обработка полигона, которая производится за O(n), но только один раз.
Нас где-то обманули
если только чуть-чуть :)
можно ещё сделать «заливку» от заданной точки.
и проверить цвет точки, которая заведомо вне многоугольника лежит )
Заливка может производится если есть массив пикселов. Полигон же может быть с любыми сторонами, даже меньше одного пиксела в длине.
хм. в таком разрезе — да.
спасибо за поправку
С меньше или равно и нулём — я бы осторожнее. Если арифметика — не целочисленная, то из-за ошибок округления всё может поехать к чОртовой матери.

Юзайте сравнения с эпсилон!
Моя оплошность — не указал явно, что все координаты предполагаются целыми. Для вещественных чисел, конечно, все будет не так шоколадно…
Выпухлые полигоны — зверь редкий, но очень вкусный.
Половина современной хитрой математики определена именно что для них.
Представим что у меня есть произвольно заданный полигон без самопересечений(которые вообще можно отдетектить за nlogn)
Что же делать?
И тут нам на помощь приходят монотоны
За O(n) вы находите сегменты линии монотонные по Y( y либо растет либо убывает, в общем не меняет знак производной)
Далее можно отработать по старинке — пустить луч из точки и считать пересечения.
Но монотоны это отсортированная последовательность, и нужный сегмент для тестирования можно найти за O(logn) — поиском делением пополам.
И из всего набора отрезков проверять только нужные.
Можно отработать местами еще хитрее, но о них не буду рассказывать пока не прочитаю что там за ссылкой в самом топике скрыто…
Интересно… Однако, вопрос: какие будут монотоны вот для такого многоугольника (и сколько их будет)?
хренова тут будет.
Выкручиваемся двумя способами — либо через теже самые монотоны или BSP бьем на конвексы, и работаем как в топике и сказано.
Либо поднимаем «spatial bullets» они же grid — но построение такой структуры относительно дорогое.
Вот для данного примера — оно смысла вообще не имеет — быстрее 50 раз проверить в лоб чем построить этот справочник и гонять по чему почти что за O(1)
Ага, вот и у меня такое же чувство :) Кажется, что это плохой пример для всех быстрых методов…
ЭЭЭ.

Достаточно провести любую прямую через точку А.
Если кол-во пересечений луча с многоугольником нечетно — то внутри.
Если кол-во пересечений луча с многоугольником 0 или четно — то снаружи.
Простите, а как вы будете искать точки пересечения, например?
А как у вас задан многоугольник?
В виде функции, системы функций? или последовательности координат вершин многоугольника? :)

Для второго случая выполним пересечение двух прямых (одна из них наша прямая, а вторая — образавана из двух вершин многоугольника), в результате, если прямые не параллельны, получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось X и на ось Y.

Это самый универсальный способ.
Перед ним можно сделать проверки, чтоб отсеять явно не пересекающие стороны многоугольника.
O(n) — чего и требуется избежать
->в таких многоугольниках все диагонали, ведущие из нулевой вершины должны лежать внутри многоугольника:
Проще говоря, точки должны быть не только отсортированы по углу, еще и порядок обхода этих точек должен совпадать с этой сортировкой.
Кстати, этот метод преподается(вался) в политехе. Так же, как и всякие интерполяции сплайнами, методы наименьших квадратов и т.п.
Если у нас один (невыпуклый) многоугольник и много запросов принадлежности точки, то задача решается за O(log(N)) на запрос плюс O(N^2*log(N)) на предвычисления (и O(N^2) памяти): режем плоскость на горизонтальные полосы линиями, проходящими через вершины, и для каждой полосы перечисляем стороны многоугольника (слева направо), которые эту полосу пересекают. Задача решается двумя бинарными поисками: по координате y находим полосу, а потом — по (x,y) находим положение точки в этой полосе.
bin, кстати надо будет его попробовать.
Только почему предвычисления N^2*log(N)
Я не очень думал над алгоритмом предвычисления. Первое, что пришло в голову — сортируем y-координаты (N*log(N) операций), получаем границы полос. Для каждой полосы (их N+1) ищем точки пересечения «средней линии» со всеми сторонами (общее время всего O(N^2), и в худшем случае — когда наш многоугольник закручен в спираль — получается O(N^2) точек пересечения), а потом сортируем эти точки для каждой полосы (общее время в худшем случае — как раз O(N^2*log(N)).
Вероятно, можно воспользоваться тем, что при переходе от одной полосы к другой последовательность сторон меняется только в одном месте. При использовании простых вставок время получится O(N^2). Интересно, можно ли довести его на O(N*log(N)), и какой должна быть структура представления многоугольника, укладывающаяся в такую память.
Если K запросов на принадлежность точки известны заранее, то ответить на них можно за O(K*log(K)+N*log(N)). А заодно получается алгоритм, позволяющий за O(N*log(N)) проверить, есть ли у замкнутой ломаной самопересечения. Память в обоих случаях линейна.
Я для каждого многоугольника вычисляю «коробку», т.е. две пары максимальных-минимальных координат. Если искомая точка не лежит между ними, то вычислять многоугольник не имеет смысла.

Спасибо за статью. Немного только не понял, разве нужно использовать полноценный intersect в этой задаче? Поскольку точка B лежит в угле CAD (он же PrPoPp), то эта часть intersect кажется всегда будет выполняться: rotate(A,B,C)*rotate(A,B,D)<=0

Тоесть достаточно проверить только то, что точки Po и A лежат по разные стороны от прямой PrPp: rotate(C,D,A)*rotate(C,D,B)<0

Only those users with full accounts are able to leave comments. Log in, please.

Articles