Минимальная стоимость полигональной триангуляции

01.01.2020Геометрия, Динамическое программирование

Триангуляция выпуклого многоугольника формируется путем рисования диагоналей между несмежными вершинами (углами) так, что диагонали никогда не пересекаются. Задача состоит в том, чтобы найти стоимость триангуляции с минимальными затратами. Стоимость триангуляции — это сумма весов составляющих ее треугольников. Вес каждого треугольника является его периметром (сумма длин всех сторон)

Смотрите следующий пример, взятый из этого источника.

Две триангуляции одного и того же выпуклого пятиугольника. Триангуляция слева имеет стоимость 8 + 2√2 + 2√5 (примерно 15.30), а справа — 4 + 2√2 + 4√5 (примерно 15.77).

Эта проблема имеет рекурсивную подструктуру. Идея состоит в том, чтобы разделить многоугольник на три части: один треугольник, подполигон слева и подполигон справа. Мы пробуем все возможные деления, подобные этому, и находим тот, который минимизирует стоимость треугольника плюс стоимость триангуляции двух подполигонов.

Let Minimum Cost of triangulation of vertices from i to j be minCost(i, j)
If j <= i + 2 Then
  minCost(i, j) = 0
Else
  minCost(i, j) = Min { minCost(i, k) + minCost(k, j) + cost(i, k, j) }
                  Here k varies from 'i+1' to 'j-1'

Cost of a triangle formed by edges (i, j), (j, k) and (k, i) is 
  cost(i, j, k)  = dist(i, j) + dist(j, k) + dist(k, i)

Следующее — реализация C ++ вышеупомянутой наивной рекурсивной формулы.

// Рекурсивная реализация для минимальной стоимости выпуклой триангуляции многоугольника
#include <iostream>
#include <cmath>
#define MAX 1000000.0

using namespace std;

// Структура точки в 2D плоскости

struct Point

{

int x, y;

};

// Сервисная функция для поиска минимум двух двойных значений

double min(double x, double y)

{

return (x <= y)? x : y;

}

// Полезная функция для определения расстояния между двумя точками на плоскости

double dist(Point p1, Point p2)

{

return sqrt((p1.x - p2.x)*(p1.x - p2.x) +

(p1.y - p2.y)*(p1.y - p2.y));

}

// Полезная функция для определения стоимости треугольника. Стоимость считается
// как периметр (сумма длин всех ребер) треугольника

double cost(Point points[], int i, int j, int k)

{

Point p1 = points[i], p2 = points[j], p3 = points[k];

return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);

}

// Рекурсивная функция для нахождения минимальной стоимости триангуляции многоугольника
// Многоугольник представлен точками [i..j].

double mTC(Point points[], int i, int j)

{

// Между i и j должно быть как минимум три точки

// (включая i и j)

if (j < i+2)

return 0;

// Инициализировать результат как бесконечный

double res = MAX;

// Найти минимальную триангуляцию, учитывая все

for (int k=i+1; k<j; k++)

res = min(res, (mTC(points, i, k) + mTC(points, k, j) +

cost(points, i, k, j)));

return res;

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};

int n = sizeof(points)/sizeof(points[0]);

cout << mTC(points, 0, n-1);

return 0;

}

Выход:

15.3006

Вышеуказанная проблема аналогична умножению матрицы . Ниже приведено дерево рекурсии для mTC (points [], 0, 4).

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

Ниже приводится реализация C ++ решения для динамического программирования.

// Программа на основе динамического программирования для поиска минимальной стоимости выпуклых
// полигональная триангуляция
#include <iostream>
#include <cmath>
#define MAX 1000000.0

using namespace std;

// Структура точки в 2D плоскости

struct Point

{

int x, y;

};

// Сервисная функция для поиска минимум двух двойных значений

double min(double x, double y)

{

return (x <= y)? x : y;

}

// Полезная функция для определения расстояния между двумя точками на плоскости

double dist(Point p1, Point p2)

{

return sqrt((p1.x - p2.x)*(p1.x - p2.x) +

(p1.y - p2.y)*(p1.y - p2.y));

}

double cost(Point points[], int i, int j, int k)

{

Point p1 = points[i], p2 = points[j], p3 = points[k];

return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);

}

// Функция на основе динамического программирования для поиска минимальной стоимости выпуклого
// полигональная триангуляция.

double mTCDP(Point points[], int n)

{

// Для формирования треугольника должно быть не менее 3 точек

if (n < 3)

return 0;

// таблица для хранения результатов подзадач. Таблица [I] [J] хранит стоимость

// триангуляция точек от i до j. Таблица записей [0] [n-1] магазинов

// окончательный результат.

double table[n][n];

// Заполнить таблицу, используя приведенную выше рекурсивную формулу. Обратите внимание, что таблица

// заполняется по диагонали, т.е. от диагональных элементов до

// таблица [0] [n-1], которая является результатом.

for (int gap = 0; gap < n; gap++)

{

for (int i = 0, j = gap; j < n; i++, j++)

{

if (j < i+2)

table[i][j] = 0.0;

else

{

table[i][j] = MAX;

for (int k = i+1; k < j; k++)

{

double val = table[i][k] + table[k][j] + cost(points,i,j,k);

if (table[i][j] > val)

table[i][j] = val;

}

return table[0][n-1];

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};

int n = sizeof(points)/sizeof(points[0]);

cout << mTCDP(points, n);

return 0;

}

Выход:

15.3006

Временная сложность приведенного выше решения динамического программирования составляет O (n ³ ).

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

Упражнение:
Расширьте вышеупомянутое решение для печати триангуляции также. Для приведенного выше примера оптимальной триангуляцией является 0 3 4, 0 1 3 и 1 2 3.

Источники:
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture12.html
http://www.cs.utoronto.ca/~heap/Courses/270F02/A4/chains/node2.html

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Минимальная стоимость полигональной триангуляции

0.00 (0%) 0 votes