ПОЛИГОНАЛЬНЫЕ СЕТКИ
Как отмечалось, полигональная сетка представляет собой набор вершин, ребер и плоских многоугольников. Вершины соединяются ребрами. Многоугольники рассматриваются либо как последовательность вершин или ребер. Можно предложить много способов внутреннего представления полигональных сеток. На рис. 2 изображен простой пример полигональной сетки из четырех многоугольников с девятью вершинами и двенадцатью ребрами. На рис. 3-5 рассмотрены несколько различных представлений и приведены соображения по их эффективности и удобству манипулирования.
Рис. 2. - Пример полигональной сетки: Pi - многоугольники, Vj - вершины, Ek - ребра
Рис. 3. Представление полигональной сетки с явным заданием многоугольников
Компактно для одного многоугольника, но сильно избыточно для набора, так как не существует общего описания общих вершин и ребер.
Рис. 4. Представление полигональной сетки с указателями на списки вершин
Элементы списка указателей на вершины для каждого многоугольника ссылаются на соответствующие координатные данные для вершин. Данное представление компактнее предыдущего, но трудно найти многоугольники с общими ребрами.
Рис. 5. Представление полигональной сетки в виде списка ребер
Элементы списка ребер содержат указатели на вершины в списке вершин, образующие данное ребро. Для обеспечения поиска всех вершин, образующих данный многоугольник, необходимо иметь обратные указатели от вершины на одно из инцидентных к ней ребер.
|
