精华内容
下载资源
问答
  • 单调多边形的三角剖分是计算几何的一个重要分支,其中严格单调多边形的三角剖分已有了 线性时间算法,但该算法对于一般单调多边形还不能给出正确的剖分....法进行了详细分析,给出了一般单调多边形三角剖分算法.
  • 多边形三角剖分算法的理论。

    看来看去还是这个论文解释的非常清楚。

    http://www.cnblogs.com/dogstar/archive/2011/04/07/2008726.html

    展开全文
  • 本项目的部分代码参考自下面博客 ... 最近项目中涉及到使用Unity3D来进行地图上国家的渲染,比如把中国圈起来染成红色的这样的需求。...最终问题卡在一个点上,对于中国边界这样的凹多边形,如何将其剖分...

    本项目的部分代码参考自下面博客

    https://www.cnblogs.com/lan-yt/p/9200621.html

     

    最近项目中涉及到使用Unity3D来进行地图上国家的渲染,比如把中国圈起来染成红色的这样的需求。

    Unity3D把区域渲染是用的MeshRender,关于MeshRender的用法我就不详细讲解了。

    最终问题卡在一个点上,对于中国边界这样的凹多边形,如何将其剖分为一系列三角形。

    本来以为这是个最常见的问题,应该会有很多求解方法的,结果我找了半天,就找到了上面给出网址的那个博客,而没找到成形的源码。

    还好那个博客上有代码,就按照那个博客上的代码,运行了一下,反正在我电脑上有点小的BUG。

    不过这个BUG很容易修改,虽然我忘记我是怎么修改的了,后来运行成功了。

    于是,我就找到中国边界数据,把它读进去,然后运行。

    等了一会儿,系统爆栈了,因为那个博客中算法用到了递归,而中国边界有八千多个点,一个点递归一次,需要递归八千次。

    不得已,只好自己写代码了。

    后来看到了一个翻译来自日本的凹多边形剖分算法,耳切法。

    博客地址:

    https://blog.csdn.net/u010019717/article/details/52753855

    根据第二个博客中的思想,来设计如下算法:

    步骤一:将多边形的所有点读入数组V中。

    步骤二:判断该多边形是否为凸多边形,如果为凸多边形,按照凸多边形剖分算法进行处理,算法结束,否则转到步骤三。

    步骤三:将所有顶点的序号读入一个数组A中保存起来,然后遍历多边形的顶点,判断每个顶点是否为“耳朵节点”,然后将所有“耳朵节点”保存到数组B。

    步骤四:如果耳朵节点数组B为空或者顶点数组V的顶点数组小于三,则算法结束。否则,取出耳朵节点中的第一个顶点P来。

    步骤五:找到该节点的前序节点M和后序节点N,这三个点MPN组成一个三角形,保存到结果数组R中,然后,把当前顶点P从耳朵节点中去掉,从数组V中去掉,从序号数组B中去掉。

    步骤六:前序节点M和后序节点N,成为了“耳朵节点”的候选。则分别判断M与N是不是耳朵节点,如果是耳朵节点,且没有在当前的耳朵节点数组B中,则将判断为耳朵节点的点放入耳朵节点数组B中。

    步骤七:跳转到步骤四。

     

    然后通过以上算法,就得到了最终的结果,这个算法没有使用递归,算法的效率还行。

     

    这个是我算法运行的结果。

    算法源码:

    https://download.csdn.net/download/kongxinyue/11230469

     

     

     

    展开全文
  • 采用C#语言实现计算几何中简单多边形三角剖分算法。内容包含源程序,可执行程序,程序运行说明文档和参考图。
  • 提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法。该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外...
  • 空间平面内任意多边形三角剖分算法 保存stl模型后分析
  • 摘要:多边形三角剖分是计算几何的一个几何基元.... 低时间复杂度是设计多边形三角剖分算法的基本要求. 针对现有单调多边形算法 的不足,提出一个复杂度为O ( N) 的算法,并在Visual C+ + 环境下实现这个算法.
  • 计算几何多边形三角剖分

    热门讨论 2011-04-07 21:36:49
    多边形三角剖分是计算几何( Computational Geometry)中的经典问题,起源于一个有趣的艺术画廊问题。目前有很多不同的算法实现了对多边形的三角剖分,三角化算法所追求的目标主要有两个:形状匀称和计算速度快。 此...
  • 基于最小距离的多边形三角剖分算法是,多边形的每个顶点对应一个距离,对这些距离进行比较,依次连接最小距离,连接后判断相邻两点的凹凸性且改变连接点的相邻点的距离,除凹点外,并不需要对所有的点进行判断和计算。...
  • 简单多边形的动态Delaunay三角剖分算法
  • 提出了一种简单多边形的动态Delaunay三角剖分算法,其时间复杂度为O( n) .从理论上证明了算法的正确性,并利用Python语言开发了一款动态Delaunay三角网生成软件,最后通过大量数据测试了该软件的健壮性并得到实例证实.
  • 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];
        }
    };
    
    展开全文
  • 最简单、 最可靠的一种多边形 ,也即多边形的最小 单位。三维应用开发有 Open GL 及 Direct 3D 渲 染引擎两种常用开发工具 ,Open GL 有直接绘制 多边形的函数 ,但仅限于凸多边形;而在 Direc 3D中
        在三维图形学及其可视化应用中 ,三角形是
    最简单、 最可靠的一种多边形 ,也即多边形的最小
    单位。三维应用开发有 Open GL 及 Direct 3D 渲
    染引擎两种常用开发工具 ,Open GL 有直接绘制
    多边形的函数 ,但仅限于凸多边形;而在 Direc
    3D中 ,只有直接绘制三角形(网)的函数。因此
    多边形三角剖分是多边形绘制的基础。
    Cheng Siuwing等[1 ,2 ,3 ]
    从建立最优三角形条
    件的角度提出了简单多边形三角剖分的算法;杨
    杰等[4 ,5 ]
    提出了根据顶点凹凸性进行简单多边形
    三角剖分的算法。然而 ,这些算法并没有考虑存
    在高程起伏特征或带岛屿的复杂多边形面状地物
    (如道路、 河流)的三角剖分。   在三维图形学及其可视化应用中 ,三角形是
    最简单、 最可靠的一种多边形 ,也即多边形的最小
    单位。三维应用开发有 Open GL 及 Direct 3D 渲
    染引擎两种常用开发工具 ,Open GL 有直接绘制
    多边形的函数 ,但仅限于凸多边形;而在 Direc
    3D中 ,只有直接绘制三角形(网)的函数。因此
    多边形三角剖分是多边形绘制的基础。
    Cheng Siuwing等[1 ,2 ,3 ]
    从建立最优三角形条
    件的角度提出了简单多边形三角剖分的算法;杨
    杰等[4 ,5 ]
    提出了根据顶点凹凸性进行简单多边形
    三角剖分的算法。然而 ,这些算法并没有考虑存
    在高程起伏特征或带岛屿的复杂多边形面状地物
    (如道路、 河流)的三角剖分。距离河流流域三角剖分时 ,如加上高程信息这一
    地形条件 ,可充分顾及地形特征 ,使剖分的长距离
    河流流域在三维 GIS中表现更加自然、 真实。
    展开全文
  • 本科算法实验-凸多边形三角剖分【数据+代码+说明+流程图+测试用例】
  • 三角剖分算法

    2021-07-19 14:16:06
    二、散乱点集剖分算法 1、Lawson算法 2、Bowyer算法 3、算法的优化 4、程序实现 三、三角形剖分算法 1、实现思想 2、代码实现 一、引言 1、背景 本算法来源于美术馆问题,美术馆问题如下:假如有一个凹...
  • 题目描述 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。 假设您将多边形剖分为 N-2 个三角形。... 返回多边形进行三角剖分后可以得到的最低分。 ...
  • 基于Java的削耳算法多边形三角剖分可视化器。 削耳算法: 在这种方法中,我们通过在多边形中找到耳,该耳是与前一个坐标和下一个坐标相结合的坐标,形成一个有效的三角形,可以在不干扰其他点的情况下将其删除,...
  • 多边形三角剖分是计算几何的一个几何基元,它可以简化问题规模,在计算机图形学、模式识别等方面有重要的应用。本文针对已有的Delaunay三角剖分算法的不足,提出新算法,并采用Visual C语言MFC类进行链表的管理,使得编程...
  • unity实现任意多边形三角剖分

    千次阅读 2017-08-12 13:39:37
    项目有一个对任意形状截面生成3维物体的需求,需要用到三角化的算法。如果截面是凸多边形,那么非常简单,以任意一点为... /// 局限性三角剖分 /// /// <returns></returns> public static int[] LimitedTriangleI
  • 算法:凸多边形最优三角剖分

    千次阅读 2019-10-31 18:20:49
    1、问题相关定义: (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。... 凸多边形三角剖分如下图所示: 2、最优子结构性质: 若凸(n+1)边形P={V0,V1……Vn}的最优三角剖分T包含三角形...
  • 计算几何 此仓库包含一些著名的计算几何算法的实现,例如凸包,线段相交,多边形三角剖分等。
  • 多边形三角剖分

    2020-08-13 14:00:00
    https://blog.csdn.net/huangzengman/article/details/77114082 https://www.cnblogs.com/lan-yt/p/9200621.html
  • 如何将一个多边形三角化是三维模型中一个比较常见的问题。最初的想法很简单,认为就是以一个点起点连接和它不相邻的点所有三角形就区分完了。这样写完后放到ue4里面测试,开始比较顺利,当但遇到凹多边形时,就发现...
  • 本程序提供一种新的剖分形式,它是实现简单多边形准实时的在线的线性时间剖分的必要形式,这种剖分由凸环和/或凹环组成,最终可以线性时间转化为三角剖分。 适合于计算机图形学、计算几何、机器人运动及图形游戏...
  • 返回多边形进行三角剖分后可以得到的最低分。 测试用例1: 输入:[1,2,3] 输出:6 解释:多边形已经三角化,唯一三角形的分数为 6。 测试用例2: 测试用例3: 输入:[1,3,1,4,1,5] 输出:13 解释:最低分
  • 一、动态规划  和分治法类似,把原问题划分成若干个子问题,不同的是,分治法(子问题间互相独立),动态规划(子问题不独立)  动态规划: (1)找出最优解的性质,刻画其...三角剖分多边形分割成互不想交的...
  • 原题链接:...动态规划: dp[i][j]表示区间[i,j]上多边形最小值 状态转移: dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+A[i]*A[k]*A[j]); 代码: int minScoreTriangulat...
  • Delaunay三角剖分算法

    2012-09-09 23:04:00
    Delaunay三角剖分算法 目录 1. 三角剖分与Delaunay剖分的定义1.1.三角剖分定义1.2. Delaunay三角剖分的定义1.3.Delaunay三角剖分的准则1.4.Delaunay三角剖分的特性1.5.局部最优化处理2.Delaunay剖分的算法展开...
  • 提出了一种基于凹多边形凸分解的相容三角剖分方法。先将凹边形分解成凸多边形,再对子多边形进行三角剖分,即可实现相容三角剖分。在最坏的情况下添加O(jk)个辅助点,时间复杂度为O(jn n log n jk log n)

空空如也

空空如也

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

多边形三角剖分算法