Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Замкнутый контур


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

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

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

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

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

Автор: Sartorius 15.10.2008, 16:00
http://algolist.ru/maths/geom/convhull/

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

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

Добавлено через 32 секунды
Цитата(maxim1000 @  15.10.2008,  18:11 Найти цитируемый пост)
тут нужно подумать над доказательством возможности и алгоритмом выбора - сейчас в голову не приходит

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

Автор: Atij 15.10.2008, 18:16
спс, согласен =)
есть ещё предложения ? =)

Автор: Akina 15.10.2008, 21:15
На сырцах тебе дали вполне рабочий ответ.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)