 |
|
|
 
|
|
Множество точек,необходимо "очертить" крайние. помогите с алгоритмом 
| Djigit |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 124 Регистрация: 10.11.2006 Репутация: нет Всего: нет |
Доброго времени суток.
Нужно решить задачу. Имеются random'ом раскинутые на диаложке точки,необходимо провести линии между крайними,чтобы остальные точки находились внутри этого многоугольника. Кто поможет с алгоритмом. Заранее благодарен. --------------------
Бабло победит зло!!! |
|||
|
||||
Загрузка ...
| Mayk |
|
|||
 ^аВаТаР^ сообщение>> Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: 2 Всего: 134 |
если я правильно понял, то это поиск по ключевым словам "выпуклая оболочка"
Добавлено через 1 минуту и 3 секунды кстати в конце http://en.wikipedia.org/wiki/Convex_hull есть линк "C++ Code and Reports for Convex Hull" -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
| Djigit |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 124 Регистрация: 10.11.2006 Репутация: нет Всего: нет |
выпуклая оболочка? ну не знаю как назвать это задание... суть его я написал... сейчас гляну по ссылке,в любом случае спасибо за уделенное внимание. --------------------
Бабло победит зло!!! |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
||||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Описывающий многоугольник не обязан быть выпуклым. Во всяком случае заданием этого не оговорено явно.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Ну как я понял задание, если предположить, что искомый многоугольник невыпуклый, то та его вершина, которая "вызывает" "невыпуклость", не будет крайней, а по условию нам нужно соединять крайние.
|
|||
|
||||
| Earnest |
|
|||
 Эксперт Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 7 Всего: 183 |
А если невыпуклая, то нет однозначного решения.
Берем выпуклую оболочку и любую (ну почти) внутреннюю точку, и включаем в подходящее место... таких зигзагов можно понарисовать, что ничего "внутри" не останется. А вто выпуклая оболочка - вполне однозначна... -------------------- ... |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0543 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |