Добрый день, помогите пожалуйста разобраться со следующим вопросом: 

Рандомно генерируются n точек. Необходимо обвести их замкнутым контуром, другими словами сделать из них многоугольник. 
Что-то никак не могу сообразить как это сделать. 
Первая идею кот-ая пришла в голову была следующей:
Берём самую отдалённую точку по X. 
Соединяем её со ближайшей точкой по Х и Y.
Соединяем её со второй по ближайшей точкой по X. 
Далее начинаем строить многоугольник снизу и сверху находя и там и там ближайшие не занятые точки по X.
Эта идея не работает =(

Была и другая:
Берём самую отдалённую точку по X. 
Соединяем её со ближайшей точкой по Х и Y.
Соединяем её со второй по ближайшей точкой по X. 
Далее начинаем строить многоугольник снизу и сверху находя просто ближайшие точки.
Тоже не пашет =(

Помогите пожалуйста  =)
 

Что значит "обвести их"? Если ситуация когда не все точки являются вершинами многоугольника устроит, то поиск по ключевым словам "выпуклая оболочка".

http://algolist.ru/maths/geom/convhull/

Я посматрел, там есть только твой линк:
http://en.wikipedia.org/wiki/Convex_hull
а мне нуно немного другое, мне не нужно соединять крайние точки, мне нужно нарисовать многоугольник. Нет не задействованных точек.
2 Sartorius. Здесь то же самое.

Это сообщение отредактировал(а) Atij - 15.10.2008, 16:02

и самопересечения запрещены?
можно попробовать так:
берём две точки, поворачиваем всё так, чтобы отрезок между ними стал горизонтальным
только нужно брать так, чтобы одна точка получилась самой левой, а другая - самой правой (тут нужно подумать над доказательством возможности и алгоритмом выбора - сейчас в голову не приходит)
разделяем остальные точки на те, что выше отрезка и те, что ниже
начинаем в левой точки, по верхним идём вправо до правой точки, по нижним возвращаемся
для прохода в каждую сторону точки сортируются и объодятся в соответствующем порядке - тогда самопересечений не будет

Добавлено через 32 секунды

а нет - таки пришло 
просто берём две самые удалённые точки

спс, согласен =)
есть ещё предложения ? =)

На сырцах тебе дали вполне рабочий ответ.