有障碍物情况下的二维空间中两点间的最短路线

这里只讨论一个障碍物的情况，多个障碍物时可以用计算机迭代找出来，这里相当介绍你一个算法。障碍物为一个闭集，由巴拿赫定理的几何形式知存在一个支撑泛函f1使得f1（A）=0几何上解释为过点A有一条切线，同理存在f2使得f2(B)=0；找到了f1和f2之后，再在各自上找一点C和D使得CD得到的线性泛函也为支撑泛函（几何解释就是CD也为切线）得到的线路A-C-D-B为所求。相关理论的证明是已经没问题的，修读过泛函就没问题，因此你只需理解它的操作思想。

你说的没错！巴拿赫定理成立的条件是凸闭集，所以我用错了。不过还是值得像你那样考虑先求出凸闭包。迭代的思想我是这样认为的：

比如你有两个障碍物，你可以假设存在一点E在两个障碍物的凸闭包的公切线上，然后分别对AE，BE做前述操作。如果有n个时候我们先看看AB线段需要跨越哪些障碍物，然后排除掉其他干扰的，剩下的先做个从左到右排序吧，然后再在相邻两个之间像之前说的那样插入一个点（不过这里有两条公切线，所以到底是插在哪条上好，直接这样是判断不出来的，这要根据实际情况，要不就让计算机两条上都插再比较咯，但这样时间复杂度就大了些，暂时还没有想到好的判别标准）

JPG和GIF存储所占空间最小~~

图像的存储方法有好多种，比如使用画笔将图像画在纸上，通过摄影将图像存储在胶卷上，使用数码相机、扫描仪等设备将图像存储在各种存储介质里。而这些图像可以归为两类，即：传统图像和数码图像。跟传统图像不同的是，数码图像使用数字来记录物体的形状和色彩。

数码图像又分为两大类，一类是位图，另一类是矢量图。位图是由不同亮度和颜色的像素所组成，适合表现大量的图像细节，可以很好的反映明暗的变化、复杂的场景和颜色，它的特点是能表现逼真的图像效果，但是文件比较大，并且缩放时清晰度会降低并出现锯齿。位图有种类繁多的文件格式，常见的有JPEG、PCX、BMP、PSD、PIC、GIF和TIFF等。

位图图像效果好，放大以后会失真：

而矢量图则使用直线和曲线来描述图形，这些图形的元素是一些点、线、矩形、多边形、圆和弧线等等，它们都是通过数学公式计算获得的，所以矢量图形文件一般较小。矢量图形的优点是无论放大、缩小或旋转等都不会失真；缺点是难以表现色彩层次丰富的逼真图像效果，而且显示矢量图也需要花费一些时间。矢量图形主要用于插图、文字和可以自由缩放的徽标等图形。一般常见的文件格式有AI等。

矢量图图像效果差，放大以后不会失真：

数码图像的文件格式

为了能表现逼真的图像效果，使用数码相机拍摄的图片都是位图文件；位图文件的格式多达几十种，不同的格式都有不同的特性，下面我们来介绍一下位图文件的几种常见格式。

1、JPEG

JPEG文件格式是Joint Photographic Experts Group(联合图像专家组)的缩写，文件的后缀名是.JPG，这也是我们最常见的一种文件格式，几乎所有的图像软件都可以打开它。现在，它已经成为印刷品和万维网发布的压缩文件的主要格式。JPEG格式可以支持16M种颜色，能很好地再现全彩色图像，较适合摄影图像的存储。由于JPEG格式的压缩算法是采用平衡像素之间的亮度色彩来压缩的，因而更有利于表现带有渐变色彩且没有清晰轮廓的图像。

JPEG文件格式允许用可变压缩的方法，保存8位、24位、32位深度的图像。JPEG使用了有损压缩格式，这就使它成为迅速显示图像并保存较好分辨率的理想格式。当进行印刷或在显示器上观察时，JPEG一般可将图像压缩为原大小的十分之一而看不出明显差异。也正是由于JPEG格式可以进行大幅度的压缩，使得它方便储存、通过网络进行传送，所以得到了广泛的应用。当使用JPEG格式保存图像时，Photoshop给出了多种保存选项，你可以选择用不同的压缩比例对JPEG文件进行压缩，即压缩率和图像质量都是可选的。

2、TIFF

TIFF是Tagged Image File Format(标记图像文件格式)的缩写，文件的后缀名是.TIF，这是现阶段印刷行业使用最广泛的文件格式。这种文件格式是由Aldus和Microsoft公司为存储黑白图像、灰度图像和彩色图像而定义的存储格式，现在己经成为出版多媒体CD-ROM中的一个重要文件格式。虽然TIFF格式的历史比其它的文件格式长一些，但现在仍是使用最广泛的行业标准位图文件格式，这主要是由于TIFF格式的规格经过多次改进。TIFF位图可具有任何大小的尺寸和分辨率。在理论上它能够有无限位深，即：每样本点1-8位、24位、32位(CMYK模式)或48位(RGB模式)。TIFF格式能对灰度、J健、CMYK模式、索引颜色模式或RGB模式进行编码。几乎所有工作中涉及位图的应用程序，都能处理TIFF文件格式—无论是置入、打印、修整还是编辑位图。

TIFF格式可包含压缩和非压缩图像数据，如使用无损压缩方法LZW来压缩文件，图像的数据不会减少，即信息在处理过程中不会损失，能够产生大约2：1的压缩比，可将原稿文件消减到一半左右。

3、RAW

目前，数码相机的存储格式除了JPEG，TIFF外，还有RAW格式。RAW究竟是一种什么样的格式？请用在何种情况下使用这种RAW格式？又有何优缺点呢？其实，RAW格式并不是一种图像格式，不能直接编辑。RAW格式是CCD或CMOS在将光信号转换为电信号时的电平高低的原始记录，单纯地将数码相机内部没有进行任何处理的图像数据，即CCD等摄影元件直接得到的电信号进行数字化处理而得到的。而用JPEG格式拍摄时，先在数码相机内部添加白平衡和饱和度等参数，然后生成图像数据、进行压缩处理。RAW数据由于没有进行图像处理，因此只能利用数码相机附带的RAW数据处理软件将其转换成TIFF等普通图像数据。

RAW格式的图像文件保留了CCD捕获图像最高质量的信息，也为后期的制作提供了最大的余地。因此，常常被采用以获得最好质量的图像。由于各厂家CCD/CMOS的排列和转换方式不同，RAW的记录方式也不同，只有通过厂家提供的转换程序转换成通用图像格式，才能为图像处理软件接受。

鉴于此，著名的软件公司Adobe在近日发布了一种新的文件格式：DNG(Digital Negative Specification)，想以此来统一数码相机使用的RAW格式，规范原始格式这种各自为政的局面。Adobe公司还发布了一个免费的软件，可以将超过65种相机的原始格式转换为DNG格式。

4、GIF

GIF是Graphics Interchange Fotmat(图像交换格式)的缩写，文件的后缀名是.GIF。这是由CompuServe公司在1987年开发的图像文件存储格式，可以说是历史悠久。GIF格式是Web页上使用最普遍的图像文件格式，并且有极少数低像素的数码相机拍摄的文件仍然用该格式存储。

GIF格式只能保存最大8位色深的数码图像，所以它最多只能用256色来表现物体，对于色彩复杂的物体它就力不从心了。正因为此，它的文件比较小，适合网络传输，而且它还可以用来制作动画。

5、BMP

BMP是Bitmap的缩写，后缀名是.BMP。它是微软公司为Windows环境设置的标准图像格式，在Windows环境下运行的所有图像处理软件都支持这种格式。Windows 3.0以前的BMP位图文件格式与显示设备有关，因此把它称为设备相关位图(device-dependent bitmap，DDB)文件格式。Windows 3.0以后的BMP位图文件格式与显示设备无关，因此把这种BMP位图文件格式称为设备无关位图(device-independent bitmap，DIB)格式，目的是为了让Windows能够在任何类型的显示设备上显示BMP位图文件。这种格式虽然是Windows环境下的标准图像格式，但是其体积庞大，不利于网络传输。

---