Определение факта выпуклости многоугольника — КиберПедия 

Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...

Определение факта выпуклости многоугольника

2017-10-10 649
Определение факта выпуклости многоугольника 0.00 из 5.00 0 оценок
Заказать работу

 

1-й метод. Вычисляем векторные произведения смежных сторон многоугольника. Векторное произведение V 1 Ä V 2 =
=(V X 1 * V Y 2V Y 1 * V X 2) * k, где k – единичный вектор, перпендикулярный плоскости, несущей векторы сомножителей.

Выводы: если все значения произведений равны нулю – многоугольник вырождается в отрезок; есть как положительные, так и отрицательные знаки произведений – многоугольник невы-пуклый; все произведения либо неотрицательные, либо неположительные – многоугольник выпуклый.

 

 

 

Рис. 6.7. Алгоритм Кируса-Бека

2-й метод. Одна из вершин выбирается как базовая, вычисляются векторные произведения пар векторов, начинающихся в этой базе и заканчивающиеся в вершинах многоугольника. Выводы аналогичны предыдущему методу.

3-й метод. Для каждой i -й вершины окна перенести ее так, чтобы эта вершина совпадала с началом координат. Повернуть многоугольник так, чтобы (i + 1)-я вершина оказалась на положительной полуоси X. Вычислить знак ординаты (i + 2)-вершины. Если знаки ординат всех (i + 2)-х вершин либо неположительны, либо неотрицательны, то многоугольник выпуклый, иначе – невыпуклый (рис. 6.8 и 6.9). Достоинством последнего метода явля-

 

Рис. 6.8. Определение факта выпуклости многоугольника
(вариант – многоугольник выпуклый)

Рис. 6.9. Определение факта выпуклости многоугольника
(вариант – многоугольник невыпуклый)

 

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

Вычисление уравнения внутренней нормали

 

Нормаль к стороне многоугольника можно вычислить, если вспомнить, что скалярное произведение пары перпендикулярных векторов равны нулю. Если nx и ny – неизвестные компоненты нормали к известному вектору (Vx, Vy) стороны многоугольника, то

n * V = (nx * i + ny * j) (Vx * i + Vy * j) = nx * Vx + ny * Vy = 0,

где i и j – единичные векторы, параллельные осям X и Y, следовательно,

nx * Vx = – ny * Vy,

так как нас интересует только направление нормали, то пусть
ny = 1 и тогда nx = – (Vy / Vx) * i + j. Если вектор стороны многоугольника образован парой вершин Vi и Vi +1 и если скалярное произведение нормали и вектора от Vi до Vi + 2 положительно, то n – это внутренняя нормаль, иначе – внешняя, и получить внутреннюю нормаль можно, умножив ее на минус 1.

 


Задание на лабораторную работу № 6

"Алгоритмы отсечения отрезков"

1. Постройте окно отсечения.

2. Постройте отрезок, пересекающий окно отсечения.

3. Произведите отсечение отрезка с помощью любого алгоритма.

4. Выделите другим цветом отсекаемую часть отрезка.

5. Повторите пп. 2 и 3 для полностью видимых и невидимых отрезков.

6. Сравните эффективность различных алгоритмов отсечения.

7. Чем отличаются алгоритмы Коэна-Сазерленда и FC-ал-горитм от алгоритма Кируса-Бека?

 


Поделиться с друзьями:

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

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

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.008 с.