|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 28 Nov 2001 22:03:43
To : Nikita Golovachev
Subject : Re: Многоугольник и точка
--------------------------------------------------------------------------------
"Nikita Golovachev" <Nikita.Golovachev@p72.f1.n5095.z2.fidonet.org> wrote in
message news:1006937066@p72.f1.n5095.z2.ftn...
> RI> Обходишь вектором из точки по контуру.
> RI> Если внутри, то вектор обойдет полный круг 2pi, если
> RI> вне - то неполный.
ИМХО проверяется _суммарный_ пройденный угол с учетом
направления, а именно идем пр часовой стрелке - прибавляем,
идем против - вычитаем. Этот угол всегда кратен 2pi, поскольку
вернулись в ту же точку границы, т.е. равен 2Npi.
Если N - нечетное, то точка внутри, если четное - то наружи.
О точках на границе - вопрос отдельный.
> RI> Хотя для сильно извратных частных случаев не работает.
>
> Hапример, как быть с самопересекающимися многоугольниками - 'восьмерка',
> 'звезда'?
> Если точка внутри многоугольника, то для 'восьмерки' вектор обойдет
неполный
> круг - второе 'ухо' 'восьмерки' будет мешать.
Что значит неполный? Hикто не говорит о том что угол должен
меняться всегда в одну сторону. В случае восьмерки просто
будет временный возврат угла, но в конце концов для внутренней
точки восьмерки суммарный угол обхода будет 2pi.
> Для звезды вектор обойдет несколько кругов (можно проверить нарисовав ее
> неотрывая руки с самопересечением и обходя точки в порядке рисования).
Если рассматривать точку в центре звезды, то для нее угол будет
4pi (т.е вне), но она ведь действительнолежит _вне_ многоугольника.
Внутренние точки - это только треугольники на лучах звезды,
а для точек на них угол опять же будет 2pi.
Cheers,
Serge
PS: Я не сторонник этого метода, гораздо проще с считать
пересечения с лучем из точки.
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
