5.8.5 Задача триангуляции многоугольника

Рисунок 5.17 – Иллюстрация к задаче триангуляции

Имеется выпуклый n-угольник Р_n = (v₁, v₂...v_n). Надо разбить его на непересекающиеся треугольники так, чтобы сумма длин отрезков разбиения была наименьшей. На рисунке показано два возможных ва- рианта триангуляции шестиуголь- ника. Будем решать данную задачу в соответствии с вышеизложенными пунктами.

Договоримся обозначать символом Р_i..j = (v_i...v_j) многоугольник, обра- зованный вершинами от v_i до v_j (ij), а символом  треугольник с вершинами v_k, v_l, v_m. Таким образом, Р_1..n  это исходный много- угольник. Пусть d(v_i, v_j) равняется длине отрезка между вершинами v_i и v_j), если v_iv_j  диагональ много- угольника и d(v_i, v_j) = 0, если v_iv_j  его сторона. Пусть f(i..j)  сумма длин отрезков оптимального раз- биения многоугольника Р_i..j на тре- угольники. Заметим следующее: из условия непересекаемости треу- гольников следует, что каждое реб- ро Р_1..n входит ровно в один из тре- угольников. В частности это каса- ется и ребра v₁v_n которое с некоей вершиной k (1 < k < n) образует . Тогда рассмотрим два ос- тавшиеся многоугольника Р_1..k и Р_k..n, которые в нашем случае и бу- дут ни чем иным, как подзадачами. Если для всех таких подзадач (при разных k) уже найдено оптималь- ное решение, то остается лишь вы- брать оптимальное значение k.

В задаче требуется найти f(1..n). Построим формулу для нахожде- ния f(i..j)  суммы длин отрезков триангуляции для многоугольника Р_i..j. Имеет место следующая зави- симость:

Формула следует из того, что вы- брав вершину k, мы получаем два меньших многоугольника Р_i..k и Р_k..j, которые надо триангулировать далее и два отрезка (v_iv_k и v_kv_j), длины которых входят в нашу три- ангуляцию (если один из них  сто- рона многоугольника, то согласно выбору d его длина не будет учиты- ваться). Очевидно, что эта форму- ла соответствует рекурсивной про- цедуре с циклом по k внутри и входными параметрами i и j. Чем не принцип «разделяй и власт- вуй»? Почти, но не совсем.

Рисунок 5.18 – Разбиение на подзадачи при триангуляции

Покажем с помощью дерева, как будем собирать целостное реше- ние из решений подзадач для се- миугольника. Задача найти f(1..7) распалась на 5 пар задач (f(1..k), f(k..7)) для k=2..5. Далее каждая из подзадач рекурсивно разбивается на более мелкие, пока последние не ста- нут тривиальными (вида f(i..i+1) или f(i..i). Если присмотреться к этому дереву, видно, что одни и те же подзадачи на разных вет- ках дерева повторяются. Более того, повторяются не только три- виальные подзадачи (например, f(2..3) на голубых узлах), но и не- тривиальные (задача f(4..7) на зе- леных узлах), которые порожда- ют целые деревья рекурсивных вызовов.

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

const

InFileName = 'in.txt'; МахN = 50; NotCalculated = -1; MaxReal = 1e30;

var

N: integer; (количество вершин) d: array[1..MaxN, 1..MaxN] of real;

(расстояния между вершинами)

f: array[1..MaxN, 1..MaxN] of real;

(динамическая таблица решений)

Cut: аггау[1..иахМ, 1..MaxN] of integer;

(таблица для запоминания вершины разреза)

(функция нахождения расстояния между двумя точками}

function distance(x1,у1,х2,у2: real):real;

begin

distance := sqrt(sqr(xl-x2)+sqr(у1-у2));

end;

(процедура считывания входящих данных и нахождения расстояний

между вершинами)

procedure ReadData; var

ft: text; х,у: array[1..MaxN] of real;

i,j: integer;

begin

assign(ft,InFileName); reset(ft); read(ft,N); for i:= 1 to N do

readln(ft, x[1],у[i]);

close(ft);

for i:= 1 to N do

for j:= 1 to д do

begin

if abs(i-j) <= 1 then

(если это сторона, то) d[i,j]:=0 (в разрез она не войдет,

значит пусть ее длина=0)

еlsе d[i,j]:=Distance(x[i],у[1],х[2],у[2]);

f [i,j]:= NotCalculated;

(ставим отметку, что подзадача f(i,.j) не peшeнa)

end;

end;

(рекурсивная процедура поиска оптимального решения)

procedure Divide(i,j:integer); var k, minK: integer;

L, minL: real;

begin

if f[i,j] <> NotCalculated then

(если подзадача уже решалась, выходим) exit;

if i+2 >= j then begin

(если задача тривиальна (треугольник, отрезок или точка))

Cut[i,j] := 0; (то разбиений нет)

f [1,2] := 0; (и длина такого несуществующего разбиения

равна нулю)

exit;

end;

minL := MaxReal;

(ищем минимум no k (рекуррентная формула))

for k := 1<1 to j-1 do begin

Divide(i,k); (решаем подзадачу f(i..k))

Divide(k,j); (решаем подзадачу f(k..2})

L := P[i,k] + F[k,j] + D[i,k] + D[k,j];

if L < MinL then begin

MinL := L; (запоминаем минимальную длину}

MinK := k; (и точку разбиения)

end;

end;

F[i,j] MinL; (запоминаем оптимум в динамической таблице)

Cut[i,j] :=MinK;

end;

(процедура рекурсивно выводит разбиение)

procedure PrintCut(i,j integer) begin

if Cut[i,j] <> 0 then begin

if i+1 < Cut[i,j] then

WriteLn(i,'-',Cut[i,j]);

if Cut[i,j]+l < j then

WriteLn(Cut[i,j],'-',3);

PrintCut(i,Cut[1 3));

PrintCut(Cut[i,j],j);

end;

end;

begin

ReadData; (читаем входные данные) Divide(1,N); (выполняем разбиение) (выводим результаты) wreteln('Min(mal cut length:f[l,n]);

writeLn('Cut the polygon along these diagonals:');

PrintCut(1,N);

end.

Листинг 5.27 – ДП-алгоритм триангуляции многоугольника

Оптимальное решение будет нахо- диться в нашей таблице после вы- зова рекурсивной процедуры с па- раметрами (1, n).