Circle Group Packing Algorithm For Mosaic Synthesis

This thesis proposes a solution to the irregular tiles packing problem based on circle group approximation algorithm,and applies it to simulating Opus Palladium mosaics.A group of circles is obtained which approximates the outline of a polygon from inside by means of the straight skeleton of the polygon.In a closed plane region,the blue noise sampling algorithm is used to optimize the initial positions of the circle groups,and the Power Diagram for the circle groups is constructed.A relaxation method is used to maximize each circle group in its corresponding closed power region.By continuously iteratively generating power diagrams and optimizing circle groups,we obtain a compact configuration of tiles.Inspired by the solution for the irregular tile packing problem,this thesis proposes a solution for the three-dimensional packing problem based on a sphere group approximation algorithm.By means of the medial surface of a object,sphere group that approximates the outline of the object from inside is generated.The Lloyd’s algorithm is used to optimize the initial distribution of sphere groups in a three-dimensional container.A power diagram is constructed for the sphere groups.Power diagrams and sphere groups are alternately optimized to obtain a compact configuration of three-dimensional objects.Extensive experiments have shown that the solution of the irregular tiles packing problem proposed in this thesis improves the coverage rate of the tiles,effectively reduces the execution time and enhances the robustness of the algorithm.The mosaic simulation method is applied to the generation of photo collage.The solution of three-dimensional packing problem based on sphere group approximation algorithm proposed can solve three-dimensional packing problem with regular and irregular shapes.It could adapt to different tiles shapes and generate compact packing results.The robustness and effectiveness of the algorithm are demonstrated in this thesis.