|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 01 Apr 2002 09:28:14
To : Alexey Skazik
Subject : Re: Определение границы...
--------------------------------------------------------------------------------
Однажды 29-Mar-02 в 00:02 Alexey Skazik (2:5061/6.61)
написал All по поводу
-=- Определение границы... -=-
AS> Есть множество точек на плоскости. Hужно найти такие точки, проведя
AS> ломанную ч/з которые, заключим всё остальное множество внутри.
AS> Идеи? Что-либо кроме простого перебора по парам точек, с выяснением
AS> есть ли что-либо с одной или другой стороны проведённой ч/з них прямой?
AS> :) Границы прямоугольной области, в которой гарантированно находится
AS> множество -известны.
Hасколько я помню, сложность этой задачи O(N*log(N)).
1. Берем какую-нибудь внутреннюю точку (например, по средним арифм.
координатам, сложность - O(N)).
2. Hаходим какую-нибудь крайнюю точку, например, с наибольшим (или
наименьшим) X (или Y).(сложность O(N))
3. Вычисляем углы для каждой точки относительно средней (O(N)).
4. Упорядочиваем точки по углу, начиная с крайней O(N*log(N)).
5. Проходим по упорядоченным точкам, в зависимости от требований к выпуклости
или оставляя все, или отбирая только те из них, для которых
угол, обращенный к центру, менее 2Pi. Скорее всего, понадобится несколько
проходов, но суммарная сложность, думаю, не превысит O(n*log(N)), т.к.
количество точек будет уменьшаться в геометрической прогрессии.
AS> :) Потом точки на границе нужно ещё и упорядочить, чтобы границу можно было
AS> обойти по/против часовой стрелки - без разницы.
Собственно, упорядочивание уже осуществлено в процессе выполнения алгоритма.
До свидания, в 22:47 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Определение границы... 
