Comments 23
Есть хорошая статья Kai Hormann, Alexander Agathos "The Point in Polygon Problem for Arbitrary Polygons", в которой показано, что по сути метод трассировки луча и метод, основанный на индексе точки — это практически одно и то же. Там же в статье описано то, как коротко и ясно разбираются абсолютно все крайние случаи для совершенно любых вариантов многоугольников (не помню только, что там насчёт вырожденных).
Спасибо за ссылку! Ну с теоретической точки зрения все-таки индекс точки и трассировка лучей — не одно и то же. Насколько я вижу, Каи Хорманн показывает, что можно свести процесс к трассировке, но с помощью нее он пытается решить именно проблему поиска индекса точки. Да, он показывает что можно избежать обратных тригонометрических функций. Но в отличие от трассировки сложность у него все-таки O(n).
И вырожденные случаи он тоже не учитывает. Но вырожденные случаи — это вообще особенная песня. Мой любимый пример, который не может нормально обработать почти ни один алгоритм: берем окружность, приближаем ее ломаной линией состоящий из миллиона (или больше) отрезков. В результате ребра многоугольника получаются настолько маленькие, что трассировка попадает в вершины и выдает множество неверных ответов, нормали из-за числовых погрешностей смотрят куда угодно, индекс точки выдает шум.
И вырожденные случаи он тоже не учитывает. Но вырожденные случаи — это вообще особенная песня. Мой любимый пример, который не может нормально обработать почти ни один алгоритм: берем окружность, приближаем ее ломаной линией состоящий из миллиона (или больше) отрезков. В результате ребра многоугольника получаются настолько маленькие, что трассировка попадает в вершины и выдает множество неверных ответов, нормали из-за числовых погрешностей смотрят куда угодно, индекс точки выдает шум.
Во-вторых, для вычисления угла придётся воспользоваться операцией арккосинуса и двумя операциями взятия корня (формула скалярного произведения и связь его с углом тем в помощь, кто не понимает, почему). Эти операции очень недешевы с точки зрения скорости, и, к тому же, погрешности связанные с ними могут быть существенны.
Ну, это два раза не совсем правда. Для определения угла можно использовать формулу
atan2( векторное произвдение, скалярное произведение)
(Если вектора (a,b) и (x,y), то получится atan2(ay-bx, ax+by)).
То есть всего одна обратная тригонометрическая функция.
Кроме того, не так уж важна точность. В идеале в сумме получится либо 0, либо 2π, либо -2π. В реальность будет ошибка, но чтобы накопилось π ошибки,
А вот с O(n) действительно ничего не сделаешь.
Первый аргумент atan2 — это же число, и значит без квадратного корня для длины вектора не обойтись. То есть да, чуть получше.
А вот насчет точность не важна — это вопрос интересный и в чем-то даже философский. Потому что найдутся приложения, в которых независимо от того, что подано на вход, хочется иметь гарантированный выход. Если у нас сумма между 0 и 2π, можно округлить до ближайшего, но будет ли этого достаточно? Особенно если у нас точка находится близко к ребру, а многоугольник не очень хороший.
Да, должно «очень сильно не повезти». И в итоге не везет именно тогда, когда этого совсем не ожидаешь.
А вот насчет точность не важна — это вопрос интересный и в чем-то даже философский. Потому что найдутся приложения, в которых независимо от того, что подано на вход, хочется иметь гарантированный выход. Если у нас сумма между 0 и 2π, можно округлить до ближайшего, но будет ли этого достаточно? Особенно если у нас точка находится близко к ребру, а многоугольник не очень хороший.
Да, должно «очень сильно не повезти». И в итоге не везет именно тогда, когда этого совсем не ожидаешь.
Есть такая замечательная библиотека под именем Common Graphics Algorithms (CGAL). А в библиотеке есть функция bounded_side_2
Если полистать исходники — то можно понять как обрабатывать все граничные ситуации первого алгоритма.
Если полистать исходники — то можно понять как обрабатывать все граничные ситуации первого алгоритма.
Угол можно вычислять так: atan2(, ). Интересно было бы сравнить производительность.
Все в этих математиках хорошо, но 99.99% реализаций (которые я видел) не содержат оптимизации через деревья. В том числе из-за того что время подготовки данных сильно больше времени работы самого алгоритма по наивному варианту.
Снижаем асимптотику, увеличиваем константный множитель :)
Вопрос в том, для скольких точек надо считать принадлежность и какой вход. Если, например, у нас миллион точек/ребер в исходном многоугольнике, то возможно подготовка дерева и работа алгоритма будут быстрее, чем алгоритм с проходом по всем точкам/ребрам.
Это как бы понятно. Можно еще учитывать что данные можно готовить чуть раньше и в другом треде, так чтобы к моменту сравнения именно сравнение быстрее сработало, даже если один раз.
Но жалуюсь я на то, что именно реализаций и не заметно – гуглинг типа «BHV point in polygon» ничего не дает. Мухи и котлеты — отдельно.
В Q/B/BSP деревья для данной задачи я не верю. И в BHV тоже не верю — тут капсули нужны, а не волумы.
Но жалуюсь я на то, что именно реализаций и не заметно – гуглинг типа «BHV point in polygon» ничего не дает. Мухи и котлеты — отдельно.
В Q/B/BSP деревья для данной задачи я не верю. И в BHV тоже не верю — тут капсули нужны, а не волумы.
-1 означает что мы внутри и многоугольник обходим по часовой стрелке, 0 означает что мы снаружи, +1 означает что мы снаружи
Помойму +1 означает что мы внутри и обходим многоугольник против часовой стрелки.
Помойму +1 означает что мы внутри и обходим многоугольник против часовой стрелки.
А почему бы не использовать подсчет площади:
1) Считаем площадь многоугольника (векторным произведением)
2) Считаем площади всех треугольников, которые образуются всеми двумя соседними точками многоугольника и точкой, нахождение которой мы проверяем.
3) Суммируем площади
4) Если сумма равна настоящей площади, то точка внутри или на многоугольнике, нет — снаружи
1) Считаем площадь многоугольника (векторным произведением)
2) Считаем площади всех треугольников, которые образуются всеми двумя соседними точками многоугольника и точкой, нахождение которой мы проверяем.
3) Суммируем площади
4) Если сумма равна настоящей площади, то точка внутри или на многоугольнике, нет — снаружи
Наверное это только с выпуклыми многоугольниками работать будет. Но для выпуклых и так есть более оптимальные алгоритмы.
Нет, работает для невыпуклых тоже
Согласен, будет работать, это я поспешил с выводами. Что там с вычислительной сложностью и погрешностями?
Ну и сам отвечу. На каждую точку два вычитания, два умножения и сложение. Цикл по всем точкам — О(n). Погрешность не должна быть хуже трассировки, при том, что граничные случаи автоматически учитываются. Требую от автора набор данных для теста.
А можно поподробнее? Что имменно предлагается суммировать в п.3?
просто по тексту S(п.3)=S(п.1)+S(п.2). Что такое настоящая площадь в п.4?
или по тексту просто опечатка, и там предполагается сравнение S(п.1) с S(п.2)?
Может ли быть ситуация, что суммы численно равны (допустим получается зеркальная копия многоугольника), а точка лежит снаружи?
З.Ы. про баян с закраской многоугольника чего-то не вспомнили…
просто по тексту S(п.3)=S(п.1)+S(п.2). Что такое настоящая площадь в п.4?
или по тексту просто опечатка, и там предполагается сравнение S(п.1) с S(п.2)?
Может ли быть ситуация, что суммы численно равны (допустим получается зеркальная копия многоугольника), а точка лежит снаружи?
З.Ы. про баян с закраской многоугольника чего-то не вспомнили…
UFO just landed and posted this here
Спасибо за статью! Вспомнил, что в 9 классе не смог решить задачу по информатике по определению принадлежности треугольнику)) тогда казалось непосильной задачей.
Третий метод не сработает, если точка совпадает с одной из вершин. (как такую вершину проецировать на окружность?)
Sign up to leave a comment.
Методы определения принадлежности точки многоугольнику