Вычислительная геометрия

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

Алгоритм жадной триангуляции заключается в следующем:

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

Триангуляция Делоне множества точек - это такое разбиение множества точек на множество треугольников, что внутри окружности, описанной вокруг любого треугольника, не лежит ни одной точки из множества, кроме вершин самого треугольника.

Свойства:

1. Триангуляция Делоне единственна
2. Триангуляция Делоне максимизирует минимальный угол в треугольниках.

Задача

Для работы используется модифицированный алгоритм Брезенхейма для построения прямых. Обрабатываемый многоугольник обязательно должен быть невырожденным. Заливка произойдёт в любом случае, однако если у многоугольника есть самопересечения, то алгоритм может отработать некорректно. Алгоритм не чувствителен к порядку обхода, в котором заданы вершины многоугольника.

Замощение (паркет) — разбиение плоскости на многоугольники (мозаику) без наложений и зазоров с повторяющимся узором.

Виды паркетов

Теорема Бояйи-Гервина

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

Если абстрактно представить любой алгоритм заливки фигур (не специализированный для какой-то конкретной фигуры, а универсальный) то в нем обязательно обнаружится шаг с проверкой удовлетворяет ли выбранная точка некоторым условиям заливки. Чаще всего эти условия простые. Например, является ли цвет выбранной точки таким же, как и цвет точки, с которой началась заливка. Или еще проще — является ли выбранная точка отличной от цвета заливки. В этой статье предлагается сделать заливку более функциональной и «гибкой», изменив тривиальные условия заливки точки на более сложные.