Разбиение невыпуклых многоугольников

Пусть область невыпуклая:

- дополнить область, или разбить ее на выпуклые области.

Факт выпуклости или вогнутости определяется путем векторного произведения всех смежных сторон.

Рассмотрим знаки:

1. все знаки равны нулю - многоугольник вырождается в отрезок;

2. есть и “+” и “-” - многоугольник не выпуклый;

3. все неотрицательные - многоугольник выпуклый и все нормали ориентированны влево от контура;

4. все неположительные - многоугольник выпуклый и все нормали ориентированны вправо от контура.

Вычисление нормалей:

одна вершина выбирается, как базовая и все векторные произведения вычисляются относительно ее.

(v_x1v_y2 - v_y1v_x2)k - векторное произведение v₁,v₂.

n*v_E = (n_x*i + n_yj)(v_Ex*i + v_Ex*j) = n_xv_Ex + n_yv_Ey + 0;

n_xv_Ex = -h_yv_Ey {n_y = 1}

n_x = -(v_Ey / v_Ex)*i + j

v_i-1 и v_i - вершины

v_i-1 * v_i > 0, то n - внутренняя нормаль, иначе - внешняя.

1. перенос начала координат в точку v₁;

2. начинаем вращать фигуру так, чтобы любое ребро лежало на оси X

3. если Y вершины меньше нуля, то фигура невыпуклая и она отсекается соседями.

Дата добавления: 2014-01-07