|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 26 Apr 2002 02:09:32
To : Alexey Kurbatov
Subject : Re: Писал yже кто-то, но пpопyстил
--------------------------------------------------------------------------------
Alexey Kurbatov wrote:
> ...
> Пpинадлежит ли точка замкнyтомy многоyгольникy?
> Оный тоже задан по вектоpам и обязательно замкнyт.
> ...
* Первый способ:
Рассматриваем воображаемый горизональный луч L, выходящий из нашей точки
и уходяший в бесконечность вправо. Просматриваем все ребра
многоугольника, одно из другим, и ищем точки пересечения каждого ребра с
лучом L. (Горизонтальные ребра - игнорируем. Для многих ребер будет
очевидно, что они не перескают луч L, даже без явного вычисления точки
пересечения.) Если луч L проходит через концевую точку ребра, то такое
пересечение засчитывается только в том случае, если вторая точка этого
ребра лежит ниже луча L.
Если финальное количество пересечений нечетно - точка внутри. В
противном случае - снаружи.
В таком виде это алгорим будет несколько нестабильно обрабатывать точки,
лежащие на границе многоугольника. Его несложно усовершенствовать, чтобы
устранить эту проблему. Тебе как нужно, чтобы точки на границе
классифицировались как внутренние, или как внешние?
* Второй способ:
Мысленно проводим лучи из нашей точки во все вершины многоугольника.
Вычисляем ориентированный угол между соседними лучами (соседние лучи -
это лучи, соответствуюшими соседним вершинам; относительный порядок
лучей соответствует порядку перечисления вершин). Суммируем все такие
углы. Если сумма равна 0, то точка снаружи. В противном случае (сумма
будет кратна 360 град.) - точка внутри.
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
