Study On Several Graphic Problems For Satellite Module Layout

The problem of satellite module layout design belongs to NP-hard or NP-Complete problem.This problem exists not only computational complexity,but also engineering complexity.Therefore,it is difficult to solve complex layout problem and is more difficult to satisfy the requirement of engineering application.Layout design of satellite module is part of its comprehensive design and has direct relation to its preference,live and dependability and so on.Our team engaged in the study of layout design of a satellite module for many years. The several graphics problems in the study need to be resolved.Therefore,this dissertation studies the following related problems:(1) layout pattern problem.Due to close relation between layout and layout topology,layout pattern is studied and layout pattern based genetic algorithm(LPBGA) combined with genetic algorithm(GA) is used to solve 2-D layout problems with performance constraint;(2) problem of regular graphc detection.Because it is necessary for human computer interactive genetic algorithm(HCIGA) brought forward by our team that prior knowledge layout diagram retrieved,which is used as reference scheme of layout design,is transformed into numerical solutions by Hough transform;(3) interference computation problem.Because interference computation is necessary for every time iterative in course of layout optimization of satellite module,searching out fast 3-D non-interference algorithm used in the iterative become too urgent to admit of longer delay.Therefore,the author study on interference detection between the two cylinders,the two cuboids,the two convex polyhedrons are studied.Obtain results can act as supporting algorithms and technology of the layout design for satellite module and can be expected to be to other engineering problem.First,approaches of constructing layout pattern based on complete incidence graph are proposed in this dissertation,including quasi-boundary line approach(QBLA) and minimization polygon approach(MPA).Author's approaches fit both to case of sparse object and dense.Further,algorithm complexity of QBLA is lower than Li G.Q.'s algorithm.LPBGA is presented to solve 2-D layout problems with performance constraint.It is key that a layout pattern resolution of the current best individual can be constructed automatically and used to replace the worse one in the population for every generation of optimization,so that evolution computation can skipped out local optimal resolution and avoid prematurity(early trap) to improve solving efficiency and resolution quality.Numerical experiment of 2-D layout design with constraint of performance shows that the approach performed better on computational efficiency and quality of solution than HCIGA,parallel hybrid ant immune algorithm(PHAIA) and GA.Secondly,three rapid generalized Hough transform approaches for graph detection are presented in this dissertation respectively,which includes:(1) detection for multi-circle;(2) detection for multi-rectangle;(3) detection for hybrid multi-circle and multi-rectangle.Owing to decrease of invalid sampling and invalid computation,author's approach improve detection efficiency.The examples of regular graph detection of simplified satellite module validate this conclusion.Thirdly,fast non-interference detection algorithms between two cylinders,two cuboids, two convex polyhedrons are given respectively.Three algorithms transform 3-D no interference detection problem into 2-D problem and then detect no interference of 3-D objects by judging no interference of simple 2-D graphic.In addition,efficiency of detecting separation of no interference detection algorithm for convex polyhedrons speeded up by using orthogonal projection of two convex polyhedrons on straight line through their center point. In this dissertation,numerical experiments for 3-D no interference detection and the example of layout problem of genetic antenna show the validity and feasibility of author's approaches.This dissertation uses layout design of a satellite module as background to study three graphics problems,which respectively are layout pattern,2-D reglar graph detection and interference computation of 3-D regular graph(cylinder,cuboid and convex polyhedron).Its aim is to provide graph algorithm for solving layout problem of satellite module.The abovementioned approaches have a certain catholicity.The author hope that this approaches can applied to the solving of some other layout problem.