Доказывание выпуклости многоугольника

Рейтинг: -1Ответов: 2Опубликовано: 03.08.2023

Что бы доказать выпуклость многоугольника, по общему мнению, надо применить псевдоскалярное умножение векторов. Применяя поочередно последовательно, по, или против часовой стрелки к углам многоугольника этот метод , мы получим некоторое значение со знаком плюс, или минус. Если знак для всех углов одинаков, то многоугольник выпуклый. Для доказывания выпуклости в системе координат предлагается формула , х1у2-х2у1 . И, надо полагать, в формуле представлены концы векторов, поскольку координаты всего две. Если векторы это стороны многоугольника, то где начало и где считать конец вектора? Например, имеем квадрат(многоугольник) ABCD. Правильно ли я понимаю, что если обходим по часовой стрелке, то сначала делаем вычисления , например, для точки A, потом B, потом С, и, наконец ,D. Для точки А вектора будут AD и AB, соответственно. И координаты , для выражения Х1У2-Х2У1, будут, соответственно, не начала, а концы векторов: Х1,У1 это точка D, а Х2,У2, точка В? Практическое вычисление показало, что у двух соседних углов знак разный.

Получен комментарий.

1 - Это вектора. 2 - вы их сами разворачиваете и потом удивляетесь. Сравнивайте DA и AB, а не AD и AB, и все будет как надо. – Kromster

Из комментария следует, что конец одного вектора есть начало другого. Но у нас всего 2 координаты? Что в этом случае х1.у1 и х2.у2?

математика
Источник: Stack Overflow на русском

Ответы

▲ 2

Пусть имеется массив/список A[] из N вершин.

Входящий в k-ю вершину вектор - это разность координат вершин

Vin = A[k]-A[k-1]

его компоненты

Vin.X = A[k].X-A[k-1].X
Vin.Y = A[k].Y-A[k-1].Y

исходящий вектор

Vout = A[k+1]-A[k]

Кросс-продукт (псевдоскалярное умножение):

 CP = Vin x VOut = Vin.X * VOut.Y - Vin.Y * VOut.X

Чтобы не считать разности по два раза, после вычисления кросс-продукта копируем Vout в Vin, а перед первым шагом считаем Vin = A[0]-A[n-1]

Так будет понятнее?

▲ 0

Даны три точки A, B, C. Будем говорить (это определение) что угол ∠ABC левый если соответствующий определитель больше нуля:

| Ax Ay 1 |
| Bx By 1 | > 0
| Cx Cy 1 |

Этот определитель равен: (AxBy - BxAy) + (BxCy - CxBy) + (CxAy - AxCy). Пары произведений забраны в скобки чтобы была видна циклическая перестановка A→B→C→A....

Выражение можно переписать в виде (Bx - Ax)(Cy - By) - (Cx - Bx)(By - Ay). Если вы раскроете скобки и сократите подобные, получите предыдущее выражение.

Введем обозначения для разности точек (вектора из A в B): AB = B - A, ABx = Bx - Ax, ABy = By - Ay. Обратите на обратный порядок в разнице.

Тогда последнее выражение можно переписать как ABxBCy - BCxABy.

Последнее выражение называют косым произведением векторов AB⋁BC ( = (B - A)⋁(C - B)).

Это, кстати, тоже определитель:

| ABx ABy|
| BCx BCy| > 0

Возвращаясь к исходному вопросу. Вектора будут такие: AB и BC, BC и CD, CD и DA, DA и AB. Снова циклическая перестановка A→B→C→D→A.... А можно не думать о векторах, а говорить в терминах точек: ABC, BCD, CDA, DAB.