Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Даны целые числа а1,а2,.Известно что а1>0 http://www.cyberforum.ru/cpp-beginners/thread796937.html
Даны целые числа а1,а2,...Известно что а1>0 и что среди а2,а3,... есть хотя бы одно отрицательное число. Пусть а1,...,аn-члены данной последовательности, предшествующие первому отрицательному члену...
C++ Файловый ввод/вывод Ребят, помогите решить один вопросик, пожалуйста. Вот есть потоковые объекты классов ifstream и ofstream, которые работают с файлами. Можно ли с помощью этих объектов открывать файлы в конкретной... http://www.cyberforum.ru/cpp-beginners/thread796922.html
C++ Problem - Undefined reference to
Доброго времени суток и спасибо заранее за Вашу помощь. В качестве хобби начал изучать C++. Прочитал немного материала на сайтах и одну книгу, получил общее представление о языке и теперь принялся...
C++ Создать функцию для создания динамического массива
Как создать функцию в другом заголовочном файле, которая будет создавать двумерный динамический массив. входящие параметры такие (имя массива,переменная кол ва строк,перемен кол ва столбов) функция...
C++ Массивы структур http://www.cyberforum.ru/cpp-beginners/thread796828.html
Ввести координаты начала и конца N отрезков на плоскости.Написать функцию определяющую пересекаются два отрезка или нет.используя эту функцию вывести список всех пересечений среди заданных...
C++ Ошибка компиляции #include <iostream> class X { public: static int a; }; void main() { подробнее

Показать сообщение отдельно
Байт
Эксперт C
16355 / 10631 / 1592
Регистрация: 24.12.2010
Сообщений: 20,279
28.02.2013, 09:57
Первое, что приходит в голову.
Провести (составить уравнения) всех Cn2 прямых соединяющих вершины. Из них отобрать те, для которых все остальные точки лежат по одну сторону (т.е. при подставлении в уравнение прямой дают одинаковый знак). Вот эти прямые и будут образовывать выпуклый многоугольник.
Только имейте в виду, что некоторые точки могут не оказаться вершинами полученного многоугольника, т.к. лежат внутри.
Кажется, этот метод называется "Построение выпуклой оболочки"

Добавлено через 6 минут
Цитата Сообщение от alexcoder Посмотреть сообщение
упорядочиваете вершины по часовой
А как вы предлагаете определить центр?
Если б не условие выпуклости, центр можно назначить произвольно.
Но ваша идея дополняет мое построение. Тогда за центр можно взять любую из полученных действительных вершин. Хотя это и не обязательно. Проведенные (подходящие) прямые уже определяют порядок обхода!
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru