概述
我们将会介绍一系列计算几何的相关问题。在过去几个世纪里，数学家们已经研究过很多这样的问题，自20世纪70年代起，计算几何开始被看做几何算法的一个子学科系统，相关数据结构保证了算法能够高效地执行。在这样的条件下，算法帮助技术人员解决了现实中大量的问题，本章将会介绍其中一些算法。本章阐述的一些数据结构和算法对于本科生来说比较高深。但是，软件专业人员能够很容易地理解这些数据结构和算法的原理，并且将其应用到实践中。
经典问题
计算几何和点、线和面这样的几何物体关系非常紧密。我们通过如下定义来判断是否一个问题为计算几何问题：（a）输入的数据类型。（b）将要进行的计算。（c）任务是静态的还是动态的。我们利用这些分类方法，针对不同的跨领域问题采取不同的技术来改善性能。
输入数据
计算机和问题必须定义输入数据。最常用的几种输入数据是：
·二维平面点集。
·二维平面线段集。
·二维平面矩形集合。
·二维平面任意多边形集合。
二维结构（线、矩形和圆）有着对应的三维结构（面、立方体和球面）和n维结构（例如超平面、超立方和超球体）。高级计算几何问题均可以扩展到更高的维度。
我们需要三个以上的维度吗？
一个计算几何问题：在一个29维面上有1400万个点，寻找每个点的最近邻接点。
现实世界的服务：eHarmony婚介服务（http://www.eharmony.com）宣称他们是“第一家使用科学方法来匹配单身男女的网络婚介服务商”。这家公司使用的匹配相容系统注册了专利（美国专利号6735568），eHarmony将会预测两个人是否能够长期包容对方。这个系统的所有用户（据估计在2007年2月时达到了1400万）需要填写一个436个问题的关系调查问卷。eHarmony然后从29个方面（即29个维度）来计算两个人的匹配度。在2003年11月的一份报告中，eHarmony指出91%的用户有10个或者更多的匹配人选。
数据置信度问题：一个包含1400万份记录的输入文件，每份记录有29个文本或者数字值的字段。有些值可能错误或者缺失。我们会用其他的近似记录来代替这份有问题的记录。
我们首先将阐述一系列计算几何的核心接口，然后再介绍一些实现这些接口的类。在实现这些接口的基础上，所有的算法都会保证最大的便携性。
本章的算法基于图9-1所示的核心思想：
IPoint
表示最基本的笛卡儿点（x,y），坐标是双浮点精度。我们编写了一个比较器，首先对x坐标从左至右进行排序，然后再对y从下到上进行排序。
IRectangle
表示笛卡儿平面上的矩形，能够判断是否和一个点相交或者是否包含另外一个IRectangle。
ILineSegment
表示笛卡儿平面上的一个有限长度线段，并且有固定的起始点。在“一般位置”上，除了水平线（这种情况下，最左边的点被当作起始点），起始点的y坐标要高于终止点的y坐标。它能够返回是否和其他的ILineSegment或者IPoint对象相交，在考虑线段的方向时，还能返回一个IPoint对象在其左边还是右边。
这些处理二维的核心思想可以很自然地扩展到如何处理多维度，如图9-2所示。
IMultiPoint
表示一个n维的笛卡儿平面点，每个坐标值是双浮点精度，能够返回和另外一个相同维度的IMultiPoint的距离，也可成一个坐标值的数组，用来优化某些算法的性能。
图 9-1 计算几何的核心接口 图 9-2 多维数据的接口IHypercube
表示一个n维的固体，能够判断是否和一个IMultiPoint相交或者是否包含另外一个同一维度上的IHypercube。
IMultiLineSegment
表示在n维笛卡儿平面上一个有限长度线段。
一般来说，点的坐标值都是实数，所以我们的实现必须用浮点值来存储数据。在20世纪70年代，由于计算机硬件的限制，浮点计算的开销要大于整数计算的开销。但是现在的计算机已经不存在这个问题。第2章讨论了更重要的几个问题，例如舍入错误，这些问题和浮点计算息息相关，对本章算法产生了不利影响。
最后，有些计算几何的算法需要整数值的间距，如图9-3所示。
图 9-3 表示间距[left，right)的接口IInterval
表示一个半开区间[left，right)，left和right为整数值，并且最小单位为1，它包含了left值，但是不包含right值。它能够返回和一个整数值的关系（左边、右边或者相交）。
我们会编写一系列类实现这些接口类型，用来初始化对象（例如，类TwoDPoint实现了IPoint和IMultiPoint接口）。
计算
计算几何明显和空间问题相关，见表9-1。有三种主要的任务。
查询
寻找数据中满足条件限制（例如最近或者最远）的元素，这类任务和第5章的查找算法直接相关。
计算
在输入数据（例如线段）上进行一系列的计算，得到一些包含了输入数据元素的几何结构（例如线段的相交点）。计算的结果就是问题的结果。
预处理
将巨大规模的输入数据组织成一种数据结构，来计算一系列问题的结果。也就是说，预处理任务的结果就是这一系列问题的输入。
在本章的剩下部分，我们将会抽象各种计算几何问题然后进行计算。这些技术的应用范围并不仅仅限于几何问题，在现实中也有很多应用。例如，扫描技术能够帮助我们对无序对象（例如点、线和多边形）排序然后进行后续处理。
任务的本质
静态任务是处理一个固定的输入集合。但是，有两个非常重要的动态思想改变了解决问题的方法。
·是否任务需要多次在同一个输入数据集上进行计算？如果是的话，那么我们需要对输入数据进行预处理来改善远期性能。
·输入数据是否在处理一次之后会改变？如果会的话，那么我们需要选择能够应对这种变化的数据结构。
动态任务要求数据结构能够较好地应对变化的输入。固定长度的数组也许适用于静态的任务，但是对于动态任务就显得力不从心，此时就需要链表或者栈来实现通用化。回忆一下第6章存储图的两种方法，邻接表和邻接矩阵，仔细考虑一下它们的优点和局限性。