|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 30 Mar 2002 01:22:42
To : Alexey Skazik
Subject : Re: Определение границы...
--------------------------------------------------------------------------------
Alexey Skazik wrote:
> ...
> >> Возмем центр масс данной системы точек и примем его за полюс
> >> полярной системы координат. Соединим все точки множества в порядке
> >> возрастания их угловой координаты. А если несколько точек имеют
> >> одинаковую координату - то в порядке возрастания радиуса. Соединим
> >> также последнюю точку с первой.
> AT> Добавление: если какая-нибудь точка совпадет с полюсом, ее можно
> AT> проигнорировать.
> Т.е. алгоритм, как часовая стрелка, сканирует все точки множества по углу
> и выбирает обладающие для угла сканирования максимальным радиусом? ...
Да, именно так.
В процессе обхода точек, если встречается несколько точек с одинаковым
полярным углом, то можно, как ты говоришь, выбирать точки, обладающие
максимальным радиусом, а остальные точки игнорировать, - такая оболочка
в общем случае окажется "ближе" к выпуклой.
А можно не выбирать, а сделать так, как сказал я, - точки с одним и тем
же полярным углом соединять в порядке возрастания (или убывания)
радиуса. Такая оболочка будет в обшем случае более "звездатой".
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
