Вопрос в том, для скольких точек надо считать принадлежность и какой вход. Если, например, у нас миллион точек/ребер в исходном многоугольнике, то возможно подготовка дерева и работа алгоритма будут быстрее, чем алгоритм с проходом по всем точкам/ребрам.
Первый аргумент atan2 — это же число, и значит без квадратного корня для длины вектора не обойтись. То есть да, чуть получше.
А вот насчет точность не важна — это вопрос интересный и в чем-то даже философский. Потому что найдутся приложения, в которых независимо от того, что подано на вход, хочется иметь гарантированный выход. Если у нас сумма между 0 и 2π, можно округлить до ближайшего, но будет ли этого достаточно? Особенно если у нас точка находится близко к ребру, а многоугольник не очень хороший.
Да, должно «очень сильно не повезти». И в итоге не везет именно тогда, когда этого совсем не ожидаешь.
Спасибо за ссылку! Ну с теоретической точки зрения все-таки индекс точки и трассировка лучей — не одно и то же. Насколько я вижу, Каи Хорманн показывает, что можно свести процесс к трассировке, но с помощью нее он пытается решить именно проблему поиска индекса точки. Да, он показывает что можно избежать обратных тригонометрических функций. Но в отличие от трассировки сложность у него все-таки O(n).
И вырожденные случаи он тоже не учитывает. Но вырожденные случаи — это вообще особенная песня. Мой любимый пример, который не может нормально обработать почти ни один алгоритм: берем окружность, приближаем ее ломаной линией состоящий из миллиона (или больше) отрезков. В результате ребра многоугольника получаются настолько маленькие, что трассировка попадает в вершины и выдает множество неверных ответов, нормали из-за числовых погрешностей смотрят куда угодно, индекс точки выдает шум.
А вот насчет точность не важна — это вопрос интересный и в чем-то даже философский. Потому что найдутся приложения, в которых независимо от того, что подано на вход, хочется иметь гарантированный выход. Если у нас сумма между 0 и 2π, можно округлить до ближайшего, но будет ли этого достаточно? Особенно если у нас точка находится близко к ребру, а многоугольник не очень хороший.
Да, должно «очень сильно не повезти». И в итоге не везет именно тогда, когда этого совсем не ожидаешь.
И вырожденные случаи он тоже не учитывает. Но вырожденные случаи — это вообще особенная песня. Мой любимый пример, который не может нормально обработать почти ни один алгоритм: берем окружность, приближаем ее ломаной линией состоящий из миллиона (или больше) отрезков. В результате ребра многоугольника получаются настолько маленькие, что трассировка попадает в вершины и выдает множество неверных ответов, нормали из-за числовых погрешностей смотрят куда угодно, индекс точки выдает шум.