Четырех угольник ABCD задан координатами своих вершин на плоскости
А(Ха,Уа) В(Хb,Уb), и т.д. Проверить, является ли он выпуклым. Даже приблизительно не представляю, как это можно сделать.

Новиков Евгений .



--------------------------------------------------------------------------------

Peter_P
Спасибо, конечно но мне это не сильно помогло, как бы это перевести в С++? к тому же используя координаты

Новиков Евгений
Берем две точки через которые проходит его сторона например А и В, определяем урние прямой на которой лежат эти точки
далее, определяем также прямую на которой лежат другие две вершины(ДС) определяем пересекаются ли эти прямые или нет - если нет то все отлично(стороны паралельны), если да проверяем попала ли точка пересечения на отрезок АВ - если да то АВСД не выпуклый. Так делаем для каждой из его сторон.

Вот тогда подсказка:

Рассмотрим вариант решения по методу (а):


Пишем примерно такой код:
1. В цикле перебрать все стороны.
2. Для каждой стороны выполнить преобразование всех координат вершин многоугольника так, чтобы выбранная сторона была параллельна оси Х, выполнить смещение так, чтобы сторона совпала с осью Х.
3. Для преобразованных координат провести проверку, что все координаты У для всех точек имеют одинаковый знак (за исключением координат У для выбранной стороны - они будут равны нулю.
4. В случае, когда проверка не удалась, вывалиться с заявой, что многоугольник впуклый.
5. После перебора всех сторон выйти с сообщением, что многоугольник выпуклый.

Историческая справка:
Для поворота, для опорной точки допустимо использовать одну из точек исследуемой стороны.
Угол для поворота - арктангенс от ( У2 - У1 ) / ( Х2 - Х1 ), где (1) - точка, вокруг которой вращаем.

Еще мудрый алгоритм.
1. Разбить на 2 треугольника, (ABC-ACD) и найти сумму их площадей S1.
2. Разбить подругому (ABD-BDC) и найти их площади S2.
3. Если S1!=S2 - фигура вогнута.
Если нарисовать на бумажке все становится видно

Проклятье не успел может на следующей неделе получится

KaYot полюбому S1=S2 даже если фигура выпукла

PsychoF
В том и фишка. Если фигура невогнута то S1=S2. Иначе площади неравны.