Study On The Rectangle Detection Of The Layout Knowledge Graph And Heuristic Search Algorithm For The Weighted Circle Packing

The container packing problems refer to place a number of objectives into a container with the non-interference while satisfying optimal utilization and several given constraints. These problems have respective application background, such as the architecture design, garment industry, electronic industry and medical equipment, aerospace, transportation, machinery manufacturing, urban planning and so on. The quality of the packing scheme has a significant impact on the productive efficiency, economic benefit and security of the system etc.The containers packing problems are a type of classical packing problems and knowledge-based algorithms are the hot areas to study. The obtaining layout knowle-dge from the prior packing scheme graphs and the knowledge-based algorithm for the circle packing problems with performance constraints are studied in this paper. It includes:(ⅰ) The weighted circle packing problem base on knowledge is studied, on the background of the printed circuit board design issues;(ⅱ) The rectangle detection in circle container is studied, on the background of the satellite cabin layout problem. For (ⅰ), due to its NP-hard attribute, it is very difficult to solve in polynomial time. Many scholars have propose many effective algorithms through a lot of practice, include:heuristic algorithms, artificial intelligence, numerical optimization algorithm, evolutionary algorithms, and human-machine interactive algorithms. For (ⅱ), the detecting method include:line-based detection method, Hough transform window and a chain code detection methods. But how to use the features of the rectangle to effectively and quickly detect rectangle, especially incomplete rectangle, still need further study. Many works for (ⅰ) and (ⅱ) are done in this paper, under the support of National Natural Science Foundation and Research Foundation of Education Bureau of Hunan Province, and some research results are obtained.It has following innovations:1. Aiming at the parameter calculation of the knowledge solution of a layout problem, this paper proposed a detection method for the multi-rectangle of the layout knowledge solution. It determined each possible rectangle with two random edge points and third edge point searched on a circle that the diameter is a line segment between two sampling edge points. When randomly sampling two points, the invalid sample is decreased by recognizing isolated and half-link noises and non-diagonal angle points. Using properties of the rectangle, we quickly determine other two vertexpoints of the possible rectangle, and affirm it for true rectangle so that the invalidcomputation is decreased. The experimental results demonstrate that the proposedalgorithm can detect quickly multiple rectangles and is effective for detectingrectangles with the incomplete side and angle.2. For the searching efficiency issues of heuristic algorithm, this paper putsforward a heuristic searching algorithm base on knowledge for circles packingproblems. The absolute value of the weight matrix rows is used as heuristicinformation of circle to be placed in first roulette wheel selection, the absolute valueof the current row vector of the current placed circle is used as heuristic informationof next circle to be placed in next roulette wheel selection; Placed the next circles inthe outer of the previous circle inverse direction when placed the current circle. Theexperimental data show that the algorithm proposed can solve the layout problem ofweighted circle set, and its performance is better than the existed algorithms.