计算几何及应用

《计算几何及应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、科学出版社职教技术出版中心www.abook.cn中创软件丛书计算几何及应用汪嘉业王文平屠长河杨承磊编著北京内容简介本书比较全面地介绍了计算几何的基本问题、基础理论和算法。本书前１２章分别介绍了凸包、Voronoi图、三角剖分、多边形剖分、几何搜索、相交计算、排列、可见性计算、路径规划等基本计算几何问题和算法，第１３、１４章则分别探讨了若干随机和并行的计算几何算法，最后一章给出了关于计算几何的几个实际研究和应用中的例子。本书在注重介绍计算几何基础理论的同时，也注意介绍简洁、实用和易编程的算法，力求易读、易懂，并使读者能够应用这些理论和算法。为便于消化和理解书

2、中内容，每章末附有习题，以及大量参考文献。本书可作为高等院校计算机及应用数学等学科的本科生、研究生学习计算几何的教材，也可作为从事计算几何研究或应用的其他科技工作者的参考用书。图书在版编目（CIP）数据计算几何及应用／汪嘉业等编著．—北京：科学出版社，２０１１　（中创软件丛书）ISBN９７８‐７‐０３‐０３２２５７‐９　Ⅰ畅①计⋯　Ⅱ畅①汪⋯　Ⅲ畅①计算几何②计算机算法　Ⅳ畅①０１８②TP３０１畅６中国版本图书馆CIP数据核字（２０１１）第１７８４５７号责任编辑：鞠丽娜／责任校对：耿耘责任印制：吕春珉／封面设计：三函设计出版北京东黄城根北街１６号邮政编码：１

3、００７１７http：／／www．sciencep．com科学出版社印刷科学出版社发行各地新华书店经销倡２０１１年９月第一版开本：７８７×１０９２　１／１６２０１１年９月第一次印刷印张：１９１／２职教技术出版中心印数：１—３０００字数：４４２０００www.abook.cn定价：46畅00元（如有印装质量问题，我社负责调换枙　　枛）销售部电话：０１０‐６２１３４９８８　编辑部电话０１０‐６２１３８９７８‐８００２版权所有，侵权必究举报电话：０１０‐６４０３０２２９；０１０‐６４０３４３１５；１３５０１１５１３０３前言在２０世纪７０年代，“计算几何”这个名词曾经被

4、不同学术领域如模式识别、自由曲线曲面设计以及离散几何问题的算法设计与分析等使用过。１９７８年，M畅I畅Shamos在其博士论文“ComputationalGeometry”中归纳和提出了一百多个离散几何问题及其算法。此后，计算几何被公认为是“离散几何问题的算法设计与分析”这一学术领域的名称。经过近３０多年的快速发展，其研究内容不断扩大，涉及了凸包、Voronoi图、三角剖分、多边形剖分、几何搜索、求交、可见性计算、路径规划、碰撞检测等众多内容。计算几何所研究的这些基本问题大都是欧几里德几何问题。它们之所以到现在才被提出来并研究其算法，是因为它们涉及了大量的计

5、算，所以只有在使用计算机的时代才会被提出来并要求解决。同时，这些问题有着广泛的应用背景。如在计算机图形学及虚拟现实中，从建模到绘制几乎都会用到计算几何的算法；几何搜索可为数据库的搜索提供有效算法；机器人运动规划、碰撞计算等计算几何的重要内容也为大规模集成电路设计、机械加工、虚拟装配、GIS等提供了必不可少的实践和理论基础。此外，计算几何还为线性规划、聚类分析、概率统计方法等提供新的算法。由于这个领域有着非常广泛的应用背景及深入探讨的理论价值，因此在国际上很快成为学术研究的热点，受到广泛重视。如在美国斯坦福大学、普林斯顿大学等国际著名学府都有专门的计算几何研究

6、团队；目前已有多个计算几何的国际学术期刊；每年也召开若干个国际学术会议。在国际上热火朝天地研究计算几何的３０年中，这门学科在我国几乎是被冷落的，很少有人系统地对其进行研究，开设这门课程的也仅有清华大学、浙江大学、山东大学等少数几个单位。一般地，研究算法的学者多热衷于图论算法的设计与分析；而对研究与计算有关的几何问题的学者而言，在连续的曲线曲面上做研究更是得心应手。然而，人们在很多应用中又不可避免地会碰到各种各样的计算几何问题。尽管在我国的学术刊物上也偶尔会刊登与应用有密切关联的讨论离散几何的文章，但由于国内缺乏对该学科的系统研究和教学的环境，研究水平与国外相

7、比还有一定差距。为此，我们在多年从事计算几何科研、教学工作的基础上出版了本书，力争比较全面地介绍计算几何的基本问题、基础理论和算法，以促进国内计算几何的研究和教学工作。本书适合作为研究生的教材。若为硕士生上课，可以讲授其中部分章节，如第一章～第九章。对于计算机专业的学生，由于较少学习具有严格逻辑推理的课程，所以可通过本书的学习，弥补这方面能力培养的不足。对于数学或其他专业的学生，通过本书的学习，可以对计算机算法的研究方法有所了解。本书也可作为从事计算几何研究或应用的其他科技工作者的参考用书。本书的写作特色是在注重介绍计算几何基础理论的同时，也注意介绍简洁、实

8、用和　·ii·计算几何及应用易编程的算法，力求让读者