|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 28 Nov 2001 02:36:46
To : Nikita Golovachev
Subject : Re: Многоугольник и точка
--------------------------------------------------------------------------------
"Nikita Golovachev" <Nikita.Golovachev@p72.f1.n5095.z2.fidonet.org> wrote in
message news:1006623065@p72.f1.n5095.z2.ftn...
> Извиняюсь, если эта задачка всем уже надоела, но очень нужно.
> Задан многоугольник (кооpдинатами веpшин) и некотоpая точка.
Имеется в виду, что еще известно как эти вершины связаны.
> Hужно опpеделить пpинадлежит ли эта точка многоугольнику.
Из точки проводится луч, например, горизонтально,
и считается количество пересечений со сторонами многоугольника,
причем, если сторона пересекает луч точно концом, то пересечение
учитывается только в том случае, если второй конец лежит, например,
ниже луча. Если пересечений нечетное число, то точка внутри.
Остается проблема попадания точно на границу, или в угол,
все легко находится и проверяется в ходе алгоритма,
но надо определиться, считать это принадлежностью или нет.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
