Построение контура
От: hypnotic  
Дата: 14.06.05 08:58
Оценка:
Дано множество точек на плоскости с координатами (x,y). Требуется построить из них замкнутый контур (соединить все точки непересекающимися отрезками, образующие замкнутый контур). Куда копать? Есть ли готовые решения (задача, вроде, типовая)? Подскажите плз!
Re: Построение контура
От: McSeem2 США http://www.antigrain.com
Дата: 14.06.05 10:09
Оценка: 2 (1)
Здравствуйте, hypnotic, Вы писали:

H>Дано множество точек на плоскости с координатами (x,y). Требуется построить из них замкнутый контур (соединить все точки непересекающимися отрезками, образующие замкнутый контур). Куда копать? Есть ли готовые решения (задача, вроде, типовая)? Подскажите плз!


Точки надо каким-либо образом отсортировать. Простейший вариант — вычислить центр масс и отсортировать по углу (xc,yc) -> (xN,yN). Отсортированное множество точек можно считать контуром.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: Построение контура
От: mkopachev  
Дата: 14.06.05 12:08
Оценка: 2 (1)
Здравствуйте, hypnotic, Вы писали:

H>Дано множество точек на плоскости с координатами (x,y). Требуется построить из них замкнутый контур (соединить все точки непересекающимися отрезками, образующие замкнутый контур). Куда копать? Есть ли готовые решения (задача, вроде, типовая)? Подскажите плз!


Найти самую нижнюю точку. Отсортировать все точки по углу, составляемому вектором из самой нижней в данную и лучом, исходящим из нижней точки влево (это, кстати первый шаг алгоритма Грэхема).
Полученная последовательность (самая нижняя точка первая или последняя) есть контур с нужными свойствами.

С уважением Михаил Копачев
... << RSDN@Home 1.1.4 @@subversion >>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.