第9章 计算几何

概述

我们将会介绍一系列计算几何的相关问题。在过去几个世纪里,数学家们已经研究过很多这样的问题,自20世纪70年代起,计算几何开始被看做几何算法的一个子学科系统,相关数据结构保证了算法能够高效地执行。在这样的条件下,算法帮助技术人员解决了现实中大量的问题,本章将会介绍其中一些算法。本章阐述的一些数据结构和算法对于本科生来说比较高深。但是,软件专业人员能够很容易地理解这些数据结构和算法的原理,并且将其应用到实践中。

经典问题

计算几何和点、线和面这样的几何物体关系非常紧密。我们通过如下定义来判断是否一个问题为计算几何问题:(a)输入的数据类型。(b)将要进行的计算。(c)任务是静态的还是动态的。我们利用这些分类方法,针对不同的跨领域问题采取不同的技术来改善性能。

输入数据

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

计算机和问题必须定义输入数据。最常用的几种输入数据是:

·二维平面点集。

·二维平面线段集。

·二维平面矩形集合。

·二维平面任意多边形集合。

二维结构(线、矩形和圆)有着对应的三维结构(面、立方体和球面)和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章存储图的两种方法,邻接表和邻接矩阵,仔细考虑一下它们的优点和局限性。