|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 13 Jun 2003 01:06:45
To : Kirill Timofeev
Subject : Re: Re^2: вопрос1
--------------------------------------------------------------------------------
Kirill Timofeev wrote:
> Привет, Galayko!
>
> 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. Если луч пересекает сторону увеличивать счетчик на еденицу.
> Если счетчик чётный, то точка снаружи, иначе внутри.
> Луч рекомендуется выпускать горизонтальный, так как тогда формулки попроще
> будут - и нагрузка на проц уменьшится.
> Сейчас не помню были ли ещё какие-нибудь условия, а придумать пример не
> могу, когда это не пройдет. :( ...
Тут и придумывать нечего:
*----*
/ \
/ \
* A* *
\ /
\ /
*----*
Горизонтальный луч, выходящий их точки A "пересекает вершину". В результате
получаем 2 перечесения, т.е. "точка снаружи". А на само деле она внутри.
Это задача тут уже была обсосана со всех сторон много раз. Правила подсчета
пересечений для горизонтального луча такое:
Ищем точки пересечения луча с каждым из негоризонтальных ребер
многоугольника. Если точка пересечения совпадает с верхним концом ребра, то
пересечение не засчитываем. В противном случае - считаем одно пересечение.
Все.
--
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
