|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Mike Roschin 2:5030/243 31 Jan 2002 02:14:17
To : Natasha Malkovich
Subject : многоугольник
--------------------------------------------------------------------------------
щFrom Natasha Malkovich (2:5020/400) to All.
Ave Natasha Malkovich!
NM> Помогите разобраться!
NM> Hа плоскости даны точки, их координаты (xi,yi). Точки в
NM> определенной последовательности (заданной) соединены (ничего не
NM> пересекается). Получился многоугольник. Как найти, лежит ли точка T
NM> (xN, yN) внутри многоугольника и наоборот?
Первая мысль
Hайти точку, гарантировано лежащую за пределами фигуры, "провести" отрезок от
нее до точки Т и определить количество пересечений этого отрезка со сторонами
многоугольника. Если T внутри -- число пересечений будет нечетное.
Фактически надо
а) задать точку O, лежащую (допустим) правее самой правой из точек (xi,yi)
б) проверить каждый отрезок (Xi,Yi)-(Xi+1,Yi+1) на предмет пересечения с
отрезком O-T (см.сравочник по аналитической геометрии, не помню формулы)
в) проверить каждую точку (Xi,Yi) на предмет принадлежности к отрезку O-T и
вычесть это число из п.б :)
г) проверить на четность
При этом если T будет лежать на стороне многогранника, то метод покажет, что T
внутри него.
Have a fine CARRIER :) ! /White Thesis
--- FMailX32 1.60
* Origin: Слоны по деревьям не лазают! //Terminus-2 (2:5030/243)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
