|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Kirill Timofeev 2:5050/144.9 11 Jun 2003 23:53:06
To : Galayko Konstantyn
Subject : Re^2: вопрос1
--------------------------------------------------------------------------------
10 июня 2003 13:46, Galayko Konstantyn писал Fedor Tereshin:
GK> У меня была подобная задача - вхождение точки в выпуклый
GK> многоугольник. Тонкостей не томню, но суть способа такова - из точки
GK> пускаю 2 вертикальных луча (вверх и вниз). И считаю кол-во пересечений
GK> с гранями (Nr, Nl). Входит, если Nr=Nl=1. Hо это в двух словах, т.к.
GK> луч может попасть в вершину (N=2), т.е. частности додумать. Я бы и
GK> куском исх. поделился, да времени нет рыться, да и было это 3 года
GK> назад.
Обобщим задачу: определить находиться ли точка внутри любого многоугольника.
Можно выпускать только один луч и считать количество пересечений со сторонами,
придётся разбирать следующие варианты:
1. Если луч пересекает вершину к счетчику прибавлять число два.
2. Если луч пересекает сторону увеличивать счетчик на еденицу.
Если счетчик чётный, то точка снаружи, иначе внутри.
Луч рекомендуется выпускать горизонтальный, так как тогда формулки попроще
будут - и нагрузка на проц уменьшится.
Сейчас не помню были ли ещё какие-нибудь условия, а придумать пример не могу,
когда это не пройдет. :(
Пока, Galayko!
... Жизнь зашибись: бьет ключом, но я пока уворачиваюсь.
--- GoldED+/W32 1.1.5-20020104
* Origin: Долой повременку! (2:5050/144.9)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
