Выпуклость многоугольника

Постановка задачи

Задача, скорее, не на программирование, а на векторную алгебру. Итак, условие. Задан многоугольник. Требуется определить, является ли он выпуклым.

Для начала определимся, что есть выпуклый многоугольник. Многоугольник называется выпуклым, если любые две точки его периметра можно соединить отрезком, каждая точка которого лежит внутри многоугольника.

Здесь слева — выпуклый многоугольник, справа — нет.

Выпуклый многоугольник Невыпуклый многоугольник

Одним из критериев выпуклости является следующий.

Многоугольник будет выпуклым, если для векторов, составляющих его периметр, выполняется условие: векторные произведения соседних векторов должны иметь одинаковый знак.

В общем случае, произведение векторов в трехмерном пространстве находится по формуле:

     \[ \left [ \bar{a},\bar{b} \right ]=\begin{vmatrix} \bar{i} & \bar{j} & \bar{k} \\ x_{1} & y_{1} & z_{1} \\ x_{2} & y_{2} & z_{2} \\ \end{vmatrix}= \left ( y_{1}z_{2}-y_{2}z_{1} \right ) \bar{i} -\left (x_{1}z_{2}-x_{2}z_{1}\right ) \bar{j} +\left (x_{1}y_{2}-x_{2}y_{1} \right) \bar{k} \]

Здесь i, j, k — орты декартовой системы (вектора единичной длины, сонаправленные с осями координат).
Однако, если мы рассматриваем вектора, лежащие в одной плоскости, то для этого случая z-составляющая векторов будет нулевой. Тогда наша формула выродится в:

     \[ \left [ a, b \right ]=\left (x_{1}y_{2}-x_{2}y_{1} \right)k \]

Таким образом, мы должны обойти все пары соседних сторон-векторов и посмотреть, все ли их произведения одного знака. (То есть все ли значения разности произведений \left (x_{i}y_{i+1}-x_{i+1}y_{i} \right) одного знака для всех i от 1 до N-1).

Итак алгоритм:

  1. Задаем N — количество вершин многоугольника
  2.  Задаем (вводим или присваиваем) все вершины многоугольника P_{i}^{x}, P_{i}^{y} для всех i от 1 до N.
  3. Полагаем многоугольник выпуклым Q=true.
  4. Вычисляем T=xNy1-x1yN
  5. Вычисляем Z=T/|T|, |T| — модуль числа Т.
  6. Полагаем P=1
  7. Для всех i от 1 до N-1 при условии что Q=true вычисляем:
    1. xi,yi
    2. xi+1,yi+1
    3. R=xiyi+1-xi+1yi
    4. P=P*Z*R/|R|, здесь |R| — модуль числа R.
    5. Если P<0, то Q=false
    6. Если Q=true — многоугольник выпуклый, иначе — нет.

Вычисление координат вектора, образованного сторонами многоугольника (xi, yi), хорошо производить в отдельной процедуре.

    \[x_{i}=P_{i+1}^{x}-P_{i}^{x}\]\[y_{i}=P_{i+1}^{y}-P_{i}^{y}\]

Для N-ой вершины N+1-ая будет, естественно, первой.

Решение задачи


Оставить комментарий