Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 46
Пока задачи такой не вставало, но за статью спасибо. Вдруг когда-нибудь понадобится.
не помню где, не помню когда, слышал что такая задача решается следующим образом:
из точки провести прямую и посчитать количество пересечений с границей многоугольника.
если количество пересечений четное — точка вне многоугольника.
из точки провести прямую и посчитать количество пересечений с границей многоугольника.
если количество пересечений четное — точка вне многоугольника.
провести луч (вероятно вы хотели написать)
о, да, конечно луч
Все правильно, нужно провести луч и посчитать количество пересечений, единственное, что может быть сложным — аккуратно отследить и правильно обработать все возможные случаи пересечения, а их, на сколько я помню, 5 штук.
Если вершины многоугольника заданы целочисленными координатами (или заданы по какой-то сетке), то достаточно сместить на пол-клетки исходную точку, и проводить луч уже от такой новой точки. Тогда не придется рассматривать различные случаи когда луч проходит по одной или нескольким граням многоугольника. Здесь есть еще пара нюансов в виде того, что такой проход надо делать два раза (X+0.5, X-0.5), но в целом имплементировать и тестить гораздо проще.
Такая реализация — наиболее простая.
Например, вы могли (бы) услышать про такой алгоритм из поста выше — цитирую: «запуск луча из заданной точки и подсчет числа его пересечений со сторонами многоугольника», там же чуть ниже объясняется основной недостаток этого алгоритма — его линейность…
кроме недостатков, наверное, у такого метода есть и достоинства, ведь так?
иначе выглядит безальтернативно, и значит тема могла бы быть раскрыта лучше.
иначе выглядит безальтернативно, и значит тема могла бы быть раскрыта лучше.
ну если проще, было бы здорово обзор возможных подходов в качестве вступления.
тогда можно было бы использовать статью как начальную точку отсчета при выборе инструмента
тогда можно было бы использовать статью как начальную точку отсчета при выборе инструмента
Конечно, достоинства есть — это универсальность и простота. Ситуация примерно такая, как с поиском числа в массиве. Есть универсальный метод последовательного поиска — работает медленно (на больших массивах), но всегда, а есть двоичный поиск — работает быстро, но только на упорядоченных массивах.
Основное достоинство — метод с лучом работает для произвольного многоугольника, а описанный в статье — для выпуклого.
Если многоугольник задан обходом вершин в известном направлении, то достаточно найти ближайшую к началу луча сторону, с которой этот луч пересекается. и посмотреть, в какую сторону она идет — вверх или вниз.
Все-таки многоугольник — это ломаная линия, поэтому он обычно задается именно последовательностью точек, а не набором отрезков. Максимум плохого здесь — эта линия может быть неверно ориентирована (по часовой), но эта проблема легко решается не более чем за линейное время.
Вообще говоря можно и без бинпоиска за O(N). Для _выпуклого_ многоугольника надо просто проверить, чтобы точка лежала по одинаковую сторону от каждой стороны (то бишь, N векторных произведений посчитать).
Луч уместно применять, только когда многоугольник невыпуклый, имхо, потому что там без чисел с плавающей точкой не обойтись (?).
Луч уместно применять, только когда многоугольник невыпуклый, имхо, потому что там без чисел с плавающей точкой не обойтись (?).
А не проще ли подсчитать сумму углов? Если она равна 360° то точка внутри, если 0°, то снаружи.
Странно, что в начале задачи дается задача в общем виде, потом говорится, что задача в общем виде решается за O(log2n), потом дается частное решение в случае выпуклого полигона. Нас где-то обманули.
В общем случае, для такого алгоритма требуется предварительная обработка полигона, которая производится за O(n), но только один раз.
В общем случае, для такого алгоритма требуется предварительная обработка полигона, которая производится за O(n), но только один раз.
можно ещё сделать «заливку» от заданной точки.
и проверить цвет точки, которая заведомо вне многоугольника лежит )
и проверить цвет точки, которая заведомо вне многоугольника лежит )
С меньше или равно и нулём — я бы осторожнее. Если арифметика — не целочисленная, то из-за ошибок округления всё может поехать к чОртовой матери.
Юзайте сравнения с эпсилон!
Юзайте сравнения с эпсилон!
Выпухлые полигоны — зверь редкий, но очень вкусный.
Половина современной хитрой математики определена именно что для них.
Представим что у меня есть произвольно заданный полигон без самопересечений(которые вообще можно отдетектить за nlogn)
Что же делать?
И тут нам на помощь приходят монотоны
За O(n) вы находите сегменты линии монотонные по Y( y либо растет либо убывает, в общем не меняет знак производной)
Далее можно отработать по старинке — пустить луч из точки и считать пересечения.
Но монотоны это отсортированная последовательность, и нужный сегмент для тестирования можно найти за O(logn) — поиском делением пополам.
И из всего набора отрезков проверять только нужные.
Можно отработать местами еще хитрее, но о них не буду рассказывать пока не прочитаю что там за ссылкой в самом топике скрыто…
Половина современной хитрой математики определена именно что для них.
Представим что у меня есть произвольно заданный полигон без самопересечений(которые вообще можно отдетектить за nlogn)
Что же делать?
И тут нам на помощь приходят монотоны
За O(n) вы находите сегменты линии монотонные по Y( y либо растет либо убывает, в общем не меняет знак производной)
Далее можно отработать по старинке — пустить луч из точки и считать пересечения.
Но монотоны это отсортированная последовательность, и нужный сегмент для тестирования можно найти за O(logn) — поиском делением пополам.
И из всего набора отрезков проверять только нужные.
Можно отработать местами еще хитрее, но о них не буду рассказывать пока не прочитаю что там за ссылкой в самом топике скрыто…
Интересно… Однако, вопрос: какие будут монотоны вот для такого многоугольника (и сколько их будет)?
хренова тут будет.
Выкручиваемся двумя способами — либо через теже самые монотоны или BSP бьем на конвексы, и работаем как в топике и сказано.
Либо поднимаем «spatial bullets» они же grid — но построение такой структуры относительно дорогое.
Вот для данного примера — оно смысла вообще не имеет — быстрее 50 раз проверить в лоб чем построить этот справочник и гонять по чему почти что за O(1)
Выкручиваемся двумя способами — либо через теже самые монотоны или BSP бьем на конвексы, и работаем как в топике и сказано.
Либо поднимаем «spatial bullets» они же grid — но построение такой структуры относительно дорогое.
Вот для данного примера — оно смысла вообще не имеет — быстрее 50 раз проверить в лоб чем построить этот справочник и гонять по чему почти что за O(1)
Хорошее оформление статьи, очень наглядно.
ЭЭЭ.
Достаточно провести любую прямую через точку А.
Если кол-во пересечений луча с многоугольником нечетно — то внутри.
Если кол-во пересечений луча с многоугольником 0 или четно — то снаружи.
Достаточно провести любую прямую через точку А.
Если кол-во пересечений луча с многоугольником нечетно — то внутри.
Если кол-во пересечений луча с многоугольником 0 или четно — то снаружи.
Простите, а как вы будете искать точки пересечения, например?
А как у вас задан многоугольник?
В виде функции, системы функций? или последовательности координат вершин многоугольника? :)
Для второго случая выполним пересечение двух прямых (одна из них наша прямая, а вторая — образавана из двух вершин многоугольника), в результате, если прямые не параллельны, получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось X и на ось Y.
Это самый универсальный способ.
Перед ним можно сделать проверки, чтоб отсеять явно не пересекающие стороны многоугольника.
В виде функции, системы функций? или последовательности координат вершин многоугольника? :)
Для второго случая выполним пересечение двух прямых (одна из них наша прямая, а вторая — образавана из двух вершин многоугольника), в результате, если прямые не параллельны, получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось X и на ось Y.
Это самый универсальный способ.
Перед ним можно сделать проверки, чтоб отсеять явно не пересекающие стороны многоугольника.
->в таких многоугольниках все диагонали, ведущие из нулевой вершины должны лежать внутри многоугольника:
Проще говоря, точки должны быть не только отсортированы по углу, еще и порядок обхода этих точек должен совпадать с этой сортировкой.
Кстати, этот метод преподается(вался) в политехе. Так же, как и всякие интерполяции сплайнами, методы наименьших квадратов и т.п.
Проще говоря, точки должны быть не только отсортированы по углу, еще и порядок обхода этих точек должен совпадать с этой сортировкой.
Кстати, этот метод преподается(вался) в политехе. Так же, как и всякие интерполяции сплайнами, методы наименьших квадратов и т.п.
Если у нас один (невыпуклый) многоугольник и много запросов принадлежности точки, то задача решается за O(log(N)) на запрос плюс O(N^2*log(N)) на предвычисления (и O(N^2) памяти): режем плоскость на горизонтальные полосы линиями, проходящими через вершины, и для каждой полосы перечисляем стороны многоугольника (слева направо), которые эту полосу пересекают. Задача решается двумя бинарными поисками: по координате y находим полосу, а потом — по (x,y) находим положение точки в этой полосе.
bin, кстати надо будет его попробовать.
Только почему предвычисления N^2*log(N)
Только почему предвычисления 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)), и какой должна быть структура представления многоугольника, укладывающаяся в такую память.
Вероятно, можно воспользоваться тем, что при переходе от одной полосы к другой последовательность сторон меняется только в одном месте. При использовании простых вставок время получится O(N^2). Интересно, можно ли довести его на 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
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Локализация точки в выпуклом многоугольнике