Отсечение многоугольника по окну

Алгоритм Сазерленда-Хождмана

Алгоритм основан на поочередном отбрасывании вершин отсекаемого многоугольника и добавлением к нему новых вершин в точках пересечения ребер с окном. Последовательные шаги осуществления этого алгоритма показаны на рисунках:

А отброшена, 1 и 2 введены. В отброшена, 3 и 4 введены. 4 отброшена, 5 и6 введены. D отброшена, 7 и 8 введены. 8 отброшена, 9 и 10 введены. Задача решена.

Задача триангуляции

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

Как интуитивно понятно, задача имеет несколько решений:

Не всякая триагуляция воспринимается как «красивая». И эстетически, и из практических соображений хорошей считается триангуляция, треугольники которой по пропорциям по возможности близки к равносторонним. Делоне предложил способ триангуляции, который позволяет получить в среднем «неплохие» результаты.

Условие Делоне

• Триангуляция набора точек S назыается триангуляцией Делоне (Delaunay), если

• окружность, описанная вокруг каждого из треугольников, не будет содержать внутри себя других точек набора S.

Алгоритм триангуляции Делоне

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

Строго говоря, сходимость алгоритма строго не доказана и его результат зависит еще и от порядка перебора вершин. Но он показывает неплохие результаты на практике, поэтому ценен и полезен.

1. 

2. 

3)

4)

5)

6)

7)

N)

ИТОГИ

1. Алгоритмы вычислительной геометрии на плоскости основаны на методах плоскостной аналитической геометрии.

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

3. В вычислительной геометрии среди операций над векторами наибольшее значение имеют операции вычисления скалярного и векторного призведений двух векторов.

4 Трехмерная вычислительная геометрия план раздела

1. Описание плоскости через точку и нормаль.

2. Описание плоскости через инцидентные ей точки.

3. Описание плоскости через вершины полигона.

4. Точка встречи прямой и плоскости.

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