Research On Circle Packing And Image Dot Painting Problems

Circle packing problem refers to given a set of circles,including the size and numbers of them,and given the shape of a container,we need to calculate the smallest volume of the container under the constraint that the circles can't overlap with each other and with the container border.This is a NP-hard problem,in other words,we can't solve it in deterministic polynomial time.Circle dot painting problem refers to given an image,we need to get a dot painting result based on the features and colors of the image.We need to put the circle dots with proper color and size in proper location,the arrangement of dots needs to reflect the feature and the color needs to reflect the image color.This paper presents a circle packing algorithm in which improves the domain partitions based on power diagram,and discusses the circle dot painting problem on image.This paper presents a circle packing algorithm which converges faster by improving the domain partitions based on power diagram.By setting the area of the container fixed,we firstly shrank the input circles so that they wouldn't overlap when scattered randomly in the container.Secondly,we triangulated the circle center points by regular triangulation,and divided the container area into sub-regions according to the radius ratio of adjacent circles.And then all circles grew by the same ratio within their own regions.By repeating the"partition-and-grow" operations,we finally got the packing result.Besides,this paper does some research on image circle dot painting.Firstly,we segment the image and extract the outline of the segmented image and then get the feature outline of the input image,generate the orientation field on the image,which makes sure that there exists a direction value at the location of each pixel to guide the dot arrangement.Next,we designed a function to reflect how the dot size changes as the gradient of the image changes.At last,we start to put circles in the image region based on the orientation field and the function mentioned above,and the algorithm ends when the domain of image is filled with dots.Besides,we fill the hole left to make the results better.Experimental results show that the improved domain partition algorithm for circle packing can converge more quickly than the algorithm based on power diagram and usually we can get better packing results.And the circle dot painting algorithm can generate proper results reflecting the features and colors of input image.