Minimum Cost Polygon Triangulation - GeeksforGeeks
Read full article from Minimum Cost Polygon Triangulation - GeeksforGeeks
A triangulation of a convex polygon is formed by drawing diagonals between non-adjacent vertices (corners) such that the diagonals never intersect. The problem is to find the cost of triangulation with the minimum cost. The cost of a triangulation is sum of the weights of its component triangles. Weight of each triangle is its perimeter (sum of lengths of all sides)
This problem has recursive substructure. The idea is to divide the polygon into three parts: a single triangle, the sub-polygon to the left, and the sub-polygon to the right. We try all possible divisions like this and find the one that minimizes the cost of the triangle plus the cost of the triangulation of the two sub-polygons.
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, j) is
cost(i, j, k) = dist(i, j) + dist(j, k) + dist(k, j)
dynamic programming solution:
Time complexity of the above dynamic programming solution is O(n3).
Please note that the above implementations assume that the points of covnvex polygon are given in order (either clockwise or anticlockwise)
Exercise:
Extend the above solution to print triangulation also. For the above example, the optimal triangulation is 0 3 4, 0 1 3, and 1 2 3.
struct Point
{
int x, y;
};
// A utility function to find distance between two points in a plane
double dist(Point p1, Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y));
}
// A utility function to find cost of a triangle. The cost is considered
// as perimeter (sum of lengths of all edges) of the triangle
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);
}
// A Dynamic programming based function to find minimum cost for convex
// polygon triangulation.
double mTCDP(Point points[], int n)
{
// There must be at least 3 points to form a triangle
if (n < 3)
return 0;
// table to store results of subproblems. table[i][j] stores cost of
// triangulation of points from i to j. The entry table[0][n-1] stores
// the final result.
double table[n][n];
// Fill table using above recursive formula. Note that the table
// is filled in diagonal fashion i.e., from diagonal elements to
// table[0][n-1] which is the result.
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];
}
Following is C++ implementation of above naive recursive formula.// A recursive function to find minimum cost of polygon triangulation// The polygon is represented by points[i..j].double mTC(Point points[], int i, int j){ // There must be at least three points between i and j // (including i and j) if (j < i+2) return 0; // Initialize result as infinite double res = MAX; // Find minimum triangulation by considering all 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;}