최소 비용 다각형 삼각 측량

교차하지 않는 대각선이 다각형에서 삼각형을 형성하는 것을 삼각 측량이라고 합니다. 우리의 임무는 삼각 측량의 최소 비용을 찾는 것입니다.

삼각측량 비용은 구성 요소 삼각형의 가중치의 합입니다. 우리는 각 삼각형의 변을 더하여 무게를 찾을 수 있습니다. 즉, 무게는 삼각형의 둘레입니다.

입력 및 출력

Input:
The points of a polygon. {(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)}
Output:
The total cost of the triangulation. Here the cost of the triangulation is 15.3006.

알고리즘

minCost(polygon, n)

여기서 cost()는 삼각형의 둘레를 계산하는 데 사용됩니다.

입력: 폴리곤을 만들기 위한 점들의 집합과 다수의 점들

출력 - 다각형의 삼각 측량을 위한 최소 비용입니다.

Begin
   if n < 3, then
      return 0
   define table or order n x n
   i := 0

   for gap := 0 to n-1, do
      for j := gap to n-1, do
      if j < i+2, then
         table[i,j] := 0
      else
         table[i, j] = ∞
         for k := i+1 to j-1, do
            val := table[i, k] + table[k, j] + cost(i, j, k)
            if table[i, j] > val
               table[i, j] := val
      i := i + 1
      done
   done
   return table[0, n-1]
End

예시

#include <iostream>
#include <cmath>
#include <iomanip>
#define MAX 1000000.0
using namespace std;

struct Point {
   int x, y;
};

double min(double x, double y) {
   return (x <= y)? x : y;
}

double dist(Point p1, Point p2) {    //find distance from p1 to p2
   return sqrt(pow((p1.x-p2.x),2) + pow((p1.y-p2.y),2));
}

double cost(Point triangle[], int i, int j, int k) {
   Point p1 = triangle[i], p2 = triangle[j], p3 = triangle[k];
   return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);    //the perimeter of the triangle
}

double minimumCost(Point polygon[], int n) {
   if (n < 3)    //when polygon has less than 3 points
      return 0;
   double table[n][n];

   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(polygon,i,j,k);
               if (table[i][j] > val)
                  table[i][j] = val;    //update table data to minimum value
            }
         }
      }
   }  
   return  table[0][n-1];
}

int main() {
   Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
   int n = 5;
   cout <<"The minimumcost: " <<minimumCost(points, n);
}

출력

The minimumcost: 15.3006