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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.02.2007, 19:54
†Virus†

 
Сообщений: n/a

найти порядок, в котором можно соединить N точек, чтобы получился N-угольник
У меня есть такая задача и я попытался ее решить пользуясь алгоритмами, описанными вот на этой странице: http://algolist.manual.ru/maths/geom/misc/linkpoly.php

Оба варианта я реализовал, но ни один из них не дает правильные результаты в 100% случаях.

Например, в варианте 1 пропущен момент о том, как поступить, если программа находит некоторые минимальные расстояния от точек к сторонам многоугольника, которые (имеется в виду перпендикуляры) далеко находятся за пределами данной стороны, что в большинстве случаев приводит к тому, что N-угольник получается с самопересечениями.

Для варианта 2 я даю ссылку на скриншот:
http://image.grat.net.ua/links/scree...-bad-algorithm

На скриншоте результат программы на 3-ем шаге (т.е. построена 3-я внутр. выпуклая оболочка), где она использовала такой вариант размещения точек для склеивания контуров, а именно P, S, S1 и P1, и под руководством данного алгоритма не ошиблась.

Хоть дело уже чисто принципа, но все же прошу мне помочь.
  #2  
Старый 27.02.2007, 21:35
незарегистрированный

 
Сообщений: n/a

самые простой алгоритм:
выбираем к-л. точку C, например, центр окаймляющего прямоугольника.
сортируем все точки по возрастанию угла между лучем из центра C в текущую точку и осью х. при этом угол считаем против часовой стрелки,
т.е. угол может быть от 0 до 2*пи.
соединяем точки в заданном порядке и получаем простой звездчатый многоугольник.
  #3  
Старый 27.02.2007, 21:42
незарегистрированный

 
Сообщений: n/a

Да вот посмотри:
http://www.cs.mcgill.ca/~ktulu/507/
(тот же)
  #4  
Старый 27.02.2007, 21:49
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

если форма несущественна, выбираем нижнюю точку, сортируем остальные по углу и соединяем, получаем "гвоздику". при наличии трех и более точек под одним углом сортируем их по удалению от начальной точки.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
как можно доказать стабильность алгоритма? Warchief Сортировка и поиск 5 01.06.2007 16:58
можно вставлять формулы в Tex Илья Кантор Новости 3 27.05.2007 19:52
движение 3-х точек... nCaine Обработка изображений, звук, графика 0 22.03.2007 04:07
среднеотдолённая от точек плоскость ankorol Математические алгоритмы 3 20.12.2006 09:59
как вписать эллипс макс. площиди в заданый 4-угольник? partizan22 Вычислительная геометрия 0 18.12.2006 00:37