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

Определить, является ли заданный многоугольник выпуклым - C++

Восстановить пароль Регистрация
 
Kolbusdkiy
 Аватар для Kolbusdkiy
0 / 0 / 0
Регистрация: 14.10.2013
Сообщений: 112
10.04.2014, 14:40     Определить, является ли заданный многоугольник выпуклым #1
Помогите решить.
Определить, является ли заданный многоугольник выпуклым. В первой строке одно число - N . Далее в N строках по паре чисел - координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2014, 14:40     Определить, является ли заданный многоугольник выпуклым
Посмотрите здесь:

Ввести количество точек, получить многоугольник, закрасить многоугольник построчно. C++
Определить, является ли текст является записью четного числа в семеричной системе C++
C++ Определить является ли заданный четырехугольник трапецией
C++ Определить выпуклый ли многоугольник.
Выяснить, является ли заданный текст идентификатором C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
10.04.2014, 15:23     Определить, является ли заданный многоугольник выпуклым #2
Kolbusdkiy, предложу такой вариант: программа находит координаты каждой точки, затем вычисляет для каждой точки угол (который мы можем найти с помощью треугольника, построенного из самой точки и двух соседних). Не уверен в решении, с математикой не очень хорошие отношения.
fishec
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
10.04.2014, 16:27     Определить, является ли заданный многоугольник выпуклым #3
Можно пройти по всем ребрам, для каждого ребра берем следующую по часовой стрелке вершину - она должна быть справа от прямой(вектора ребра) для всех ребер.
palva
 Аватар для palva
2372 / 1594 / 190
Регистрация: 08.06.2007
Сообщений: 6,362
Записей в блоге: 4
10.04.2014, 23:04     Определить, является ли заданный многоугольник выпуклым #4
По треугольникам хорошая идея. По трем последовательным вершинам вычисляется площадь треугольника (определитель четвертого порядка). При обходе многоугольника все эти площади должны быть одного знака.

Другой алгоритм. Обходим многоугольник и для каждых двух последовательных вершин A и B составляем уравнение прямой AB и в это уравнение подставляем координаты вершины, которая предшествует вершине A и которая идет после вершины B. Эти подстановки должны дать результат одного знака (точки должны находиться по одну сторону от прямой AB).

Добавлено через 5 часов 51 минуту
Все-таки второй алгоритм надо забраковать. По вычислениям это то же, что и первый алгоритм. Подстановка точки в уравнение прямой и дает площадь треугольника с некоторым положительным коэффициентом. Получается, что площадь каждого треугольника при обходе многоугольника вычисляется дважды. То есть он в два раза медленнее работает.

А в первом алгоритме в формуле площади треугольника есть коэффициент 1/2. Его использовать не нужно, поскольку нам важно узнать лишь знак площади.
Yandex
Объявления
10.04.2014, 23:04     Определить, является ли заданный многоугольник выпуклым
Ответ Создать тему
Опции темы

Текущее время: 07:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru