计算几何项目报告.PDFVIP

计算几何项目报告 夏东林 慕巍 见英 问题背景： 包扎问题是计算几何中的一类经典难题，我们研究的是这一问题的简化版本——One Single Fold。任意给定一个简单多边形P 和一个圆盘D ，仅仅折叠一次P ，使得D 的表面全 部包围在P 内，没有任何的部分显露出来。 那么，任意给定的简单多边形必然会存在满足一次折叠覆盖条件的最大D。我们的问题 就是求出这样最大的D，并且给出折叠方案。 算法及原理： 显而易见，这个问题等价于在 P 中求两个半径相同且不相重叠的最大圆，然后过这两 个圆的圆心做一条垂直平分线，便是题目所求得包扎方案。 如图所示是在多边形中的相同大圆的一些例子。经过观察可知，如果给出的圆是最大圆 的话，必然会满足一些必要条件。比如，必然与边界相切，而且不能仅与一条边界相切，换 言之，两个大圆中至少要有一个与边界有两个以上的切点。由于圆的对称性，很容易知道其 中一个圆心在多边性的中轴上。由此，Demaine 证明了如下的引理： 引理1：任意简单多边形中一对最大的半径相等且不重叠圆，必然可以通过移动使得他 们的圆心全部在多边形的中轴上。 Medial Axis of two polygons 这就保证了我们在寻找问题的解答时，只需要将圆心限定在多边形的中轴之上。进一步， Demaine 证明了两个大圆如果不相切，必然可以将其中的一个移动到多边形中轴的某个顶 点上。 由于多边形中轴线可以分为直线段和抛物线段两类，所以有如下的结果： 中轴线上最大圆半径 边 类 最大半径计算表达式 型 e e 1 2 均在 直线 中轴 上 圆心坐标 e1 在直 线中 轴 上， e2 在抛 物线 中轴 上 e e 1 2 全部 问题的方程是一个8 次的方程，由于比较繁琐，暂不在这里 在抛 给出。 物线 上 根据如上的原理，我们设计的算法步骤如下： 1．计算多边形P 的中轴M 2 ．for 中轴的每条边e1, do ： (a) for 中轴的每个顶点v, do: 找到圆心为v 的在多边形P 内部的最大圆，设半径为r 在边e1 上发现点p ，使得圆心为p 半径为r 的圆在多边形P 内，且d(p,v)=2*r 若找到则将其加入圆对队列 (b) for M 的每条边e2 do: 找到点p1 在边e1 上，点p2 在边e2 上，r ＝d （p1 ，p2 ）/2, 以点p1 ，p2 为圆心，r 为半径分别作圆，且都在多边形内。 若找到则将其加入圆对队列 3 ．在所有的圆对中发现半径最大的，即为结果。 系统设计 系统采用了以VC 编程为基本框架，嵌入多种功能模块的方式。其中包括两类主要模块， 第一个是经过java 整理的多边形中轴计算模块，第二个是采用Matlab 进行编写的方程求解 模块。VC 编写的框架负责处理界面，数据的输入输出和中间两次的数据转换，数据合法性 的验证。 过程中遇到的问题及解决对策 (1) 抛物线的多解问题 由于抛物线是二次曲线，解方程会有多根。我们将抛物线由顶点分割为两部分。 (2) 方程求解问题 由于线段边和抛物线边的方程是4 次方的，抛物线边和抛物线边的方程是8 次方的， 因此求解时要利用牛顿插值。我们借用了matlab 工具来解。 (3) 在VC 中画抛物线 由于一般性的抛物线方程较为复杂，而且一般x.y 坐标不是一一对应，所以要用参 数表示。我们采用抛物线