这是本来ACM竞赛使用的关于最小球覆盖与三维凸包计算几何模版代码，挺好用的。

计算几何_苏步青计算几何_苏步青计算几何_苏步青计算几何_苏步青

CGAL模型凸包计算，利用CGAL计算几何算法库，解决了模型凸包运算问题。资源包含完整代码和详细说明文档。

计算几何或者计算机图形学里bezier2次曲线插值作图matlab

第一章 计算几何：导言 第二章 线段求交：专题图叠合 第三章 多边形三角剖分：画廊看守 第四章 线性规划：铸模制造 第五章 正交区域查找：数据库查询 第六章 点定位：找到自己的位置 第七章 Voronoc图：邮局问题 第八章 排列与对偶：光线跟踪超采样 第九章 Delaunay三角剖分：高度插值 第十章 更多几何数据结构：截窗 第十一章 凸包：混合物 第十二章 空间二分：画家算法 第十三章 机器人运动规划：随意所之 第十四章 四叉树：非均匀网格生成 第十五章 可见性图：求最短路径 第十六章 单纯区域查找：再论截窗

中文名: 计算几何--算法与应用 原名: Computational Geometry:Algorithms and Applications 作者: (荷)Mark de Berg, Marc van Kreveld等资源格式: PDF 版本: 第3版　清晰版 出版社: Springer Berlin Heidelberg书号: 3642096816发行时间: 2009年 地区: 美国 语言: 英文 简介: 内容简介： 计算几何是计算机理论科学的一个重要分支.自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用. 本书的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是本书的一个鲜明特点.第5章至第10章介绍了多种几何结构，包括几何查找、kd树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等.第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前十章内容的进一步深化. 本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，为读者更深入的理解提供了可能. 目录: Table of Contents 1 Computational Geometry --- Introduction 1.1 An Example: Convex Hulls 1.2 Degeneracies and Robustness 1.3 Application Domains 1.4 Notes and Comments 1.5 Exercises 2 Line Segment Intersection --- Thematic Map Overlay 2.1 Line Segment Intersection 2.2 The Doubly-Connected Edge List 2.3 Computing the Overlay of Two Subdivisions 2.4 Boolean Operations 2.5 Notes and Comments 2.6 Exercises 3 Polygon Triangulation --- Guarding an Art Gallery 3.1 Guarding and Triangulations 3.2 Partitioning a Polygon into Monotone Pieces 3.3 Triangulating a Monotone Polygon 3.4 Notes and Comments 3.5 Exercises 4 Linear Programming --- Manufacturing with Molds 4.1 The Geometry of Casting 4.2 Half-Plane Intersection 4.3 Incremental Linear Programming 4.4 Randomized Linear Programming 4.5 Unbounded Linear Programs 4.6* Linear Programming in Higher Dimensions 4.7* Smallest Enclosing Discs 4.8 Notes and Comments 4.9 Exercises 5 Orthogonal Range Searching --- Querying a Database 5.1 1-Dimensional Range Searching 5.2 Kd-Trees 5.3 Range Trees 5.4 Higher-Dimensional Range Trees 5.5 General Sets of Points 5.6* Fractional Cascading 5.7 Notes and Comments 5.8 Exercises 6 Point Location --- Knowing Where You Are 6.1 Point Location and Trapezoidal Maps 6.2 A Randomized Incremental Algorithm 6.3 Dealing with Degenerate Cases 6.4* A Tail Estima

CGAL是Computational Geometry Algorithms Library(计算几何算法库)的缩写，用C++语言提供高效、可靠的算法库。被广泛应用于几何计算相关的领域，如信息可视化系统，计算机辅助设计，分子生物学，医学图像处理，计算机图形学，机器人设计等。

不等式绘图的一般实现计算几何-regionsurf.m 在可视化上matlab已经很强大了（但是令人吐槽的是它的默认色彩方案以及不光滑的线条），但是有些功能还是没有现成的官方函数能够简单实现，比如经常会遇到的区域绘图/不等式绘图。这种功能在 Mathematica 里面有build-in函数可以实现（RegionPlot和RegionPlot3D）。 严格来说，不等式绘图其实是属于计算几何里面的东西。更加一般的情况是，在指定空间区域绘制一个函数的图像——而不是仅仅绘制这个不等式区域。这一点，Mathematcia里面的RegionFunction选项可以很方便做到。 1. MATLAB实现任意不等式区域（空间）可视化 那么MATLAB想要实现这些功能，就必须自己动手了。下面是我写的两个函数regionfill和regionsurf，分别实现的是平面和三维 任意不等式绘图。使用的算法各自是：步进矩形 二分搜索、步进四面体 逻辑比较。因此，任意实数域（以及部分复数域）内的解集都能可视化。具体详细功能请阅读里面的说明和例子。 regionfill.m 二维不等式绘图 regionsurf.m 三维不等式绘图 2. 指定不等式区域（空间）内绘制曲面 1) 平面不等式的情况 只需要使用regionfill返回不等式解集面片fv，就能用于单值函数曲面在指定区域内的绘图（相当于RegionFunction的一部分功能）。 2) 三维情况 这个功能暂时没加入，主要是由于平均交点个数是二维情况的三次方，直接用m函数实现就显得效率不够高了（除非加入八叉树算法来减少检索时间），使用MT算法 C-mex可能比较快，但是没精力去做这个了，如果谁有兴趣可以试一试。 3. 曲面布尔运算 平面布尔运算，MATLAB有polybool函数可以实现，但是对于三维情况，就没有函数提供了。这是因为，三维布尔运算的难度不是从二维到三维那么简单的提升，而是有着非常大的难度。因此，现在已经有些工具包能实现这个功能（比如iso2mesh工具箱，以及最新的GBT工具箱），大多数都是采用通过m调用exe程序来计算，或者使用c-mex/dll。 要解决曲面布尔运算这个问题，关键在于三个地方： a. 碰撞检测； b. 曲面求交线； c. 相交部分的拓扑重构。 要知道，上述每一点都是计算几何领域的热点问题，如今也没有很高效且简单的算法。目前已有的算法分为两种：牺牲准确度以提高速度，牺牲效率以提高准确度。作为非专业建模用途，仅仅是可视化的matlab，我们只需要选择前一种算法即可。 目前我只是用c-mex写了曲面求交线的一个函数surfs，由于使用的算法只是简单的相交测试 三角面片求交，并未用到比较高效的链表查询机制，因此很多相邻边的交点其实是重复计算了的，因而对于大量的三角面（比如5000以上的三角面片的两个复杂曲面）求交线，时间效率就会急剧上升（大概会在6s以上），对于三角面片不多1000左右，0-2s内可以给出结果。 surfs.rar 曲面求交线 上面给出的东西也算是抛砖引玉吧，希望有高手能将这些问题完美解决。 补充内容 : 更新：11楼发布了regionsurf的更新版，修正了一些bug，并改进了一些细节。

不等式绘图的一般实现计算几何-regionfill.m 在可视化上matlab已经很强大了（但是令人吐槽的是它的默认色彩方案以及不光滑的线条），但是有些功能还是没有现成的官方函数能够简单实现，比如经常会遇到的区域绘图/不等式绘图。这种功能在 Mathematica 里面有build-in函数可以实现（RegionPlot和RegionPlot3D）。 严格来说，不等式绘图其实是属于计算几何里面的东西。更加一般的情况是，在指定空间区域绘制一个函数的图像——而不是仅仅绘制这个不等式区域。这一点，Mathematcia里面的RegionFunction选项可以很方便做到。 1. MATLAB实现任意不等式区域（空间）可视化 那么MATLAB想要实现这些功能，就必须自己动手了。下面是我写的两个函数regionfill和regionsurf，分别实现的是平面和三维 任意不等式绘图。使用的算法各自是：步进矩形 二分搜索、步进四面体 逻辑比较。因此，任意实数域（以及部分复数域）内的解集都能可视化。具体详细功能请阅读里面的说明和例子。 regionfill.m 二维不等式绘图 regionsurf.m 三维不等式绘图 2. 指定不等式区域（空间）内绘制曲面 1) 平面不等式的情况 只需要使用regionfill返回不等式解集面片fv，就能用于单值函数曲面在指定区域内的绘图（相当于RegionFunction的一部分功能）。 2) 三维情况 这个功能暂时没加入，主要是由于平均交点个数是二维情况的三次方，直接用m函数实现就显得效率不够高了（除非加入八叉树算法来减少检索时间），使用MT算法 C-mex可能比较快，但是没精力去做这个了，如果谁有兴趣可以试一试。 3. 曲面布尔运算 平面布尔运算，MATLAB有polybool函数可以实现，但是对于三维情况，就没有函数提供了。这是因为，三维布尔运算的难度不是从二维到三维那么简单的提升，而是有着非常大的难度。因此，现在已经有些工具包能实现这个功能（比如iso2mesh工具箱，以及最新的GBT工具箱），大多数都是采用通过m调用exe程序来计算，或者使用c-mex/dll。 要解决曲面布尔运算这个问题，关键在于三个地方： a. 碰撞检测； b. 曲面求交线； c. 相交部分的拓扑重构。 要知道，上述每一点都是计算几何领域的热点问题，如今也没有很高效且简单的算法。目前已有的算法分为两种：牺牲准确度以提高速度，牺牲效率以提高准确度。作为非专业建模用途，仅仅是可视化的matlab，我们只需要选择前一种算法即可。 目前我只是用c-mex写了曲面求交线的一个函数surfs，由于使用的算法只是简单的相交测试 三角面片求交，并未用到比较高效的链表查询机制，因此很多相邻边的交点其实是重复计算了的，因而对于大量的三角面（比如5000以上的三角面片的两个复杂曲面）求交线，时间效率就会急剧上升（大概会在6s以上），对于三角面片不多1000左右，0-2s内可以给出结果。 surfs.rar 曲面求交线 上面给出的东西也算是抛砖引玉吧，希望有高手能将这些问题完美解决。 补充内容 : 更新：11楼发布了regionsurf的更新版，修正了一些bug，并改进了一些细节。

Mard de Berg Otfried Cheong Marc van Kreveld Mard Overmars