15.1 引言 与点、线、多边形、圆形等各种几何图形相关的算法称为计算几何(computational geometry)算法。计算几何已成为3D图形、CAD、机器人等多种领域的基础,在计算机学科中占据了重要地位。程序设计竞赛中也常常出现有关计算几何的问题。 计算几何包含了很多内容,涉及面非常广。不过,程序设计竞赛中出现的题目大多集中于基础性的问题。解决这种问题时需要的并不是宏大的算法或设计范式,而是把本科线性代数或高中几何学的内容转换成代码。因此,本章重点在于如何将基础数学理论转换成既简洁又无异常的代码形式。 计算几何是涉及二维平面和三维立体图形的一门学问,而程序设计竞赛的问题主要是二维几何学相关内容。因此,本书也只介绍二维几何学。