ন্যূনতম খরচে পলিগন ট্রায়্যাঙ্গুলেশন

যখন একটি পলিগনে নন-ইন্টারসেক্টিং ডায়াগোনাল দ্বারা ত্রিভুজ তৈরি করা হয়, তখন তাকে ট্রায়্যাঙ্গুলেশন বলে। আমাদের কাজ হল ট্রায়্যাঙ্গুলেশনের ন্যূনতম খরচ বের করা।

ট্রায়্যাঙ্গুলেশনের খরচ হল তার উপাদান ত্রিভুজগুলোর ওজনের যোগফল। প্রতিটি ত্রিভুজের ওজন তাদের বাহুগুলো যোগ করে বের করা যায়, অর্থাৎ ওজন হল ত্রিভুজের পরিসীমা।

ইনপুট এবং আউটপুট

ইনপুট: একটি পলিগনের বিন্দুগুলো।
{(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)}

আউটপুট: ট্রায়্যাঙ্গুলেশনের মোট খরচ। এখানে খরচ ১৫.৩০০৬।

অ্যালগরিদম

minCost(polygon, n)

এখানে cost() ফাংশন ত্রিভুজের পরিসীমা বের করতে ব্যবহৃত হবে।

ইনপুট: পলিগন তৈরির জন্য বিন্দু সেট এবং বিন্দু সংখ্যা।
আউটপুট: পলিগন ট্রায়্যাঙ্গুলেশনের ন্যূনতম খরচ।

শুরু
  যদি n < 3 হয়, তবে
    ফেরত দিন 0
  n x n ক্রমের টেবিল সংজ্ঞায়িত করুন
  i := 0
  gap := 0 থেকে n-1 পর্যন্ত, করুন
    j := gap থেকে n-1 পর্যন্ত, করুন
      যদি j < i+2 হয়, তবে
        table[i,j] := 0
      অন্যথায়
        table[i, j] = ∞
        k := i+1 থেকে j-1 পর্যন্ত, করুন
          val := table[i, k] + table[k, j] + cost(i, j, k)
          যদি table[i, j] > val হয়, তবে
            table[i, j] := val
        শেষ
      i := i + 1
    শেষ
  শেষ
  table[0, n-1] ফেরত দিন
শেষ

উদাহরণ (C++)

#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) {
  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);
}

double minimumCost(Point polygon[], int n) {
  if (n < 3) 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;
        }
      }
    }
  }
  return table[0][n-1];
}

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

আউটপুট

The minimum cost: 15.3006