Декомпозиция полигонов на треугольники

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

Если внутренние углы при всех вершинах полигона меньше 0°, то такой полигон называется выпуклым. На рис. 5.2(б) утренний угол при вершине Р больше 180°. Такую вершину будем называть невыпуклой. Все другие вершины на рис. 3.8 - выпуклые. Если полигон имеет хотя бы одну невыпуклую вершину, то весь такой полигон будем называть невыпуклым.

Если А и В — две точки на границе выпуклого полигона, то и весь отрезок АВ будет принадлежать полигону. Для невыпуклых полигонов это условие может не соблюдаться.

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

Операция разбивки выпуклого полигона на треугольники чрезвычайно проста, как это видно из рис. 5.3. Если вершины полигона пронумеровать последовательно Р₀, Р₁..., Р_n-1 а за­тем вычертить диагонали Р₀Р₂, Р₀Р₃,... Р₀Р_n-2 то этого будет достаточно. В невыпуклом полигоне, как на рис. 3.9(6), этот простой способ работать не будет, поскольку некоторые из диагоналей Р₀Р₂, Р₀Р₃,... Р₀Р_n-2 могут выходить за пределы полигона.

Составим теперь программу, которая будет считывать координаты вершин полигона и выполнит разбиение полигона на треугольники. Требуется, чтобы вершины были указаны обяза­тельно в порядке обхода против часовой стрелки. Например, у полигона на рис. 5.3(6) верной окажется последовательность Р₄Р₅Р₆Р₀Р₁Р₂Р₃, а последовательность Р₆Р₅Р₄Р₃Р₂Р₁Р₀ будет непригодной. Для полигона с n вершинами сначала указывается количество вершин n, затем последовательно перечисляются n пар координат всех вершин в порядке обхода полигона против часовой стрелки. В результате будет получен чертеж полигона с вычерченными диагоналями, полностью разбивающими весь полигон на треугольники. Перед вычерчиванием диагоналей необходимо удостовериться, что рее диагонали лежат полностью внутри полигона.

Предположим, что Р_i-1, Р_i, Р_i+1 обозначают три соседние вершины, причем будем считать, что Р_-1 = Р_n-1 и P_n = Р₀, чтобы можно было рассматривать случаи, когда i = 0 и i = n - 1. Напомним, что вершины должны быть перечислены в порядке обхода против часовой стрелки. В этом случае Р_i будет выпуклой вершиной тогда, и только тогда, когда три вершины Р_i-1, Р_i, Р_i+1 именно в этом порядке будут обходиться в направлении против часовой стрелки.

В качестве контрпримера рассмотрим рис. 5.4, в котором обход тройки Р₁Р₂Р₃ выполняется по часовой стрелке. Вершина Р₂ является невыпуклой» и диагональ Р₁Р₃ лежит вне полигона. Таким образом, диагональ Р_i-1Р_i+1 может быть только кандидатом для наших целей, если три вершины Р_i-1(х_i-1, у_i-1), Р_i(х_i, у_i), Р_i+1(х_i+1, у_i+1), именно в этом порядке, обходятся в на­правлении против часовой стрелки, то есть если

| x_i-1 y_i-1 1 |

D = | x_i y_i 1 | > 0

| x_i+1 y_i+1 1 |

Это условие является необходимым, но, к сожалению, недо­статочным, как это показано на рис.5.5. Здесь точки Р₀, Р₁, Р₂ обходятся именно в таком порядке, в направлении против часовой стрелки, но отрезок Р₀Р₂ нельзя использовать для деления полигона на треугольники. Такой ситуации можно избежать, ели принимать во внимание также длину диагоналей. Будем выбирать наикратчайшую диагональ Р_i-1Р_i+2, которую может меть выпуклая вершина Р_i между точками Р_i-1 и Р_i+1. Эта диагональ используется для отсечения треугольника Р_i-1Р_iР_i+1. Затем таким же образом проверяется оставшийся полигон

Р₀, Р₁,..., Р_i-1, Р_i+1,..., Р_n-1

и так далее. Технически это реализуется введением целочисленного массива v₀,..., v_m-1, содержащего номера вершин оставше­юся полигона. Вначале задаем m = n и v_j = j (i = 0, 1,..., n - 1). Каждый раз при отсечении треугольника число m уменьшается на единицу. Если подобная программа предназначается для практического применения, то желательно выполнить некоторое число испытаний на допустимость входных данных. Программа, которая надежно отвергает любой непригодный набор данных, может быть названа устойчивой.

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

n x₀ y₀ x₁ y₁... x_n-1 y_n-1

вообще описывает полигон. Например, совершенно непригодна последовательность

4 1 1 2 2 2 1 1 2

поскольку обход точек в заданном порядке приведет к ситуации, оказанной на рис. 5.6, но в качестве полигона такую фигуру принять нельзя.

Из других проверок следует обратить внимание на:

- максимальное количество точек n, например, n £ 500;

- минимальное и максимальное значения координат;

- ориентацию обхода точек в направлении против часовой стрелки.

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

/* POLY_TRIA: Разбиение полигона на треугольники */

/* Dividing a polygon into triangles */

#define NMAX 500

#define BIG 1.0e30

#include "math.h"

#include "stdio.h"

#include "stdlib.h"

#include "grasptc0.h"

int n, v[NMAX];

float x[NMAX], y[NMAX];

void error_gr(char *str)

{ endgr();

printf(" %s ",str);

exit(1);

}

int counter_clock(int h,int i,int j,double *pdist)

{ double xh=x[v[h]], xi=x[v[i]], xj=x[v[j]],

yh=y[v[h]], yi=y[v[i]], yj=y[v[j]],

x_hi, y_hi, x_hj, y_hj, Determ;

x_hi=xi-xh; y_hi=yi-yh; x_hj=xj-xh; y_hj=yj-yh;

*pdist=x_hj * x_hj + y_hj * y_hj;

Determ = x_hi * y_hj - x_hj * y_hi;

return Determ > 1e-6;

}

void draw_polygon()

{ int i;

move(x[n-1], y[n-1]);

for (i=0; i<n; i++) draw(x[i], y[i]);

}

void dash(float x1,float y1,float x2,float y2)

{ int i, k;

float xdif=x2-x1, ydif=y2-y1, pitch0=0.3, dx, dy;

k=2*(int)(ceil(sqrt(xdif*xdif+ydif*ydif)/pitch0))+1;

dx=xdif/k; dy=ydif/k;

for (i=0; i<k; i+=2)

{ move(x1+i*dx, y1+i*dy);

draw(x1+(i+1)*dx, y1+(i+1)*dy);

}

}

void main()

{ int i, h, j, m, k, imin;

double diag, min_diag;

printf("%s %s ", “Задайте число вершин n и затем n пар координат вершин (x, у) ",

" в порядке обхода против часовой стрелки ");

scanf("%d", &n);

if (n>=NMAX) { printf (“Число n слишком велико "); exit(1); }

for (i=0; i<n; i++) {scanf("%f %f", &x[i], &y[i]); v[i]=i; }

initgr();

m=n;

draw_polygon();

while (m>3)

{ min_diag = BIG;

for (i=0; i<m; i++)

{ h = (i==0?m-1:i-1); j=(i==m-1?0:i+1);

if (counter_clock(h, i, j, &diag)&&(diag<min_diag))

{ min_diag=diag; imin=i;

}

}

i=imin; h=(i==0?m-1:i-1); j=(i==m-1?0:i+1);

if (min_diag==BIG)

error_gr("Неправильное направление обхода ");

dash(x[v[h]], y[v[h]], x[v[j]], y[v[j]]);

m--;

for (k=i; k<m; k++) v[k]=v[k+1];

}

endgr();

}

Следующая входная последовательность

1 1 6 1 6 4 4 4 4 3 5 3

5 2 2 2 2 3 3 3 3 4 1 4

приведет к выводу изображения, показанного на рис. 5.8.

Дата добавления: 2014-01-14