ДЕКОМПОЗИЦИЯ ПОЛИГОНОВ НА ТРЕУГОЛЬНИКИ

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

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

Составим теперь программу, которая будет считывать координаты вершин полигона и выполнит разбиение полигона на треугольники. Требуется, чтобы вершины были указаны обяза­тельно в порядке обхода против часовой стрелки. Например, у полигона на рис. 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 |

Р₀, Р₁, ..., Р_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.