न्यूनतम लागत पॉलीगॉन ट्राईएंगुलेशन

जब नॉन-इंटरसेक्टिंग डायगोनल्स एक पॉलीगॉन में ट्राईएंगल बनाते हैं, तो इसे ट्राईएंगुलेशन कहा जाता है। हमारा कार्य ट्राईएंगुलेशन की न्यूनतम लागत ढूंढना है।

ट्राईएंगुलेशन की लागत इसके घटक ट्राईएंगल्स के वजन का योग है। हम प्रत्येक ट्राईएंगल का वजन उनकी भुजाओं को जोड़कर ढूंढ सकते हैं, दूसरे शब्दों में, वजन ट्राईएंगल का परिमाप है।

इनपुट और आउटपुट

इनपुट: एक पॉलीगॉन के पॉइंट्स
{(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)}

आउटपुट: ट्राईएंगुलेशन की कुल लागत। यहां ट्राईएंगुलेशन की लागत 15.3006 है।

एल्गोरिदम

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 minimumcost: " << minimumCost(points, n);
}

आउटपुट

The minimumcost: 15.3006