Awesome computational geometry

Awesome Computational Geometry ¶

> 精选的计算几何可视化、库和资源列表.

Computational geometry 是计算机科学中的一个主题，侧重于解决几何问题. 计算几何的应用包括计算机辅助设计、机器人技术、GIS 系统和计算机视觉.

Algorithm Visualizations¶

• Convex Hull - 形状的凸包是包含它的最小凸集.
• Convex Hull Algorithms - 一个可视化许多凸包算法的网站，包括礼品包装、Graham 的扫描、quickhull、分而治之、单调链和 Chan 的算法.
• Chan's Algorithm - 一种优化的输出敏感算法，用于计算 2 或 3 维中一组点的凸包.
• Kirkpatrick's Point location - 使用三角测量的 O(n) 空间和 O(log n) 查询时间的点定位的数据结构和方法.
• Voronoi Diagrams - 将平面划分为靠近给定点集的区域.
• Fortune's Algorithm - A sweep line algorithm for generating the Voronoi diagram in O(n log n) time and O(n) space.
• Point/Line Duality - 一种常用于计算几何算法的数学对偶性.
• k-d tree - 一种以有效方式划分 k 维空间的方法，用于像最近邻居这样的搜索.
• Configuration Space - 像机器人这样的物体的可能配置空间.

Books¶

• Computational Geometry: Algorithms and Applications - Mark de Berg、Otfried Cheong、Marc van Kreveld 和 Mark Overmars 合着的教科书（2008 年）.
• Computational Geometry in C - Joseph O'Rourke（1998 年）对计算机图形学、机器人学和工程设计等领域中出现的几何算法的设计和实现的流行介绍.
• Computational Geometry: An Introduction - Franco P. Preparata 和 Michael I. Shamos (1993) 的介绍性教科书.
• Algorithmic Geometry - Jean-Daniel Boissonnat、Mariette Yvinec 和 Herve Bronniman 合着的教科书（1998 年）.
• Discrete and Computational Geometry - 对离散几何的混合进行了全面但易于理解的介绍，这是纯数学中相对较新的发展，计算几何是 Satyan L. Devadoss 和 Joseph O'Rourke（2011 年）应用驱动的计算机科学中的一个新兴领域.
• Interactive Computational Geometry - A taxonomic approach - Jim Arlow（2014 年）使用 Mathematica 交互式介绍了一些计算几何的基本算法.

Notes¶

• Lecture Notes - David Mount 的马里兰大学 CMSC 754 计算几何的讲义（2002 年）.
• Handbook of Discrete and Computational Geometry - Jacob E. Goodman、Joseph O'Rourke 和 Csaba D. Tóth 的手册（2017 年）.
• Handbook of Computational Geometry - JR Sack 和 J. Urrutia（1998 年）对计算几何中的关键概念和结果的概述.
• Computing in Euclidean Geometry - Ding-Zhu Du 和 Frank Hwang（1995 年）关于计算欧几里德几何领域最新发展的调查和探索性文章集.

Libraries¶

• CGAL - 一个软件项目，以 C++ 库的形式提供对高效可靠的几何算法的轻松访问. 该网站还对其中许多算法进行了解释.
• Wykobi - 一个极其高效、健壮且易于使用的面向 C++ 2D/3D 的计算几何库.
• geometry3Sharp - Open-Source, Boost-licensed C# library for geometric computing.
• Computational Geometry Software Libraries - Jeff Erickson 的 UIUC 几何软件的大型集合和库.
• The Stony Brook Algorithm Repository - 基于算法的存储库 The Algorithm Design Manual.
• Geometric Tools - 用于数学、图形、图像分析和物理领域计算的源代码库，其中包括一些计算几何算法.
• GeoLib - A fast and efficient computational geometry library available in C++, C# and Java.
• hull.js - 构建一组点的凸包的 JavaScript 库.
• S2 Geometry Library - 用于操纵几何形状的包. 与许多几何库不同，S2 主要设计用于处理球面几何，即绘制在球体上而不是平面 2D 地图上的形状. 这使得它特别适合处理地理数据.
• Computational Geometry Unity Library - 用于 Unity 的计算几何算法库.

Conferences¶

Strictly Computational Geometry¶

• Symposium on Computational Geometry - 年度研讨会.
• The Canadian Conference on Computational Geometry - 一年一度的国际盛会，旨在传播计算和组合几何领域的新成果. 会议通常在 8 月中旬的某个时间在加拿大某个城市举行.
• Japan Conference on Discrete and Computational Geometry, Graphs, and Games - 自 1997 年以来每年举行一次会议，2008 年除外.

Broader¶

• Symposium on Discrete Algorithms - ACM-SIAM，每年举办一次.
• Annual ACM Symposium on Theory of Computing - STOC 涵盖算法和计算理论中的所有研究领域.
• IEEE Symposium on Foundations of Computer Science - 由 IEEE 计算机协会计算数学基础技术委员会 (TCMF) 主办的旗舰会议，涵盖广泛的理论计算机科学.
• Annual Allerton Conference on Communications, Control and Computing - 吸引来自工业界、学术界和政府的一些最聪明的头脑讨论通信、控制和计算领域的创新.

Journals¶

• arXiv - 最近向 arXiv 提交的关于计算几何的文章.
• Elsevier - 计算几何理论和应用方面的研究论坛.
• Journal of Computational Geometry - 一份国际开放获取期刊，致力于发表计算几何各个方面最高质量的原创研究.

Competitive Programming¶

• HackerEarth - 一组关于计算几何的文章.
• TopCoder - 一组关于计算几何的文章.
• HackerRank - 一组使用计算几何的编程问题.
• GeeksforGeeks - 几何算法中大量常见问题和常见话题的实现和解释.

Courses¶

Open Courses¶

• MIT OCW - Nicholas Patrick 和 Takashi Maekawa 在
• Udemy - 关于在 C++ 中实现计算几何算法的课程.
• edX - 计算几何课程.
• Brilliant - 计算几何基本概念的练习题.

University Courses¶

• Brown University - 2005 年由 Roberto Tamassia 教授的课程.
• Washington University in St. Louis - 2017年陶炬教授的一门课程.
• The University of Maryland - Dave Mount 于 2002 年教授的课程.
• UC Santa Barbara - 2021 年由 Subhash Suri 教授的课程.
• UIUC - 杰夫·埃里克森 (Jeff Erickson) 于 2022 年教授的课程.
• UC Berkeley - 2019 年 Jonathan Shewchuk 教授的课程.
• Tufts - 2022 年由 Diane Souvaine 教授的课程.
• KIT - 2018 年由 Tamara Mchedlidze 和 Chih-Hung Liu 教授的课程.

Miscellaneous¶

• The Open Problems Project - 一个旨在记录计算几何和相关领域中重要的未解决问题的项目.
• Wolfram - 用 Wolfram 语言实现的计算几何算法的文档.
• Matlab - 在 Matlab 中实现的计算几何算法的文档.

Contributing¶

欢迎投稿！ 见 contribution guidelines.