Тест принадлежности точки многоугольнику

Будем понимать под многоугольником фигуру, ограниченную на плоскости простой (несамопересекающейся) замкнутой ломаной. Сама ломаная задается на- бором своих вершин Ai(xi , yi), i = 1, . . ., n, причем соседние точки в этом списке являются смежными вершинами ломаной. Задача состоит в том, чтобы получить растровую развертку многоугольника, т. е. инициировать его внутренние точки. Начнем с обсуждения задачи о локализации точки относительно многоуголь- ника. Решение этой задачи даст возможность эффективно определять, является ли точка внутренней или внешней по отношению к нему. Теорема Жордана утверждает, в частности, что простая (т. е. не имеющая само- пересечений) замкнутая плоская ломаная разбивает плоскость на две связные ком- поненты — ограниченную, которая является внутренностью многоугольника, и не- ограниченную, которая является внешней по отношению к многоугольнику. Алгоритм должен уметь различать внутренние и внешние точки плоскости. Обозначим ребра многоугольника через Ei : Ei ∶ [Ai ,Ai+1], i = 1, . . ., n. Пусть P(x, y) — некоторая точка плоскости, не лежащая на ломаной, и нужно определить, принадлежит она этому многоугольнику или нет. Проведем через точку P горизонтальную полупрямую с правым концом в точке P. Так как ломаная ограничена, то всегда легко найти на этой полупрямой доста- точно удаленную точку Q, которая заведомо не принадлежит многоугольнику. Если отрезок QP не имеет пересечений с границей многоугольника, то точки Q и P ле- жат в одной компоненте связности и, следовательно, точка P — внешняя. Рассмотрим случай, когда отрезок QP пересекает ломаную (рис. 3.7). Будем двигаться от точки Q в направлении к точке P. Миновав первое пересечение от- резка и границы, мы попадем внутрь многоугольника. Миновав следующее пере- сечение отрезка и границы, мы окажемся снаружи многоугольника, и так далее.

Рис. 3.7 – Тест принадлежности точки многоугольнику Легко видеть, что если мы встретим на своем пути четное число пересечений, то точка P будет внешней точкой многоугольника. Если же число пересечений окажется нечетным, то точка P будет внутренней точкой многоугольника. Важно только удостовериться, что пересечения отрезка с границей были существенными, т. е. отрезок действительно пересек ломаную, а не просто касался ее в одной из вершин

Фракталы

Фрактальная графика основана на автоматической генерации изображений пу- тем математических расчетов. Создание фрактальных изображений основано не в рисовании, а в программировании. Фрактальная графика редко используется в печатных или электронных документах.

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

С точки зрения компьютерной графики, фрактальная геометрия незаменима при генерации облаков, гор, поверхности моря. Фактически найден способ легкого представления сложных неевклидовых объектов, образы которых весьма похожи на природные [10, 13]. Определение фрактала, данное Мандельбротом, звучит так: «Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому.»

Одним из основных свойств фракталов является самоподобие. В самом простом случае небольшая часть фрактала содержит информацию о всем фрактале. Фрактал можно определить, как объект довольно сложной формы, получающийся в результате выполнения простого итерационного цикла. Итерационность, рекурсивность обуславливают такие свойства фракталов, как самоподобие — отдельные части похожи по форме на весь фрактал в целом [13].

Мандельброт: zk+1 = z 2 k + z0, k = 0, 1, . . ., n

Цикл итераций для фрактала Мандельброта можно выполнять в диапазоне x = (от − 2.2 до 1), y = (от − 1.2 до 1.2). Для того чтобы получить изображение в растре, необходимо пересчитывать координаты этого диапазона в пиксельные.

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

Джулия: zk+1 = z 2 k + c,

где c — комплексная константа. Условием завершения итераций является ∣zk ∣ > 2 — так же, как для фрактала Мандельброта. На рис. 1.6 приведено два изображения фрактала Джулия для c = 0.36 + i ⋅ 0.36, изображение построено в границах x ∈ [−1, 1], y ∈ [−1.2, 1.2]. На рис. 1.6, б показан увеличенный фрагмент фрактала. Как видим, фрактал самоподобный — при любом увеличении отдельные части напоминают формы целого.

Ньютон: zk+1 = 3z 4 k + 1 4z 3 k ,

где z — также комплексные числа, причем z0 = x + i ⋅ y соответствует координатам точки изображения. Условием прекращения цикла итераций для фрактала Ньютон есть приближе- ние значений ∣z 4 − 1∣ к нулю. Например, изображение на рис. 1.7 было получено для ∣z 4 − 1∣ 2 > 0.001, границы расчета x ∈ [−1, 1], y ∈ [−1, 1].

Фрактальное сжатие

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

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

Нам пригодятся следующие:

Метрика — функция, заданная на пространстве, возвращающая расстояние между двумя точками этого пространства. Например, привычная нам Эвклидова метрика. Если на пространстве задана метрика, оно называется метрическим. Метрика должна удовлетворять определенным условиям, но не будем углубляться.

Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.

Сжимающие отображения обладают важным свойством. Если взять любую точку и начать итеративно применять к ней одно и то же сжимающее отображение: f(f(f...f(x))), то результатом будет всегда одна и та же точка. Чем больше раз применим, тем точнее найдем эту точку. Называется она неподвижной точкой и для каждого сжимающего отображения она существует, причем только одна.

Несколько аффинных сжимающих отображений образуют систему итерированных функций (СИФ). По сути, СИФ — это множительная машина. Она принимает исходное изображение, искажает его, перемещает, и так несколько раз.

Например, вот так при помощи СИФ из трех функций строится треугольник Серпинского:

Не нашли, что искали? Воспользуйтесь поиском по сайту: