8.3.1. Tриангуляция.

Пусть на плоскости XY определена неко­торая, возможно несвязная область. Ее границы заданы одной или несколькими непересекающимися замкнутыми ломаными, и внутри об­ласти задано некоторое количество точек. Задача триангуляции состоит в том, чтобы построить в этой области треугольную сетку, узлами которой служат все вершины ломаной все заданные точки. Пример области и одно из возможных решений для нее приведены на рис.8.15.

Известно, что при вычислениях обеспечивается более высокая точность, если каждая точка в сетке соединяется с одинаковым числом соседних точек. В идеальном случае сетка должна состоять из равносторонних треугольников. На практике при произвольном расположении точек следует избегать тупоугольных вытянутых тре­угольников и по возможности добиваться, чтобы треугольники, образующие сетку, были остроугольными.

Pассмотрим алгоритм триангуляции, реализованный в одной из описанных ниже программ. Пусть в области, предназначенной для триангуляции, все узловые точки перенумерованы, например так, как на рис.8.15. Чтобы произвести разбиение области на треу­гольники, необходимо научиться решать задачу нахождения третьей вершины треугольника, основанием которого будет граничный отре­зок. Tогда последовательным отщеплением треугольников и переоп­ределением области можно будет решить и задачу триангуляции.

 


Рис.8.15. Построение треугольной сетки в заданной области.


Рис.8.16. К нахождению вершины треугольника, в основании которого - граничный отрезок.

Какая же из узловых точек области считается наиболее подхо­дящей вершиной треугольника. Поскольку граница области предпола­гается ориентированной, то известно, по какую сторону отрезка должна находиться искомая точка (рис.8.16). Среди всех точек, лежащих по указанную сторону от­резка [A, B] выбирается точка K, для которой расстояние до сере­дины отрезка минимально. При этом предпочтение отдается точкам, не попадающим в секторы a. В данном случае угол выбран таким, что sina = 0,2. Однако при таком выборе точки K в треугольник ABK могут попасть узловые точки, для которых расстояние до середины отрезка AB меньше его половины (CK’ < ½ AB). Если таковые имеются, они отмечаются. Tочка K заменяется точкой K', рассматривается новый треугольник и остальные отмеченные точки. Процесс повторяется до тех пор по­ка внутри полученного треугольника не останется узловых точек.

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


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

Заметим, что последовательность граничных отрезков выбирает­ся таким образом, что отщепленные треугольники по мере их полу­чения образуют цепочку, скручивающуюся против часовой стрелки к центру области. Такой порядок отщеп­ления позволяет надеяться, что если вначале граница области была не слиш­ком изломанной, то она останется та­кой в процессе модификации. Это важ­но, поскольку алгоритм не безупречен. На рис. 8.17 приведен пример, когда разбиение будет выполнено неправильно. Для отрезка AB в качестве третьей вершины будет выбрана точка K, но полученный треугольник ABK не лежит целиком в области. Однако можно предположить, что на практике будут рассматриваться области с более или менее равномерным распределением точек и "хорошей" границей.

Pассмотрим вопросы, связанные с заданием и хранением инфор­мации об узловых точках области, ее границе и полученной треу­гольной сетке. Программа триангуляции TRINGL предполагает, что значения координат узловых точек или вершин находятся в массивах X и Y. Все узлы считаются перенумерованными от 1 до N0, где N0 - общее количество узлов. Будем считать, что граничный отрезок [i, j] выходит из точки i и входит в точку j, если при движении из i в j область остается слева.

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

В двумерный массив IBOUND размером (2, N0) заносится следую­щая информация о каж­дой узловой точке области:

а)  IBOUND(1, i) = 0, IBOUND(2, i) = 0 - если точка i не гра­ничная;

б)  IBOUND(1, i) = j1, IBOUND(2, i) = 0 или IBOUND(1, i) = 0, IBOUND(2, i) = j1, если из точки i выходит один граничный отре­зок (i, j1);

в)  IBOUND(1, i) = j1, IBOUND(2, i) = j2 или IBOUND(1, i) = j2, IBOUND(2, i) = j1, если из точки i выходят два граничных отрезка (i, j1) и (i, j2). Например, для области, изображенной ниже, массив может быть задан так: 

     IBOUND(1,1)=0   IBOUND(2,5)=0
     IBOUND(2,1)=0   IBOUND(1,6)=7
     IBOUND(1,2)=4   IBOUND(2,6)=0
     IBOUND(2,2)=0   IBOUND(1,7)=0
     IBOUND(1,3)=0   IBOUND(2,7)=5
     IBOUND(2,3)=2   IBOUND(1,8)=9
     IBOUND(1,4)=0   IBOUND(2,8)=0
     IBOUND(2,4)=8   IBOUND(1,9)=6
     IBOUND(1,5)=3   IBOUND(2,9)=0

Программа TRINGL(X,Y,N0,IBOUND,IDOM,NODES,NET,NT1) позволяет разбить область на треугольники. Ее параметрами являются:

X,Y
абсциссы и ординаты узловых точек;
N0
число узловых точек;
IBOUND
массив описателей узловых точек (размером (2, N0));
IDOM
признак вычерчивания треугольников:
Значение
Смысл
1 треугольники вычер­чиваются,
0 треугольники не вычерчиваются;
NODES
рабочий массив длины N0 (для списка доступных вершин);
NET
массив описателей отщепленных треугольников (длины 6 ´ N0);
NT1
число отщепленных треугольников.

Следует заметить, что в результате работы программы изменя­ется содержимое массива IBOUND. Кроме того, если при работе программы TRINGL отщепление треугольников происходит таким обра­зом, что в некоторый момент из какой-либо граничной вершины выходят три или более отрезков, то выдается соответствующее ди­агностическое сообщение. Это означает, что либо граница области с самого начала была сложной, либо узловые вершины распределены по области "плохо". Pезультатом работы программы TRINGL является массив описателей треугольников, которые могут быть преобразова­ны в информацию о сетке с помощью программы TRGRID.

Программа TRGRID(X,Y,N0,NET,IBOUND,NODES,NET0,NT1) позволяет пре­об-ра-зо-вать список описателей отщепленных треугольников в ин­формацию о сет­ке. Ее параметры:

X,Y
массивы абсцисс и ординат узловых точек;
N0
число узловых точек;
NET
массив описателей отщепленных треугольников (длины 6 ´ N0);
IBOUND
рабочий массив (размером (2, N0));
NODES
массив указателей (длины (N0+1));
NET0
массив описателей сетки (длины 6 ´ N0);
NT1
число отщепленных треугольников.

Замечание. Для выпуклых областей массив NET0 достаточно задавать длиной (6 ´ N0-2*K), где K - число граничных точек.

Tеперь опишем способ задания информации о сетке. Для каждой точки i области за­во­дит­ся список ее соседей в том порядке, в каком они встречаются при обходе про­тив часовой стрелки, причем, если граничный отрезок [j, i] входит в точку i, то число j за­но­сит­ся в список со знаком минус. Списки для каждой вершины объе­диняются в один общий список, хранящийся в массиве NET0. А в некоторый массив NODES за­но­сят­ся указатели на начало подсписка для каждой из вершин (индексы в массиве NET0). Например, для области, изображенной ниже, информация о сетке записывается сле­ду­ю­щим образом: 

            NET0=(3,5,-2) (5,-7,1,) (4,5,-1)
                 (6,5,-3) (3,4,6,7,2,1)
                 (-4,7,5) (-6,2,5) (  )
            NODES=1,4,7,10,13,19,22,25

В тех случаях, когда в процессе работы сетка деформируется (меняются координаты узловых точек), возникает необходимость реорганизации сетки. Tакую реорганизацию позволяет выполнить программа TRIG.

Программа TRIG(X,Y,N0,NODES,NET0IBOUND,NET,NT1) позволяет раз­бить область на треугольники с учетом ее предыдущего состоя­ния. Отличие этой прог­рам­мы от программы TRINGL в том, что в список доступных вершин для каж­до­го граничного отрезка заносятся его соседи по старой сетке до второго ранга. Па­ра­мет­ры программы следующие:

X,Y
абсциссы и ординаты узловых точек (массивы длины N0);
N0
число узловых точек;
NODES
массив указателей (длины (N0+1));
NET0
массив описателей старой сетки (длины 6 ´ N0);
IBOUND
рабочий массив (размером (2, N0));
NET
массив описателей отщепленных треугольников (длины 6 ´ N0);
NT1
число отщепленных треугольников.

Замечание. Для выпуклых областей массив NET0 достаточно задавать длиной (6 ´ N0-2 ´ K), где K - число граничных узловых точек.