Рубрики

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

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

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

Две триангуляции одного и того же выпуклого пятиугольника. Триангуляция слева имеет стоимость 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 3 ).

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