清华大学2022春 computational geometry 讲义：理论、算法与实践

清华大学的"计算几何"课程是2022春季学期的重要教学资源，旨在为学生提供坚实的理论基础和实用技能，使他们在未来的研究和工作中能够从几何的角度理解和解决复杂问题。课程内容涵盖了计算几何的广泛理论和实践，从对计算几何理论的总体认识出发，引导学生深入理解几何问题求解的基本范式和策略，如递增式构造、平面扫描、分治法、分层化、近似算法以及随机化方法。 核心知识点包括但不限于： 1. 计算几何理论：课程强调理解几何在计算机科学中的应用，让学生具备整体把握计算几何理论的能力，这将为他们的后续研究提供几何思维方式的支撑。 2. 几何构造与求解策略：课程深入讲解如何通过递增式构造方法来构建复杂几何结构，平面扫描技术用于处理大规模数据集，分治策略用于分割和简化问题，分层化处理有助于优化性能，近似算法则适用于处理精度与效率之间的权衡，而随机化方法在处理不确定性和效率方面具有重要作用。 3. 基本几何结构与算法：凸包、多边形细分、Voronoi图和Delaunay三角剖分等基本结构是几何分析的核心，这些内容对于理解空间数据的组织和操作至关重要。此外，课程还涉及几何求交、点定位、范围查找和截窗查询等常用算法，这些都是数据结构和算法设计的基础。 4. 学习资源：丰富的学习资料包括讲义、课件、演示视频，以及在线课程MOOC，学生可以通过XuetangX等平台获取课程内容。此外，还有测验、考试、编程作业、OJ练习和期末考试等评估方式，确保学生对所学知识的掌握。 5. 参与与考核：课程强调课堂参与，鼓励学生通过弹幕互动和讨论区提问，作业创意、勘误、测例设计和进步幅度将作为加分项。总成绩由百分制决定，通过综合考虑基本知识点的掌握、方法技巧的应用以及课外活动的表现来评定等级。 6. 编程作业与期末考试：课程包含七次编程作业，每个作业包含六道题目，学生需要通过OJ平台完成。期末考试则测试学生对整个课程内容的深度理解，重点考察基本概念和技能的综合运用。 通过这门课程的学习，学生不仅将获得扎实的计算几何理论知识，还将培养解决问题的策略思维和实践能力，为他们在计算机图形学、GIS、机器人、游戏开发等领域的发展打下坚实基础。