Определение выпуклости многоугольника
Определение выпуклости многоугольника.
Алгоритм Кируса–Бэка предполагает наличие выпуклого многоугольника, используемого в качестве окна.
Однако на практике весьма часто возникает задача отсечения многоугольником, а информация о том, является он выпуклым или нет изначально не задается. В таком случае, прежде чем начать процедуру отсечения необходимо определить какой задан многоугольник – выпуклый или нет.
Дадим некотрые определения выпуклости многоугольника
Выпуклым считается многоугольник, для которого выполняется одно из ниже перечисленных условий:
1) в выпуклом многоугольнике все вершины располагаются по одну сторону от линии, несущей любое ребро (по внутреннюю сторону относительно данного ребра);
2) все внутренние углы многоугольника меньше 180о;
3) все диагонали, связывающие вершины многоугольника, лежат внутри этого многоугольника;
4) все углы многоугольника обходятся в одном направлении (Рис. 3.3‑1).
Рекомендуемые материалы
Для выработки аналитического представление последнего критерия выпуклости, используем векторное произведение.
Векторное произведение W двух векторов a и b (Рис. 3.3‑2 а) определяется как:
где:
- ax,ay,az и bx,by,bz являются проекциями на оси координат X,Y,Z, соответственно, векторов – сомножителей a и b,
- i, j, k – единичные векторы по координатным осям X, Y, Z.
Рис. 3.3‑1
Рис. 3.3‑2
Если рассматривать двумерное представление многоугольника как представление его в координатной плоскости XY трехмерной системе координат X,Y,Z (Рис. 3.3‑2 b), то выражение для формирования векторного произведения векторов U и V , где векторы U и V являются соседними ребрами, образующими угол многоугольника, можно записать в виде определитель:
Вектор векторного произведения перпендикулярен плоскости, в которой находятся вектора-сомножители. Направление вектора произведения определяется по правилу буравчика или по правилу винта с правой нарезкой.
Для случая, представленного на Рис. 3.3‑2 b), вектор W, соответствующий векторному произведению векторов V,U, будет иметь ту же направленность, что и направленность координатной оси Z.
Учитывая то, что проекции на ось Z векторов –сомножителей в этом случае равны нулю, векторное произведение можно представить в виде:
(3.3-1)
Единичный вектор k всегда положительный, следовательно, знак вектора w векторного произведения будет определяться только знаком определителя D в выше приведенном выражении. Отметим, что на основании свойства векторного произведения, при перестановке местами векторов-сомножителей U и V знак вектора w будет меняться на противоположный.
Отсюда следует, что, если в качестве векторов V и U рассматривать два соседних ребра многоугольника, то порядок перечисления векторов в векторном произведении можно поставить в соответствие c обходом рассматриваемого угла многоугольника или ребер, образующих этот угол. Это позволяет использовать в качестве критерия определения выпуклости многоугольника правило:
Если Вам понравилась эта лекция, то понравится и эта - 4 - Искусство.
если для всех пар ребер многоугольника выполняется условие:
Если знаки векторных произведений для отдельных углов не совпадают, то многоугольник не выпуклый.
Так как ребра многоугольник задаются в виде координат их концевых точек, то для определения знака векторного произведения удобнее использовать определитель:
Легко показать, что этот определитель эквивалентен определителю в выражении (3.3-1).