精华内容
下载资源
问答
  • 计算几何多边形三角剖分

    热门讨论 2011-04-07 21:36:49
    多边形三角剖分是计算几何( Computational Geometry)中的经典问题,起源于一个有趣的艺术画廊问题。目前有很多不同的算法实现了对多边形的三角剖分,三角化算法所追求的目标主要有两个:形状匀称和计算速度快。 此...
  • 多边形三角剖分问题

    千次阅读 2016-08-27 19:11:16
    动态规划 凸多边形三角剖分问题

    1、问题定义:

         (1)凸多边形的三角剖分将凸多边形分割成互不相交的三角形的弦的集合T。

        (2)最优剖分给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分,使得该三角剖分中诸三角形上权之和为最小。

         凸多边形三角剖分如下图所示:


    2、优化解结构的分析

    设:
    – P=(v0,v1,...vn)是n+1个顶点的多边形
    – TP是P的优化三角剖分,包含三角形v0,vk,vn

    – TP=T(v0, ..., vk)∪T(vk, ..., vn)∪{v0,vk,vn}

    因此,可得递推关系式:

    这是一个划分动态规划问题,和矩阵链乘问题相似,只需将矩阵链乘问题的代码稍作修改即可。

    http://blog.csdn.net/z1185196212/article/details/52312194

    展开全文
  • 5047. 多边形三角剖分的最低得分 题目难度 Medium 题目描述 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。 假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形...

    5047. 多边形三角剖分的最低得分

    转载请注明出处
    附上我的博客链接 四元君
    题目难度 Medium

    题目描述

    给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。

    假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

    返回多边形进行三角剖分后可以得到的最低分。

    示例 1:

    输入:[1,2,3]
    输出:6
    解释:多边形已经三角化,唯一三角形的分数为 6。
    

    示例 2:
    img

    输入:[3,7,4,5]
    输出:144
    解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,或 3*4*5 + 3*4*7 = 144。最低分数为 144。
    

    示例 3:

    输入:[1,3,1,4,1,5]
    输出:13
    解释:最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
    

    提示:

    3 <= A.length <= 50
    1 <= A[i] <= 100
    

    解法

    基本的思路是动态规划。

    假设我们现在有一个六边形,我们用cost[i][j]存储由第i号顶点到第j号顶点所划定的三角形的值之和。如下图:
    img

    比如说我们选定cost[0][3],他表示从0号顶点到3号顶点的所有右侧的三角形值的和(右侧是我们的顺时针方向)。这个值的和可以有两种算法,一种是蓝色的S012+S023;一种是紫色的S013+S123。我们将所有的计算的值存储在一张表中,如下图:
    img

    将cost[i][i+1]的对角线初始化为0,意义为两个重合点无法构成三角形;cost[i][i+2]对角线初始化为由i,i+1,i+2三点构成的三角形的值。

    此后更新步长step,美更新一次意味着划定的区域多加入一个三角形,新的值由新的三角形面积和老的三角形面积共同决定,核心公式为:

    cost[当前目标] = min (cost[当前目标], cost[细分后三角形A] + cost[细分后三角形B]+ A[i] * A[j] * A[k]);
    

    cost[i][j] = min (cost[i][j], cost[i][k] + cost[k][j]+ A[i] * A[j] * A[k]);
    

    完整代码如下:

    class Solution {
    public:
        int cost[100][100];
        int minScoreTriangulation(vector<int>& A) {
            int n = A.size();
            for (int i = 0;i < n; ++ i) {
                for (int j = 0;j < n; ++ j) {
                    cost[i][j] = INT_MAX;
                }
            }
            for (int i = 0;i < n - 1; ++ i) {
                cost[i][i + 1] = 0;
            }
            
            for (int step = 2; step < n; ++ step) {
                for (int i = 0;i + step < n; ++ i) {
                    int j = i + step;
                    for (int k = i + 1;k <= j - 1; ++ k) {
                        cost[i][j] = min (cost[i][j], cost[i][k] + cost[k][j]+ A[i] * A[j] * A[k]);
                    }
                }
            }
            return cost[0][n-1];
        }
    };
    
    展开全文
  • 多边形三角剖分的最低得分 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。 假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分...

    题目

    多边形三角剖分的最低得分

    给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。

    假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

    返回多边形进行三角剖分后可以得到的最低分。

    示例二

    输入:[3,7,4,5]
    输出:144
    解释:有两种三角剖分,可能得分分别为:375 + 457 = 245,或 345 + 347 = 144。最低分数为 144。
    在这里插入图片描述

    思路分析

    • 令dp[i][j]为下标为[i,…,j]的最小三角形的最低得分。
    • 分为中间一个切分点k

    代码

    class Solution {
    public:
        int minScoreTriangulation(vector<int>& A) {
            int n = A.size();
            vector<vector<int>> dp(n, vector<int>(n, 0));
            for(int i = n - 3; i >= 0; i--){
                dp[i][i + 2] = A[i] * A[i + 1] * A[i + 2];
                for(int j = i + 3;j < n;j++){
                    dp[i][j] = 0x3f3f3f3f;
                    for(int k = i + 1;k < j;k++){
                        dp[i][j] = min(dp[i][j],A[i] * A[j] * A[k] + dp[i][k] + dp[k][j]);
                    }
                }
            }
            return dp[0][n - 1];
        }
    };
    
    
    展开全文
  • 多边形三角剖分的最低得分–LeetCode1039 题目 给定 N,想象一个凸 N边多边形,其顶点按顺时针顺序依次标记为 A[0],A[1],...,A[i],...,A[N-1]。假设您将多边形剖分为 N-2个三角形。对于每个三角形,该三角形的值是...

    多边形三角剖分的最低得分–LeetCode1039

    题目

    给定 N,想象一个凸 N边多边形,其顶点按顺时针顺序依次标记为 A[0],A[1],...,A[i],...,A[N-1]。假设您将多边形剖分为 N-2个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2个三角形的值之和。返回多边形进行三角剖分后可以得到的最低分。

    示例 1:

    输入:[1,2,3]
    输出:6
    解释:多边形已经三角化,唯一三角形的分数为 6。
    

    示例 2:
    在这里插入图片描述

    输入:[3,7,4,5]
    输出:144
    解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,
    或 3*4*5 + 3*4*7 = 144。最低分数为 144。
    

    示例 3:

    输入:[1,3,1,4,1,5]
    输出:13
    解释:最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
    

    提示:

    • 3 <= A.length <= 50
    • 1 <= A[i] <= 100

    思路

    分析一个较大凸多边形进行三角剖分得到的最低分时,需要用到包含在该较大多边形中的小凸多边形的三角剖分的最低分。多边形三角剖分的示意图如下图所示。这是对区间[i, j]进行三角剖分,选取了区间中的一个点ki-k这条线分出了上面一个小多边形,k-j这条线分出了下面一个小多边形,虚线表示区间[i, k][k, j]之间的顶点个数不确定,可能是一个也可能是多个。
    在这里插入图片描述

    dp数组含义:dp[i][j]为区间[i, j]的多边形三角剖分的最低得分。那么最终的结果肯定是整个区间的三角剖分的最低得分,即dp[0][n-1],其中n为数组长度。

    转移方程:
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i]* A[k] * A[j]), k∈(i,j)(后面一部分就是根据上面的三角剖分示意图得出来的)

    初始化:因为需要求得分的最小值,所以dp数组中每个元素要初始化为整型的最大值。其次两个点是无法构成三角形的,所以dp[i][i+1]=0

    参考题解:
    52Hz的题解
    Peter的题解

    代码如下:

    class Solution {
        public int minScoreTriangulation(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int n = A.length;
            int[][] dp = new int[n][n];
            // 初始化每个元素为整型的最大值
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
            // 两个点是无法构成三角形的
            for (int i = 0; i < n-1; i++) {
                dp[i][i+1] = 0;
            }
            
            // 枚举区间长度:len表示i和j的间隔,要构成三角形,至少间隔两个点
            for (int len = 2; len < n; len++) {
                for (int i = 0; i < n; i++) {//枚举区间的起点
                    int j = i+len;//根据起点和长度得到终点
                    if (j >= n) continue;
                    for (int k = i+1; k < j; k++) {//枚举该区间的分割点
                        dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]+A[i]*A[k]*A[j]);
                    }
                }
            }
            return dp[0][n-1];
        }
    }
    
    展开全文
  • 单调多边形的三角剖分是计算几何的一个重要分支,其中严格单调多边形的三角剖分已有了 线性时间算法,但该算法对于一般单调...本文对严格单调多边形三角剖分算 法进行了详细分析,给出了一般单调多边形的三角剖分算法.
  • 摘要:多边形三角剖分是计算几何的一个几何基元. 它可以简化问题规模,在计算机图形学、模式识别和地 理数据库方面有重要应用. 低时间复杂度是设计多边形三角剖分算法的基本要求. 针对现有单调多边形算法 的不足,提出...
  • 本科算法实验-凸多边形三角剖分【数据+代码+说明+流程图+测试用例】
  • 多边形三角剖分可视化工具 基于Java的削耳算法的多边形三角剖分可视化器。 削耳算法: 在这种方法中,我们通过在多边形中找到耳,该耳是与前一个坐标和下一个坐标相结合的坐标,形成一个有效的三角形,可以在不干扰...
  • 多边形三角剖分的最低得分1 问题描述2 问题分析 1 问题描述 2 问题分析 1.利用动态规划解题如何确保
  • 1039. 多边形三角剖分的最低得分

    千次阅读 2019-07-10 08:27:49
    给定N,想象一个凸N边多边形,其顶点按顺时针顺序依次标记为A[0], A[i], ..., A[N-1]。...返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角...
  • 返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 示例 2: 输入:[3,7,4,5] 输出:144 解释:有两种三角剖分,可能得分分别为:375 +...
  • 返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 思路: 类似戳气球题目 但与其相反,选择最小值 解题思路类似,将范围从小到大计算,...
  • 多边形三角剖分

    2020-08-13 14:00:00
    https://blog.csdn.net/huangzengman/article/details/77114082 https://www.cnblogs.com/lan-yt/p/9200621.html
  • 给定N,想象一个凸N边多边形,其顶点按顺时针顺序依次标记为A[0], A[i], ..., A[N-1]。...返回多边形进行三角剖分后可以得到的最低分。 lru_cache 能够自动缓存函数执行的结果,非常适合动态规划和递归 from...
  • 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], ...返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 示例 ...
  • 1039. 多边形三角剖分的最低得分 分割一个凸多边形的方案数: 如何做到不重不漏? 如下图: 在剖分的最后,111和nnn一定会和第三个点构成一个三角形(如果不是,就不满足题目要求了), 在[2,n−1][2,n-1][2,n−1]中...
  • 返回多边形进行三角剖分后可以得到的最低分。 测试用例1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 测试用例2: 测试用例3: 输入:[1,3,1,4,1,5] 输出:13 解释:最低分
  • 多边形三角剖分算法的理论。
  • 如何将一个多边形三角化是三维模型中一个比较常见的问题。最初的想法很简单,认为就是以一个点起点连接和它不相邻的点所有三角形就区分完了。这样写完后放到ue4里面测试,开始比较顺利,当但遇到凹多边形时,就发现...
  • 返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 示例 2: 输入:[3,7,4,5] 输出:144 解释:有两种三角剖分,可能得分分别为:375 +
  • 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。...返回多边形进行三角剖分后可以得到的最低分。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/p...
  • unity实现任意多边形三角剖分

    千次阅读 2017-08-12 13:39:37
    项目有一个对任意形状截面生成3维物体的需求,需要用到三角化的算法。如果截面是凸多边形,那么非常简单,以任意一点为... /// 局限性三角剖分 /// /// <returns></returns> public static int[] LimitedTriangleI
  • 游戏中需要实现一个小功能,显示一个玩家的能力图,这个图是一个有6个顶点任意摆放组合的多边形。而绘制多边形主要用到的知识就是Mesh构建,mesh的构建主要需要顶点列表,三角形列表,法线列表、uv列表等等等等,在...
  • 文章目录1. 题目2....返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 示例 2: 输入:[3,7,4,5] 输出:144 解释:
  • 返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 图解状态转移 代码 class Solution { public int minScoreTrian
  • 题目描述 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。 假设您将多边形剖分为 N-2 个三角形。... 返回多边形进行三角剖分后可以得到的最低分。 ...
  • 题目描述: 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …...返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分...
  • 返回多边形进行三角剖分后可以得到的最低分。 示例 1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 示例 2: 输入:[3,7,4,5] 输出:144 解释:有两种三角剖分,可能得分分别为:...
  • 『题目』:  给定 NNN,想象一个凸 NNN 边多边形,其顶点按顺时针顺序依次标记为 ...对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N−2N-2N−2 个三角形的值之和。 返回多边...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 607
精华内容 242
关键字:

多边形三角剖分