网格剖分-耳切法效果展示

1.前言

将简单多边形转换成一组由同样顶点组成的三角形集合是计算机图形学中的一个经典问题。问题中，简单多边形是指由一组有序顶点组成的，点V0~点Vn-1。相邻的顶点之间通过边(Vi,Vi-1)连接，并且边（Vn-1,V0）连接起始点。每个顶点被两条边所共享，而边的所有交点都是顶点。

将一个简单多边分解成三角形集合的方法称之为多边形的三角形化（triangulation of thePolygon）。几何学的知识告诉我们，由n个顶点组成的简单多边形总是可以分解成n-2个三角形。

2.耳切法

简单多边形的耳朵，是指由连续顶点V0,V1和V2组成的内部不包含其他任意顶点的三角形。在计算机几何术语中，v0与V2之间的连线 称之为多边形的对角线，点V1称之为耳尖。虽然你可以将耳尖放到三角形的任意一个顶点上，但是我们认为三角形包含一个耳尖。一个由四个顶点（或者更多）组成的多变形至少有两个不重叠的耳尖。这个特性提供了一个通过递归来解决三角化分割的方法。针对由N个定点组成的多边形，找到其耳尖，移除唯一耳尖上的顶点，此时剩余顶点组成了一个n-1个顶点的简单多边形。我们重复这个操作知道剩余三个顶点。这样的话会产生一个复杂度为O(N3)的算法。随着一些细节改进，耳朵消除可以在O （ N2）的时间来完成。

3.关键点

1. 需要实现简单多边形轮廓的耳切法网格剖分；
2. 对于带洞口的情况可以先寻找内外轮廓可见点，并双向联通可见点得到贯通内外轮廓的简单多边形，再进行上述网格化；

   

3. 由于部分内轮廓不存在与原始外轮廓的可见点对，需要通过轮廓排序等方式先处理具有可见点对的内轮廓，将问题简化；

   

4. 当多个内轮廓外部可见点重合时可能会造成问题，构造的简单多边形outer在耳切法处理时可能会找不到有效耳朵点。再寻找内轮廓的外部可见点时需要避免与此前轮廓的外部可见点重合的情况；
5. 对于洞口中可能继续层层嵌套轮廓的情况，可以简化为带洞口轮廓情况处理，深度优先或广度优先遍历轮廓树，以每两级轮廓（外轮廓和内轮廓）为处理单元进行耳切法网格剖分，将结果数据进行归并得到整体的网格数据。

4.效果

 

5.写在后面

1、网格化处理是基础几何算法内容，其准确性和效率是评判几何内核质量的重要指标；

几何算法学习实践和应用（二维）_工程师要掌握的几何图形算法-CSDN博客文章浏览阅读1.4k次。几何算法底层的原理很多是相通的，用到的也都是基础的工具函数，学习和积累非常重要。很多原理可由二维推广到三维，一些复杂三维算法可以分解为二维实现。_工程师要掌握的几何图形算法https://blog.csdn.net/baidu_38621657/article/details/129509086

几何算法学习实践（三维）_三维图形算法-CSDN博客文章浏览阅读2k次，点赞2次，收藏4次。将个人几何算法学习和实践进行记录，方便自己和有需要的人。学习和实践相结合，建立小项目进行练手，该项目包含几何工具库与图形显示两部分。_三维图形算法https://blog.csdn.net/baidu_38621657/article/details/129473678 

2、上述结果展示使用了WPF技术，在数据预处理过程中调用了轮廓提取、组织处理轮廓树等算法接口；详细可参考博主此前文章。

利用WPF绘制轮廓并保存为图片_c#wpf在图片上划线,保存划线后的图片-CSDN博客文章浏览阅读423次。WPF作为显示工具也挺好用，用C#开发应用软件会比较省力，当然也有其缺点，如在对效率要求较高的情况下有性能问题，本文记录用WPF绘制轮廓并保存为图片相关内容。显示效果也还不错，满足调试使用了，_c#wpf在图片上划线,保存划线后的图片https://blog.csdn.net/baidu_38621657/article/details/142340681从线段中搜寻提取闭合轮廓（三）_ai提取图片轮廓线-CSDN博客文章浏览阅读563次，点赞6次，收藏18次。做底层和数据的调试问题也是个麻烦事，如果没有方便的可视化工具辅助，那将令人感到痛苦，借助可视化的工具可以让我们高效、省心，进而心情舒畅，重要的是可以提高调试效率。当然可视化工具也分不同层次的，大致分为手动操作为主的、自动为主的两种，手动操作为主的也要区分工具准确性、易用性，如果碰到难用的也是经常令人心情烦躁，甚至破口大骂；而易用性较好的会比较省心，但由于其手动操作为主的特点，需要耗时耗力，也难以心情很舒畅。（中间吐槽省略......）_ai提取图片轮廓线https://blog.csdn.net/baidu_38621657/article/details/142144804

图形几何、数据处理、并行计算相关研究和研发，公众号：geometrylib，欢迎交流。