|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Konstantin S. Rabkin 2:5020/175.2 16 Jul 2001 11:25:12
To : Kirill Volkov
Subject : Вхождение точки в произвольный многоугольник на плоскости
--------------------------------------------------------------------------------
Здрям!
Sat Jul 14 2001 12:04, Kirill Volkov wrote to All:
KV> В общем, нужен алгоритм по определению сабжа, еще лучше - несколько
KV> алгоритмов.
KV> Очень желательно, чтобы все считалось максимально быстро, поэтому лучше
KV> целочисленные вычисления, дабы не заюзывать сопроцессор (хотя если это не
KV> будет тормозить, то но проблемс).
KV> Приму с благодарностью помощь в любом виде - описания алгоритма, ссылки
KV> на инет, фак-сервера, сорцы на паскале, с, асме.
AFAIK наиболее употребительны два алгоритма:
- Метод луча. Из точки проводишь луч в любом направлении, в частности,
например горизонтальный. После чего считаешь пересечения луча со сторонами.
Если их число нечетно, то точка внутри. Особый момент - луч проходит через
вершину или сторона совпадает с лучем - обходится следующим образом - если луч
проходит через вершину - считаешь ее только тогда, когда она лежит строго выше
второй вершины ребра. Можно и строго ниже - непринципиально.
- Метод углов. Для каждого ребра считаешь угол APB, где A - начальная точка
ребра, В - конечная (ребра должны быть направлеными - задано направление
обхода полигона.), Р - твоя точка. Суммируешь все углы. Для точки снаружи
полигона сумма будет ноль, для точки внутри - два пи.
tsostik aka Zopuh. mailto: ksr@mikron.ru ICQ UIN 65436527
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Вхождение точки в произвольный многоугольник на плоскости 
