不规则图形排序.doc

不规则图形的排序 《数学模型部分》 （西南民族大学计科学院 成都 610041） 问题提出： 在医疗事业上，放射治疗肿瘤的基本原理是让高能射线‘杀死’肿瘤区的不良细胞，但同时要求肿瘤区外的细胞尽量避免受损伤。这就要求在治疗时要用合适的材料把良性组织保护起来，而用一定高度的挡铅块是其中一种方便的做法。浇注低熔点铅的一种经济的模具就是泡沫。切割的泡沫的形状大致是治疗肿瘤区的形状，在浇注低熔点铅后，泡沫外的区域就有了铅，泡沫占据的区域就是空隙，就这样形成了挡铅块。在具体治疗时，把挡铅块放在射线源和肿瘤区之间，这样就起到了保护良性组织的作用。比如肿瘤的切除需要先在其中填充泡沫，使肿瘤分割为许多不同的图形，当然我们希望这些图形都能有一个最佳排序，这样我们的填充物就越少。（也就是说，假设有一个容器，我们往里面放一些不规则的图形进行一定原则的排序，使得剩下的面积最大）。现考察如下具体的问题： 一个300mm*300mm的正方形容器（如图一），定义15幅不规则相异图形Pi（i=1, …，15），并且这15图形要求为单连通区域，然后把这15个图形放进这个正方形中，要求图形之间的距离为4mm，最后图形经过排序后，要使得剩余的面积S最大， （图一）………………………4mmSmax300mm300mm求S的最大值 （图一） ……………………… 4mm Smax 300mm 300mm 求S的最大值 ………… ………… 要求图形方向可以变换，以求最好的排序！ 写出算法思想和过程 编程序实现（要求：可以在其他机子上运行，可以读取其机子上的图形运行程序，并且能输出结果！求出Smax！） 问题的分析 假设每个不规则的单连通域图形都被一个小矩形所包围，而且这个矩形要求恰好能容纳这个图形（面积是最小的），也就是说，求一个最佳的矩形来配个不规则图形，在这个过程中，我们应该对图形进行方向的变换，使矩形的面积达到最小，然后把这个矩形的长和宽增加2mm（题意本来是说要图形之间间距为4mm）。 2mm2mmImage1 2mm 2mm Image1 图一 按照题设的要求，将每个要求拼接的图形的最左，做右，最上，最下的顶点上分别做平行于X轴，Y轴的四条平行线，四条直线相交构成矩形，则题设问题中转化为每个图形相切矩形之间的距离，由于题设要求两个图形之间的距离等于4MM，那么我们可以将求的矩形的长和宽各自扩大2MM，构成一个新的矩形，则在固定的容器中拼接不规则不相邻图象的问题转化为规则矩形的相邻拼接问题。但是 各个图形的想切或者相邻的矩形不是随意的，必须是让该图形想切或者相切的矩形的面积最小，这样就可以保证题目要求的Smax 在实际上为最大值，下面我们讨论如何求的一个不规则图形的相切或者相接的面积最小的矩形 二. 问题说明及数学模型 2.1为了说明问题，下面给出一个正方形容器内的图形布局问题，图内有15个不规则图形（简称图元）Xi，i∈I={1，2……15}，我们建立坐标系XOY，第I个图形的形心Oi=（xi，yi），不规则图形形心到边界的最大距离为ri，对应最佳矩形的长和宽分别为ai,bi,假设这15个图形是均匀的（重心和形心重合）。要求这15个图形尽量排的紧密，使得剩余的面积最大，满足如下约束： 各图元之间不发生重合 图元不超出正方形容器 布局后使得剩余面积S最大 （xi，yi）Y （xi，yi） Y O O X X R R 图元布局示意 图元布局示意 以上问题的一般性数学模型如下： 22 求Xi（i∈I）使其满足： 2 2 min f（Xi）=max|√xi +yi +ri| (1) 1. 图元之间不干涉条件 f1（Xi）=ri+rj-√(xi-xj)* (xi-xj)+(yi-yj)* (yi-yj) ≤0 (2) i≠j,i,j∈I; 2. 图元与容器之间不干涉条件： f2（Xi）=√xi*xi +yi*yi +ri-R ≤0 i∈I (3) 3. S面积最大的条件 当我们建立的最佳矩形拼接最优时。达到无缝拼接！ 2.2 关于求最佳矩形的数学模型 2.2.1 我们假设这些图形都是凸边形，证明有一条边重合于所求矩形的边时这个矩形的面积最小，具体证明如下： 以简单的三角形为例，依次推广，见图二 图a 图a h h L1 L1 图bh 图b h L2a L2 a 图二 图二 由图a，图b 可知道，假设面积分别为S1，S2，则： S1=L1*h 在图b 中，L2=L1*cosa S2=L1*cosa*（h/cosa+C） 其中C是一个大于0的数，所以S2-S1