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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.90
Рулик
 Аватар для Рулик
8 / 8 / 0
Регистрация: 14.11.2011
Сообщений: 54
#1

Выпуклый многоугольник - C++

10.07.2012, 21:36. Просмотров 2551. Ответов 4
Метки нет (Все метки)

Есть массив точек, нужно определить выпуклый ли это многоугольник.
Я так понимаю что нужно посчитать каждый угол. Может быть можно другим более простым способом это сделать ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.07.2012, 21:36     Выпуклый многоугольник
Посмотрите здесь:

Многоугольник выпуклый или нет? C++
C++ Выпуклый многоугольник
Ввести количество точек, получить многоугольник, закрасить многоугольник построчно. C++
C++ 25. По координатам вершин четырехугольника определить, выпуклый он или нет
C++ Выпуклый многоугольник (вычислить площадь, периметр, количество сторон)
C++ задача выпуклый многоугольник
C++ Определить выпуклый ли многоугольник.
C++ Рассчитать выпуклый многогранник методом триангуации
По координатам вершин четырехугольника определить, выпуклый он или нет C++
C++ По координатам вершин четырехугольника определить, выпуклый он или нет
C++ Разбить выпуклый n-угольник на треугольники согласно условию
C++ Разбить выпуклый многоугольник на треугольники

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 1
10.07.2012, 22:23     Выпуклый многоугольник #2
В выпуклом многоугольнике, если мы возьмём любое его ребро и проведём через него прямую, все остальные точки будут лежать по одну и ту же сторону этой прямой, то есть, в одном полупространстве. Прямая описывается уравнением A*x + B*y + C = 0, коэффициенты A, B и C элементарно находятся по координатам вершин ребра. Если подставить в это уравнение координаты точек, то знак получившегося числа будет зависеть от того, "выше" или "ниже" прямой находится точка. Следовательно, если у всех остальных точек при подстановке в уравнение одинаковый знак, они по одну сторону от прямой. Если это условие выполняется для каждого ребра, многоугольник выпуклый.
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
10.07.2012, 23:24     Выпуклый многоугольник #3
Все это выражается значительно проще:
1) При каждой вершине строим два вектора с началом в данной вершине и с концами в смежных.
2) Считаем векторные произведения для всех пар векторов.
3) У выпуклого многоугольника знаки всех этих векторных произведений должны совпадать.
Nick Alte
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 1
10.07.2012, 23:33     Выпуклый многоугольник #4
Какой может быть знак у векторного произведения, это ж вектор? Скалярное произведение тут тем более не годится...
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
10.07.2012, 23:44     Выпуклый многоугольник #5
Пардон сглупил немного:
Пункт 3) звучит так:
3) У выпуклого многоугольника все векторные произведения направлены в одну и ту же сторону.
Yandex
Объявления
10.07.2012, 23:44     Выпуклый многоугольник
Ответ Создать тему
Опции темы

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