![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Разбиение невыпуклых многоугольников
Метод поворотов и переносов окна позволяет разбивать или разделять простой невыпуклый многоугольник на несколько выпуклых. Предположим, что вершины многоугольника перечисляются против часовой стрелки, тогда алгоритм будет иметь следующий вид: - для каждой i-й вершины многоугольника надо так ее перенести, чтобы она совпадала с началом координат; - повернуть многоугольник относительно координат по часовой стрелке так, чтобы (< +1)-я его вершина оказалась на положительной полуоси х (рис. 15); - проанализировать знак ординаты (г+-2)-й вершины, если он
- многоугольник разрезается вдоль положительной полуоси х, т.е. находятся все его такие стороны, которые пересекаются с осью х, образуется два новых многоугольника: один состоит из вершин лежащих выше оси.г и ближайшей к началу координат точки пересечения с x> xi+1, второй - из вершин лежащих ниже оси х. Когда после поворота его вершина V2 совпадет с началом координат, Уз ляжет на положительной оси х, знак ординаты V4 будет отрицательным, значит многоугольник невыпуклый. Разрезание его осью х дает многоугольник V3V4V5 ниже оси х и V2V5V1) - выше оси х (рис. 15). Возобновление работы алгоритма с новыми многоугольниками показывает, что они оба выпуклые, поэтому алгоритм прекратит дальнейшую работу. Алгоритм рекурсивно применяется к полученным многоугольникам до тех пор, пока все они не станут выпуклыми.
|