ПОЛИГОНАЛЬНЫЕ СЕТКИ

 

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

На рис. 2 изображен простой пример полигональной сетки из четырех многоугольников с девятью вершинами и двенадцатью ребрами. На рис. 3-5 рассмотрены несколько различных представлений и приведены соображения по их эффективности и удобству манипулирования.

 

Рис. 2. - Пример полигональной сетки: P_i - многоугольники, V_j - вершины, E_k - ребра

 

Рис. 3. Представление полигональной сетки с явным заданием многоугольников

 

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

 

Рис. 4. Представление полигональной сетки с указателями на списки вершин

 

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

 

Рис. 5. Представление полигональной сетки в виде списка ребер

 

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