Comments 46
Пока задачи такой не вставало, но за статью спасибо. Вдруг когда-нибудь понадобится.
0
не помню где, не помню когда, слышал что такая задача решается следующим образом:
из точки провести прямую и посчитать количество пересечений с границей многоугольника.
если количество пересечений четное — точка вне многоугольника.
из точки провести прямую и посчитать количество пересечений с границей многоугольника.
если количество пересечений четное — точка вне многоугольника.
+11
провести луч (вероятно вы хотели написать)
+2
о, да, конечно луч
+2
Все правильно, нужно провести луч и посчитать количество пересечений, единственное, что может быть сложным — аккуратно отследить и правильно обработать все возможные случаи пересечения, а их, на сколько я помню, 5 штук.
0
Если вершины многоугольника заданы целочисленными координатами (или заданы по какой-то сетке), то достаточно сместить на пол-клетки исходную точку, и проводить луч уже от такой новой точки. Тогда не придется рассматривать различные случаи когда луч проходит по одной или нескольким граням многоугольника. Здесь есть еще пара нюансов в виде того, что такой проход надо делать два раза (X+0.5, X-0.5), но в целом имплементировать и тестить гораздо проще.
0
Такая реализация — наиболее простая.
+1
Например, вы могли (бы) услышать про такой алгоритм из поста выше — цитирую: «запуск луча из заданной точки и подсчет числа его пересечений со сторонами многоугольника», там же чуть ниже объясняется основной недостаток этого алгоритма — его линейность…
+4
кроме недостатков, наверное, у такого метода есть и достоинства, ведь так?
иначе выглядит безальтернативно, и значит тема могла бы быть раскрыта лучше.
иначе выглядит безальтернативно, и значит тема могла бы быть раскрыта лучше.
+1
ну если проще, было бы здорово обзор возможных подходов в качестве вступления.
тогда можно было бы использовать статью как начальную точку отсчета при выборе инструмента
тогда можно было бы использовать статью как начальную точку отсчета при выборе инструмента
0
Конечно, достоинства есть — это универсальность и простота. Ситуация примерно такая, как с поиском числа в массиве. Есть универсальный метод последовательного поиска — работает медленно (на больших массивах), но всегда, а есть двоичный поиск — работает быстро, но только на упорядоченных массивах.
+1
Основное достоинство — метод с лучом работает для произвольного многоугольника, а описанный в статье — для выпуклого.
0
Если многоугольник задан обходом вершин в известном направлении, то достаточно найти ближайшую к началу луча сторону, с которой этот луч пересекается. и посмотреть, в какую сторону она идет — вверх или вниз.
0
UFO just landed and posted this here
Все-таки многоугольник — это ломаная линия, поэтому он обычно задается именно последовательностью точек, а не набором отрезков. Максимум плохого здесь — эта линия может быть неверно ориентирована (по часовой), но эта проблема легко решается не более чем за линейное время.
+3
Вообще говоря можно и без бинпоиска за O(N). Для _выпуклого_ многоугольника надо просто проверить, чтобы точка лежала по одинаковую сторону от каждой стороны (то бишь, N векторных произведений посчитать).
Луч уместно применять, только когда многоугольник невыпуклый, имхо, потому что там без чисел с плавающей точкой не обойтись (?).
Луч уместно применять, только когда многоугольник невыпуклый, имхо, потому что там без чисел с плавающей точкой не обойтись (?).
0
А не проще ли подсчитать сумму углов? Если она равна 360° то точка внутри, если 0°, то снаружи.
0
Можно и так, но это 1) опять-таки будет линейно, 2) требует применения тригонометрических функций, которые в отличие от арифметики вычисляются очень и очень долго.
0
Странно, что в начале задачи дается задача в общем виде, потом говорится, что задача в общем виде решается за O(log2n), потом дается частное решение в случае выпуклого полигона. Нас где-то обманули.
В общем случае, для такого алгоритма требуется предварительная обработка полигона, которая производится за O(n), но только один раз.
В общем случае, для такого алгоритма требуется предварительная обработка полигона, которая производится за O(n), но только один раз.
+5
можно ещё сделать «заливку» от заданной точки.
и проверить цвет точки, которая заведомо вне многоугольника лежит )
и проверить цвет точки, которая заведомо вне многоугольника лежит )
0
С меньше или равно и нулём — я бы осторожнее. Если арифметика — не целочисленная, то из-за ошибок округления всё может поехать к чОртовой матери.
Юзайте сравнения с эпсилон!
Юзайте сравнения с эпсилон!
+2
Выпухлые полигоны — зверь редкий, но очень вкусный.
Половина современной хитрой математики определена именно что для них.
Представим что у меня есть произвольно заданный полигон без самопересечений(которые вообще можно отдетектить за nlogn)
Что же делать?
И тут нам на помощь приходят монотоны
За O(n) вы находите сегменты линии монотонные по Y( y либо растет либо убывает, в общем не меняет знак производной)
Далее можно отработать по старинке — пустить луч из точки и считать пересечения.
Но монотоны это отсортированная последовательность, и нужный сегмент для тестирования можно найти за O(logn) — поиском делением пополам.
И из всего набора отрезков проверять только нужные.
Можно отработать местами еще хитрее, но о них не буду рассказывать пока не прочитаю что там за ссылкой в самом топике скрыто…
Половина современной хитрой математики определена именно что для них.
Представим что у меня есть произвольно заданный полигон без самопересечений(которые вообще можно отдетектить за nlogn)
Что же делать?
И тут нам на помощь приходят монотоны
За O(n) вы находите сегменты линии монотонные по Y( y либо растет либо убывает, в общем не меняет знак производной)
Далее можно отработать по старинке — пустить луч из точки и считать пересечения.
Но монотоны это отсортированная последовательность, и нужный сегмент для тестирования можно найти за O(logn) — поиском делением пополам.
И из всего набора отрезков проверять только нужные.
Можно отработать местами еще хитрее, но о них не буду рассказывать пока не прочитаю что там за ссылкой в самом топике скрыто…
+1
Интересно… Однако, вопрос: какие будут монотоны вот для такого многоугольника (и сколько их будет)?


0
хренова тут будет.
Выкручиваемся двумя способами — либо через теже самые монотоны или BSP бьем на конвексы, и работаем как в топике и сказано.
Либо поднимаем «spatial bullets» они же grid — но построение такой структуры относительно дорогое.
Вот для данного примера — оно смысла вообще не имеет — быстрее 50 раз проверить в лоб чем построить этот справочник и гонять по чему почти что за O(1)
Выкручиваемся двумя способами — либо через теже самые монотоны или BSP бьем на конвексы, и работаем как в топике и сказано.
Либо поднимаем «spatial bullets» они же grid — но построение такой структуры относительно дорогое.
Вот для данного примера — оно смысла вообще не имеет — быстрее 50 раз проверить в лоб чем построить этот справочник и гонять по чему почти что за O(1)
+1
Хорошее оформление статьи, очень наглядно.
0
ЭЭЭ.
Достаточно провести любую прямую через точку А.
Если кол-во пересечений луча с многоугольником нечетно — то внутри.
Если кол-во пересечений луча с многоугольником 0 или четно — то снаружи.
Достаточно провести любую прямую через точку А.
Если кол-во пересечений луча с многоугольником нечетно — то внутри.
Если кол-во пересечений луча с многоугольником 0 или четно — то снаружи.
0
Простите, а как вы будете искать точки пересечения, например?
0
А как у вас задан многоугольник?
В виде функции, системы функций? или последовательности координат вершин многоугольника? :)
Для второго случая выполним пересечение двух прямых (одна из них наша прямая, а вторая — образавана из двух вершин многоугольника), в результате, если прямые не параллельны, получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось X и на ось Y.
Это самый универсальный способ.
Перед ним можно сделать проверки, чтоб отсеять явно не пересекающие стороны многоугольника.
В виде функции, системы функций? или последовательности координат вершин многоугольника? :)
Для второго случая выполним пересечение двух прямых (одна из них наша прямая, а вторая — образавана из двух вершин многоугольника), в результате, если прямые не параллельны, получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось X и на ось Y.
Это самый универсальный способ.
Перед ним можно сделать проверки, чтоб отсеять явно не пересекающие стороны многоугольника.
0
->в таких многоугольниках все диагонали, ведущие из нулевой вершины должны лежать внутри многоугольника:
Проще говоря, точки должны быть не только отсортированы по углу, еще и порядок обхода этих точек должен совпадать с этой сортировкой.
Кстати, этот метод преподается(вался) в политехе. Так же, как и всякие интерполяции сплайнами, методы наименьших квадратов и т.п.
Проще говоря, точки должны быть не только отсортированы по углу, еще и порядок обхода этих точек должен совпадать с этой сортировкой.
Кстати, этот метод преподается(вался) в политехе. Так же, как и всякие интерполяции сплайнами, методы наименьших квадратов и т.п.
0
Если у нас один (невыпуклый) многоугольник и много запросов принадлежности точки, то задача решается за O(log(N)) на запрос плюс O(N^2*log(N)) на предвычисления (и O(N^2) памяти): режем плоскость на горизонтальные полосы линиями, проходящими через вершины, и для каждой полосы перечисляем стороны многоугольника (слева направо), которые эту полосу пересекают. Задача решается двумя бинарными поисками: по координате y находим полосу, а потом — по (x,y) находим положение точки в этой полосе.
+1
bin, кстати надо будет его попробовать.
Только почему предвычисления N^2*log(N)
Только почему предвычисления N^2*log(N)
0
Я не очень думал над алгоритмом предвычисления. Первое, что пришло в голову — сортируем 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)), и какой должна быть структура представления многоугольника, укладывающаяся в такую память.
+1
Я для каждого многоугольника вычисляю «коробку», т.е. две пары максимальных-минимальных координат. Если искомая точка не лежит между ними, то вычислять многоугольник не имеет смысла.
0
Спасибо за статью. Немного только не понял, разве нужно использовать полноценный 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
0
Only those users with full accounts are able to leave comments. Log in, please.
Локализация точки в выпуклом многоугольнике