Посоветуйте алгоритм: лежит ли точка внутри многоугольника?
Я в алгоритмах не силён, но на правах КО: если многоугольник невыпуклый, а массив неупорядочен, но он может быть задан неоднозначно. Поэтому, очевидно, этого алгоритма быть не может для таких данных.
то что с ходу помню
* считается чётность пересечения рёбер с лучом пущенным из точки в произвольную сторону, есть тонкость когда луч попадает на вершину
* считается суммарная площадь всех треугольников образованных ребрами и этой вершиной и сравнивается с площадью многоугольник, афаик работает только для выпуклых многоугольников. для
невыпуклых это проверяет что-то другое.
это всё требует упорядоченности.
если мне не изменяет мой склероз в "Особенности национальных задач по информатике" была какая-то неплохая глава про такую простую вычислительную геометрию
* считается чётность пересечения рёбер с лучом пущенным из точки в произвольную сторону, есть тонкость когда луч попадает на вершину
* считается суммарная площадь всех треугольников образованных ребрами и этой вершиной и сравнивается с площадью многоугольник, афаик работает только для выпуклых многоугольников. для
невыпуклых это проверяет что-то другое.
это всё требует упорядоченности.
если мне не изменяет мой склероз в "Особенности национальных задач по информатике" была какая-то неплохая глава про такую простую вычислительную геометрию
для выпуклых можно посмотреть на совпадение всех знаков векторного произведения
для неупорядоченных достаточно проверить что интервалы между азимутами векторов из точки на вершины не больше 180 градусов. вроде чтоб это проверить не нужно полностью упорядочивать вершины.
ну да, это очевидно делается за линейное время.
ну да, это очевидно делается за линейное время.
del
вот, кстати, там у тебя в комментах дали ссылочку на статью, где разбираются эти самые тонкости, которые у тебя не упомянуты.
http://algolist.manual.ru/maths/geom/belong/poly2d.php
http://algolist.manual.ru/maths/geom/belong/poly2d.php
есть тонкость когда луч попадает на вершинуЕще луч может содержать сторону многоугольника. Если многоугольник рисуется людьми, то это вполне вероятно.
Еще луч может содержать сторону многоугольника. Если многоугольник рисуется людьми, то это вполне вероятно.да, это все просто обрабатывается, в статье на алголисте написано.
логично что в этом случае он и в вершину попадёт. даже в две. так что это часть того частного случая.
Всем спасибо. Думаю, мне подойдет алгоритм, считающий четность пересечений.
Думаю, мне подойдет алгоритм, считающий четность пересечений.Таким лучше пользоваться только для невыпуклых.
Если все же у тебя выпуклый многоугольник, то проверять принадлежность точки внутренности можно с логарифмической сложностью — если точек для проверки и сторон много, то это сильно поможет со скоростью. Идея: соединим центр масс многоугольника лучами с вершинами и получим набор секторов; двоичным поиском по полярному углу найдем сектор, в который попадает проверяемая точка, а потом посмотрим, попадает ли она в треугольник, соответствующий сектору.
центр масс многоугольникаЭто уже линейная сложность.
имеется ввиду для случая, когда поступает много запросов "лежит ли точка внутри одного и того же многоугольника?"
К тому же, похоже, подойдет любая точка внутри многоугольника. Для заведомо выпуклого такую точку можно найти за константное время.
Это уже линейная сложность.Во-первых, правильно заметил, что такой алгоритм имеет смысл для случая, когда надо для многих точек проверять их принадлежность многоугольнику, иначе меньше линейной сложности не получить — прочесть-то координаты вершин все равно надо.
Во-вторых, в указанной тобою части линейной сложности нет: чтобы делать двоичный поиск по углу, нам даром не надо знать полярные углы, под которыми видны вершины из центра масс (более того, это даже вредно ввиду того, что полярный угол хорошо определяется только на плоскости с вырезом по полуоси). Для того, чтобы делать поиск, надо только уметь отвечать на вопрос "левее или правее сектора находится точка", а это делается, исходя из знаков соответствующих ориентированных площадей.
To : да, подойдет кто угодно из внутренности или даже границы.
Оставить комментарий
onyxis
Все происходит на плоскости. Есть массив координат вершин многоугольника. Пусть будет упорядоченным, т.е. соседние элементы массива соответствуют соседним точкам многоугольника, последний элемент массива - соседний с первым. Многоугольник скорее всего выпуклый (хотя не факт). Есть ли какие-нибудь эффективные алгоритмы определения того, лежит ли точка внутри выпуклого/невыпуклого многоугольника? А также алгоритмы, не требующие упорядоченности массива точек.