ต้นทุนต่ำสุด สามเหลี่ยมหลายเหลี่ยม

เมื่อเส้นทแยงมุมที่ไม่ตัดกันสร้างรูปสามเหลี่ยมในรูปหลายเหลี่ยม จะเรียกว่าสามเหลี่ยม งานของเราคือการหาต้นทุนขั้นต่ำของสมการสามเหลี่ยม

ต้นทุนของรูปสามเหลี่ยมคือผลรวมของน้ำหนักของสามเหลี่ยมส่วนประกอบ เราสามารถหาน้ำหนักของสามเหลี่ยมแต่ละรูปได้โดยบวกข้างของพวกมัน หรืออีกนัยหนึ่ง น้ำหนักคือเส้นรอบรูปของสามเหลี่ยม

อินพุตและเอาต์พุต

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