Una triangulación de un polígono convexo se forma dibujando diagonales entre vértices no adyacentes (esquinas) de modo que las diagonales nunca se crucen. El problema es encontrar el costo de la triangulación con el costo mínimo. El costo de una triangulación es la suma de los pesos de los triángulos que la componen. El peso de cada triángulo es su perímetro (suma de las longitudes de todos los lados)
Vea el siguiente ejemplo tomado de esta fuente.
Dos triangulaciones del mismo pentágono convexo. La triangulación de la izquierda tiene un costo de 8 + 2√2 + 2√5 (aproximadamente 15,30), la de la derecha tiene un costo de 4 + 2√2 + 4√5 (aproximadamente 15,77).
Este problema tiene una subestructura recursiva. La idea es dividir el polígono en tres partes: un solo triángulo, el sub-polígono a la izquierda y el sub-polígono a la derecha. Probamos todas las divisiones posibles como esta y encontramos la que minimiza el costo del triángulo más el costo de la triangulación de los dos subpolígonos.
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, i) is
cost(i, j, k) = dist(i, j) + dist(j, k) + dist(k, i)
A continuación se muestra la implementación de la fórmula recursiva ingenua anterior.
C++
// Recursive implementation for minimum cost convex polygon triangulation
#include <iostream>
#include <cmath>
#define MAX 1000000.0
using namespace std;
// Structure of a point in 2D plane
struct Point
{
int x, y;
};
// Utility function to find minimum of two double values
double min(double x, double y)
{
return (x <= y)? 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 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;
}
// Driver program to test above functions
int main()
{
Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
int n = sizeof(points)/sizeof(points[0]);
cout << mTC(points, 0, n-1);
return 0;
}
Java
// Class to store a point in the Euclidean plane
class Point
{
int x, y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
// Utility function to return the distance between two
// vertices in a 2-dimensional plane
public double dist(Point p)
{
// The distance between vertices `(x1, y1)` & `(x2,
// y2)` is `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return Math.sqrt((this.x - p.x) * (this.x - p.x)
+ (this.y - p.y) * (this.y - p.y));
}
}
class GFG
{
// Function to calculate the weight of optimal
// triangulation of a convex polygon represented by a
// given set of vertices `vertices[i..j]`
public static double MWT(Point[] vertices, int i, int j)
{
// If the polygon has less than 3 vertices,
// triangulation is not possible
if (j < i + 2)
{
return 0;
}
// keep track of the total weight of the minimum
// weight triangulation of `MWT(i,j)`
double cost = Double.MAX_VALUE;
// consider all possible triangles `ikj` within the
// polygon
for (int k = i + 1; k <= j - 1; k++)
{
// The weight of a triangulation is the length
// of perimeter of the triangle
double weight = vertices[i].dist(vertices[j])
+ vertices[j].dist(vertices[k])
+ vertices[k].dist(vertices[i]);
// choose the vertex `k` that leads to the
// minimum total weight
cost = Double.min(cost,
weight + MWT(vertices, i, k)
+ MWT(vertices, k, j));
}
return cost;
}
// Driver code
public static void main(String[] args)
{
// vertices are given in clockwise order
Point[] vertices
= { new Point(0, 0), new Point(2, 0),
new Point(2, 1), new Point(1, 2),
new Point(0, 1) };
System.out.println(MWT(vertices,
0, vertices.length - 1));
}
}
// This code is contributed by Priiyadarshini Kumari
Python3
# Recursive implementation for minimum # cost convex polygon triangulation from math import sqrt MAX = 1000000.0 # A utility function to find distance # between two points in a plane def dist(p1, p2): return sqrt((p1[0] - p2[0])*(p1[0] - p2[0]) + \ (p1[1] - p2[1])*(p1[1] - p2[1])) # A utility function to find cost of # a triangle. The cost is considered # as perimeter (sum of lengths of all edges) # of the triangle def cost(points, i, j, k): p1 = points[i] p2 = points[j] p3 = points[k] return dist(p1, p2) + dist(p2, p3) + dist(p3, p1) # A recursive function to find minimum # cost of polygon triangulation # The polygon is represented by points[i..j]. def mTC(points, i, 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 res = MAX # Find minimum triangulation by considering all for k in range(i + 1, j): res = min(res, (mTC(points, i, k) + \ mTC(points, k, j) + \ cost(points, i, k, j))) return round(res, 4) # Driver code points = [[0, 0], [1, 0], [2, 1], [1, 2], [0, 2]] n = len(points) print(mTC(points, 0, n-1)) # This code is contributed by SHUBHAMSINGH10
C#
using System;
using System.Collections.Generic;
// Class to store a point in the Euclidean plane
public class Point {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// Utility function to return the distance between two
// vertices in a 2-dimensional plane
public double dist(Point p) {
// The distance between vertices `(x1, y1)` & `(x2,
// y2)` is `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return Math.Sqrt((this.x - p.x) * (this.x - p.x) +
(this.y - p.y) * (this.y - p.y));
}
}
public class GFG {
// Function to calculate the weight of optimal
// triangulation of a convex polygon represented by a
// given set of vertices `vertices[i..j]`
public static double MWT(Point[] vertices, int i, int j) {
// If the polygon has less than 3 vertices,
// triangulation is not possible
if (j < i + 2) {
return 0;
}
// keep track of the total weight of the minimum
// weight triangulation of `MWT(i,j)`
double cost = 9999999999999.09;
// consider all possible triangles `ikj` within the
// polygon
for (int k = i + 1; k <= j - 1; k++) {
// The weight of a triangulation is the length
// of perimeter of the triangle
double weight = vertices[i].dist(vertices[j]) +
vertices[j].dist(vertices[k])
+ vertices[k].dist(vertices[i]);
// choose the vertex `k` that leads to the
// minimum total weight
cost = Math.Min(cost, weight +
MWT(vertices, i, k) +
MWT(vertices, k, j));
}
return Math.Round(cost,4);
}
// Driver code
public static void Main(String[] args) {
// vertices are given in clockwise order
Point[] vertices = { new Point(0, 0),
new Point(2, 0),
new Point(2, 1),
new Point(1, 2),
new Point(0, 1) };
Console.WriteLine(MWT(vertices, 0, vertices.Length - 1));
}
}
// This code is contributed by gauravrajput1
Javascript
// A JavaScript program for a
// Recursive implementation for minimum cost convex polygon triangulation
const MAX = 1.79769e+308;
// Utility function to find minimum of two double values
function min(x, y)
{
return (x <= y)? x : y;
}
// A utility function to find distance between two points in a plane
function dist(p1, p2)
{
return Math.sqrt((p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]));
}
// A utility function to find cost of a triangle. The cost is considered
// as perimeter (sum of lengths of all edges) of the triangle
function cost(points, i, j, k)
{
p1 = points[i], p2 = points[j], p3 = points[k];
return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);
}
// A recursive function to find minimum cost of polygon triangulation
// The polygon is represented by points[i..j].
function mTC(points, i, 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
let res = MAX;
// Find minimum triangulation by considering all
for (let k=i+1; k<j; k++){
res = min(res, (mTC(points, i, k) + mTC(points, k, j) + cost(points, i, k, j)));
}
return res;
}
// Driver program to test above functions
{
let points = [[0, 0], [1, 0], [2, 1], [1, 2],[0, 2]]
let n = points.length;
console.log(mTC(points, 0, n-1));
}
// The code is contributed by Nidhi Goel
Producción:
15.3006
El problema anterior es similar a Matrix Chain Multiplication . El siguiente es un árbol de recursión para mTC (puntos [], 0, 4).
Se puede ver fácilmente en el árbol de recurrencia anterior que el problema tiene muchos subproblemas superpuestos. Dado que el problema tiene ambas propiedades: subestructura óptima y subproblemas superpuestos , se puede resolver de manera eficiente mediante programación dinámica.
A continuación se muestra la implementación en C++ de la solución de programación dinámica.
C++
// A Dynamic Programming based program to find minimum cost of convex
// polygon triangulation
#include <iostream>
#include <cmath>
#define MAX 1000000.0
using namespace std;
// Structure of a point in 2D plane
struct Point
{
int x, y;
};
// Utility function to find minimum of two double values
double min(double x, double y)
{
return (x <= y)? 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];
}
// Driver program to test above functions
int main()
{
Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
int n = sizeof(points)/sizeof(points[0]);
cout << mTCDP(points, n);
return 0;
}
Java
// A Dynamic Programming based program to find minimum cost
// of convex polygon triangulation
import java.util.*;
class GFG
{
// Structure of a point in 2D plane
static class Point {
int x, y;
Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Utility function to find minimum of two double values
static double min(double x, double y)
{
return (x <= y) ? x : y;
}
// A utility function to find distance between two
// points in a plane
static double dist(Point p1, Point p2)
{
return Math.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
static 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.
static 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 = new double[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] = 1000000.0;
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];
}
// Driver program to test above functions
public static void main(String[] args)
{
Point[] points = { new Point(0, 0), new Point(1, 0),
new Point(2, 1), new Point(1, 2),
new Point(0, 2) };
int n = points.length;
System.out.println(mTCDP(points, n));
}
}
// This code is contributed by Karandeep Singh
Python3
# A Dynamic Programming based program to find minimum cost # of convex polygon triangulation import math class GFG: # Structure of a point in 2D plane class Point: x = 0 y = 0 def __init__(self, x, y): self.x = x self.y = y # Utility function to find minimum of two double values @staticmethod def min(x, y): return x if (x <= y) else y # A utility function to find distance between two # points in a plane @staticmethod def dist(p1, p2): return math.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 @staticmethod def cost(points, i, j, k): p1 = points[i] p2 = points[j] p3 = points[k] return GFG.dist(p1, p2) + GFG.dist(p2, p3) + GFG.dist(p3, p1) # A Dynamic programming based function to find minimum # cost for convex polygon triangulation. @staticmethod def mTCDP(points, 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. table = [[0.0] * (n) for _ in range(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. gap = 0 while (gap < n): i = 0 j = gap while (j < n): if (j < i + 2): table[i][j] = 0.0 else: table[i][j] = 1000000.0 k = i + 1 while (k < j): val = table[i][k] + table[k][j] + \ GFG.cost(points, i, j, k) if (table[i][j] > val): table[i][j] = val k += 1 i += 1 j += 1 gap += 1 return table[0][n - 1] # Driver program to test above functions if __name__ == "__main__": points = [GFG.Point(0, 0), GFG.Point(1, 0), GFG.Point( 2, 1), GFG.Point(1, 2), GFG.Point(0, 2)] n = len(points) print(GFG.mTCDP(points, n)) # This code is contributed by Aarti_Rathi
C#
using System;
// A Dynamic Programming based program to find minimum cost
// of convex polygon triangulation
// Structure of a point in 2D plane
public class Point {
public int x;
public int y;
}
public static class Globals {
public const double MAX = 1000000.0;
// Utility function to find minimum of two double values
public static double min(double x, double y)
{
return (x <= y) ? x : y;
}
// A utility function to find distance between two
// points in a plane
public static double dist(Point p1, Point p2)
{
return Math.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
public static double cost(Point[] points, int i, int j,
int k)
{
Point p1 = points[i];
Point p2 = points[j];
Point 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.
public static 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 = new double[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];
}
// Driver program to test above functions
public static void Main()
{
Point[] points = { new Point(){ x = 0, y = 0 },
new Point(){ x = 1, y = 0 },
new Point(){ x = 2, y = 1 },
new Point(){ x = 1, y = 2 },
new Point(){ x = 0, y = 2 } };
int n = points.Length;
Console.Write(mTCDP(points, n));
}
}
// This code is contributed by Aarti_Rathi
Producción:
15.3006
La complejidad temporal de la solución de programación dinámica anterior es O(n 3 ).
Tenga en cuenta que las implementaciones anteriores asumen que los puntos del polígono convexo se dan en orden (ya sea en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj)
Ejercicio:
Amplíe la solución anterior para imprimir también la triangulación. Para el ejemplo anterior, la triangulación óptima es 0 3 4, 0 1 3 y 1 2 3.
Fuentes:
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture12.html
http:/ /www.cs.utoronto.ca/~heap/Courses/270F02/A4/chains/node2.html
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA