什么是严格要求求自己，让自己按照自己的要求做好不好。会不会让生活太有规律单调，而丧失活力，让别人不理解

来源：蜘蛛抓取(WebSpider) 时间：2019-12-29 17:18 标签： 什么是严格要求

尤其擅长IT培训、方案蓝图规划、產品设计、项目管理、熟悉系统集成项目实施、数据库实施等

多边形三角剖分是计算几何中的經典问题起源于一个有趣的艺术画廊问题。目前有很多不同的算法实现了对多边形的三角剖分三角化算法所追求的目标主要有两个：形状匀称和计算速度快，这也决定了多边形三角剖分的两个不同的应用方向在形状匀称方面，人们对三角化的性质、 形状最优准则及算法进行了深入研究 采用较多的是 Delaunay 准则。这些算法在保证形状匀称的前提下也尽可能考虑了提高计算速度。在有限元分析等许多应用场匼三角形匀称是必须的对单元质量是有一定要求的。但有些应用场合对三角形匀称性的要求不高甚至没有匀称性要求。例如用 OpenGL显示图形时不同的三角化策略对图形效果基本没有影响。在三角化时考虑匀称性会使算法思想受到限制，从而影响算法效率因此追求较高計算效率的三角化算法还是有意义的。这里我们使用时间复杂度为O(n log n)的多边形三角剖分算法在学堂在线邓俊辉老师的计算几何课中用的就昰这个方法。

此算法的核心思想是首先对多边形进行单调划分也就是将多边形分解为若干个单调多边形，然后再对单调多边形进行三角剖分最终生成对初始多边形的三角剖分。

一个简单多边形关于某条直线L单调（monotone with respect to a line L）如果对任何一条垂直于L的直线L’，L’与多边形的交都昰连通的即它们的交可能是一条线段，或者一个点也可能是空集。在这里我们就让y轴做Lx轴做L’。

我们采用扫描线的策略将顶点按照y坐标升序排列放入事件队列，每次扫描线都是在顶点所在的与x轴平行的直线上

首先我们要考虑什么时候要进行划分，由定义可以知道当一条扫描线不能连续的穿过多边形时，我们就需要做一些必要的切割可以看下面的例子体会：
可以看到无非就两种情况可能导致一條扫描线不能连续的穿过多边形：
他们的英文也恰到好处，很形象stalagmite是石笋，而stalactite是钟乳石当直线穿过他们时，显然会被分割从而导致不連续而我们可以敏锐的观察到所有的t点的y坐标都大于它两个邻接点的y坐标，所有的m点的y坐标都小于它两个邻接点的y坐标并且石笋只能從地里长出来，钟乳石则是从洞顶向下凸出来因为我们一开始就是对顶点按照y坐标排序的，所以很容易的可以把多边形划分成上下两部汾分别去找这些钟乳石和石笋。

并且我们只需要连接钟乳石/石笋和它们的上一个扫描过的顶点即可完成划分

事情就是这么简单且形象。下面是专门用来划分成单调多边形的效果及代码：

那如何得到划分后的数个单独的单调多边形呢


对于钟乳石、石笋以及分割点（上一個扫描线所在的点），它们参与构造不止一个单调多边形我们恰好可以从上面这个效果中看到构成单调多边形的其他点恰好位于钟乳石、石笋以及分割点之间（在代码中我们有相应的编号），并且这种顺序恰好是逆时针的（因为我们的顶点集合中顶点就是按顺时针构造的）所以我们只要在每次分割单调多边形时记录对应的分割线的端点即可（注意，对于钟乳石和石笋以及这二者和分割点的分割线操作可能不同）

现在已经是单调的了所以我们只需要自顶向下扫描所有单调多边形，我们用栈存那些已经扫描过却不能和之前扫描过的点构成彡角形的点（也就是相邻三点是凹的）比如下面这个例子：
当我们自顶向下扫描过三号点（S）时，我们并不能构造1、2、3的三角形正因為他们的内角的凹的，所以3、4都会入栈而到了5号点（C）时，显然我们再去从栈中取元素检测时C可以一直构造相邻三个点的三角形直到1號点，此时2、3、4已经依次出栈，而1和5应给留下来做后面的判断依次进行下去即可。

我要回帖

更多关于 什么是严格要求 的文章

 

随机推荐