|
Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Построение выпуклой оболочки методом Джарвиса |
|
Построение выпуклой оболочки методом Джарвиса
|
Студент Сообщения: 445 |
Профиль | Отправить PM | Цитировать Выпуклая оболочка для некоторого множества точек - это выпуклый многоугольник с вершинами в точках данного множества, причём всё точки данного множества лежат внутри многоугольника или на его рёбрах.
1. Находим пару точек A(x1, y1) и B(x2, y2)таких, что все другие точки лежат по одну сторону от прямой, на которой лежит отрезок AB. Эти две точки будут включены в выпуклую оболочку Это можно сделать например полным перебором всех вариантов. А можно и не полным перебором. Например можно найти точку с наименьшей абсциссой и перебором найти для неё пару. 2. Для одной из точек (ну пусть будет B) находим точку C (не совпадающую с A) такую, что все другие точки лежат по одну сторону от прямой, на которой лежит отрезок BС. Включаем точку C в нашу выпуклую оболочку. 3. По аналогии со 2-м пунктом находим для каждой новой точки такую точку, что все другие точки по одну сторону от прямой... И так до тех пор, пока новая найденная нами точка не совпадёт с точкой A. Я понятно объяснил, или может стоит запостить пример програмки? ПС Я слышал такое странное название для этого метода - "Метод заворачивания подарков" |
|
------- Отправлено: 15:41, 29-11-2001 |
Модер Сообщения: 1716
|
Профиль | Сайт | Отправить PM | Цитировать можно просто пройти по всем вершинам в одном направлении и для трех соседних вершин проверять целесообразность соединения 1-й и 3-й (включить 2-ю в ВО).
И так крутиться пока не будет отсутствие изменений. Если вообще понятно, что я написал. |
------- Отправлено: 18:38, 29-11-2001 | #2 |
Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети. Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля. |
Студент Сообщения: 445
|
Профиль | Отправить PM | Цитировать vasketsov
А если у тебя не прямоугольник в порядке обхода по часовой стрелке, а просто множество точек? ПС Мы кстати о методе Джарвиса. Кстати этот медод самый простой в реализации из всех известных мне... |
------- Отправлено: 02:59, 30-11-2001 | #3 |
Студент Сообщения: 445
|
Профиль | Отправить PM | Цитировать vasketsov
Кстати что ты называешь "целесообразностью" и как ты собираешься её проверять? |
------- Отправлено: 03:01, 30-11-2001 | #4 |
Модер Сообщения: 1716
|
Профиль | Сайт | Отправить PM | Цитировать Это если дан многоугольник и порядок его обхода.
Берешь <=4 точки (с максимальной и минимальной абсциссой и ординатой). Получаешь 4 (или 3)-угольник. Если совсем вырожденный случай - 2-хугольник ) получишь. Пусть N углов. Дальше проходишь цикл по всем точкам и выкидываешь все внутренние точки. Посте этого выбираешь одну любую точку (внешнюю) и добавляешь ее к ВО (исходя из ее абсциссы и ординаты). Для треугольника, который она добавила, опять выкидываешь все внутренние точки. И так далее, пока множество внешних точек не будет пустым. Хотя, я так подумал, по числу операций тоже O(N*N), как и метод Джарвиса. |
|
------- Отправлено: 11:06, 30-11-2001 | #5 |
Студент Сообщения: 445
|
Профиль | Отправить PM | Цитировать vasketsov
Да, только метод Джарвиса пишется буквально в несколько строк... Я всегда им пользуюсь |
------- Отправлено: 01:05, 01-12-2001 | #6 |
Guest |
Пожалуйста, вставте исходнике, ещ просьба чтобы они были на Паскале.
Заранее спасибо! |
Отправлено: 12:34, 16-12-2003 | #7 |
karina20
Сообщения: n/a |
для студента:
Уважаемый, если вы так хорошо разбираетесь в методе Джарвиса,не могли бы вы поместить программную реализацию данного метода(на Delphi али на Pascal-у).А то,что-то у меня не получается.Заранее большое-прибольшое СПАСИБО!!!!!!! |
Отправлено: 15:24, 16-02-2005 | #8 |
Старый параноик Сообщения: 2423
|
Профиль | Отправить PM | Цитировать |
Последний раз редактировалось hasherfrog, 16-02-2005 в 23:36. Отправлено: 23:23, 16-02-2005 | #9 |
karina20
Сообщения: n/a |
hasherfrog,благодарю!
|
Отправлено: 14:24, 17-02-2005 | #10 |
Участник сейчас на форуме | Участник вне форума | Автор темы | Сообщение прикреплено |
| |||||
Название темы | Автор | Информация о форуме | Ответов | Последнее сообщение | |
SOFT_CD Creator (интеграция софта в различные оболочки) | bodro | Автоматическая установка приложений | 22 | 18-10-2011 22:15 | |
Службы - оболочки программ | arblu | Microsoft Windows Vista | 1 | 14-11-2009 03:41 | |
Глюки с отображением оболочки | rafka | Непонятные проблемы с Железом | 5 | 31-07-2008 12:44 | |
Интерфейс - Explorer - перезагрузка оболочки | LeonF | Microsoft Windows 2000/XP | 1 | 08-08-2007 15:13 | |
Подвисания оболочки Win2003 при правом клике | Apock | Microsoft Windows NT/2000/2003 | 1 | 25-01-2007 11:45 |
|