Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
Akkanee
2 / 2 / 0
Регистрация: 09.01.2013
Сообщений: 65
#1

Построение многоугольника

28.02.2013, 08:59. Просмотров 801. Ответов 2
Метки нет (Все метки)

Здравствуйте, как построить выпуклый многоугольник по беспорядочно заданным вершинам?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.02.2013, 08:59
Ответы с готовыми решениями:

Площадь многоугольника
Найти площадь невыпуклого многоугольника(n-угольник). Входные данные:...

Вращение многоугольника
Добрый вечер! Есть прога, которая рисует многоугольник с заданным числом...

Триангуляция многоугольника
Добрый вечер. Ни у кого случайно нет алгоритма для триангуляции ПРОИЗВОЛЬНОГО...

Площадь многоугольника
Всем добрый вечер! Есть задача: Заданы координаты n последовательных вершин...

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

2
alexcoder
1558 / 703 / 146
Регистрация: 03.06.2009
Сообщений: 4,060
Завершенные тесты: 1
28.02.2013, 09:45 #2
1) Где гарантия, что возможно построить такой многоугольник?
2) Если условие это гарантирует, упорядочиваете вершины по часовой или против часовой стрелки и соединяете их последовательно.

Для сортировки первое, что приходит в голову - это перевод координат в полярную систему координат.
1
Байт
Эксперт C
17938 / 11929 / 2478
Регистрация: 24.12.2010
Сообщений: 24,032
28.02.2013, 09:57 #3
Первое, что приходит в голову.
Провести (составить уравнения) всех Cn2 прямых соединяющих вершины. Из них отобрать те, для которых все остальные точки лежат по одну сторону (т.е. при подставлении в уравнение прямой дают одинаковый знак). Вот эти прямые и будут образовывать выпуклый многоугольник.
Только имейте в виду, что некоторые точки могут не оказаться вершинами полученного многоугольника, т.к. лежат внутри.
Кажется, этот метод называется "Построение выпуклой оболочки"

Добавлено через 6 минут
Цитата Сообщение от alexcoder Посмотреть сообщение
упорядочиваете вершины по часовой
А как вы предлагаете определить центр?
Если б не условие выпуклости, центр можно назначить произвольно.
Но ваша идея дополняет мое построение. Тогда за центр можно взять любую из полученных действительных вершин. Хотя это и не обязательно. Проведенные (подходящие) прямые уже определяют порядок обхода!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.02.2013, 09:57

Разрезание многоугольника
Здравствуйте программисты! Мне необходимо написать программу, которая бы...

Периметр многоугольника
Данные координаты вершин многоугольника (x1, y1, x2, y2, .x10, y10). Напишите...

замкнутость многоугольника
добрый вечер.пишу игру точки.подскажите,плз,как можно реализовать вычисление...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru