Дано множество точек на плоскости с координатами (x,y). Требуется построить из них замкнутый контур (соединить все точки непересекающимися отрезками, образующие замкнутый контур). Куда копать? Есть ли готовые решения (задача, вроде, типовая)? Подскажите плз!
Здравствуйте, hypnotic, Вы писали:
H>Дано множество точек на плоскости с координатами (x,y). Требуется построить из них замкнутый контур (соединить все точки непересекающимися отрезками, образующие замкнутый контур). Куда копать? Есть ли готовые решения (задача, вроде, типовая)? Подскажите плз!
Найти самую нижнюю точку. Отсортировать все точки по углу, составляемому вектором из самой нижней в данную и лучом, исходящим из нижней точки влево (это, кстати первый шаг алгоритма Грэхема).
Полученная последовательность (самая нижняя точка первая или последняя) есть контур с нужными свойствами.
С уважением Михаил Копачев
... << RSDN@Home 1.1.4 @@subversion >>