卫星舱布局设计问题属于NP-Hard或NP-Complete问题,它既存在计算复杂性又具有工程复杂性,求解困难,达到工程应用要求更难。卫星舱布局设计属于卫星总体布局设计的重要内容,关系到卫星性能、寿命、可靠性等问题。本课题组多年来从事卫星舱布局设计研究,其中存在若干图形学问题需要解决。为此,本文做了如下3个问题的研究:(1)由于布局与布局模式密切相关,研究了布局模式问题,并将它与遗传算法相结合构成基于布局模式的遗传算法(Layout Pattern Based Genetic Algorithm,LPBGA),用于求解2-D带性能约束的布局问题;(2)在本课题给出的人机结合的遗传算法中,需检索先验布局图作为参考图,并转化为数值解。为此研究了规则图形检测,又称为图形的形数转换;(3)研究了圆柱体-圆柱体、长方体-长方体和凸多面体-凸多面体的快速干涉计算问题。在基于演化算法的卫星舱复杂布局优化过程中,每次迭代需要对待布物之间作干涉计算,因此,如何寻求迭代过程中快速3-D干涉计算法是一个待解决的问题。将上述研究成果做为卫星舱布局优化的支撑方法和技术,也期望具有一定普遍性。本文主要工作如下:1.本文给出了基于完全关联图的布局模式构造算法,它包括最小多边形法和准边界直线法。本文的布局模式构造方法不论待布物分布稀疏或密集都是适用的,并且准边界直线方法的计算复杂度也较低。进而给出基于布局模式的遗传算法,用于求解2-D带性能约束的布局问题。其关键是在优化迭代过程中的每一代,都自动构造最优个体的布局模式解(个体)替代种群中较差的个体,跳出局部最优,避免早熟以提高求解效率和解的质量。经2-D带性能约束的布局设计的数值实验表明:本文方法与遗传算法(GA)、人机交互遗传算法(HCIGA)和并行混合蚂蚁免疫算法(PHAIA)等相比,具有较高的精度和效率。2.本文提出了一种3类图形的快速检测(图形至数值变换)的广义Hough变换方法。包括:(1)多个圆检测;(2)多个矩形检测;(3)混合多个圆、多个矩形检测。由于减少了无效采样和无效计算,经简化卫星舱布局的2-D规则图形检测等算例验证,提高了其检测效率。3.本文给出了圆柱体-圆柱体、长方体-长方体和凸多面体-凸多面体的快速不干涉检测算法。先将3-D问题投影为2-D问题,然后基于不适合多边形(no-fit polygon,NFP)对2-D问题实现快速不干涉检测,凸多面体不干涉检测算法还采用了向中心线正投影作不干涉加速检测。经遗传天线布局问题等算例验证,表明了其有效性。本文以卫星舱布局问题为背景,研究与该布局问题求解相关的三个图形学问题,即布局模式、2-D规则图形检测(形数变换)和3-D规则图形(圆柱体、长方体和凸多面体)的不干涉检测问题,为卫星舱布局问题求解提供支持。此外,上述算法和方法也具有一定的普遍性,可望推广应用于其它某些布局问题求解。