Geek Answers Handbook

Break a square or rectangle into a large number of squares or rectangles of arbitrary size

I am trying to split a square or rectangle into a large number of squares or rectangles of arbitrary size so that none of them overlap.

Well, of course, others asked about this, the best thread I found How to fill a square with smaller squares / rectangles?

The solution looks like either through bin packaging or some kind of tree map.

But what I'm looking for is the actual algorithm in Java, Javacript, actionscript, or even C.

+4
source share
3 answers

The code provided creates a kd tree. You can use this to draw lines on your rectangle that would divide it into smaller rectangles. After you get your tree, you can use it as follows to divide the area into these rectangles:

  • Select a node in the root of the tree.
  • Draw a vertical line through this point.
  • Select the left child, draw a horizontal line through this point on the left side of the line that you just drew through the parent (this line stops at the line you just drew).
  • Choose the right child, draw a horizontal line through this point on the right side of the line that you just drew through it the parent (this line also stops on the line that you drew through the parent).
  • Do this recursively by going between the vertical and horizontal lines at each level of the tree.

code:

int MAX_HEIGHT = 100; int MAX_WIDTH = 100; int NUM_POINTS = 6; // Generate random list of points List<Point> pointList = new List<Point>(); Random rand = new Random(); for(int i = 0; i < NUM_POINTS ; i++) { pointList.add(new Point(rand.nextInt(MAX_HEIGHT), rand.nextInt(MAX_WIDTH)); } BinaryTree tree = CreateKDTree(pointList, 0); // Recursive function for creating a KD Tree from a list of points // This tree can be used to draw lines that divide the space up // into rectangles. public BinaryTree CreateKDTree(List<Point> pointList, int depth) { // Have to create the PointComparator class that just selects the // specified coordinate and sorts based on that Coordinate coord= depth % 2 == 0 ? X_COORDINATE : Y_COORDINATE Collections.sort(pointList, new PointComparator(coord)); int median = pointList.size() / 2; // unfortunately Java doesn't have a BinaryTree structure so // you have to create this too BinaryTree node = new BinaryTree(pointList[median]); if(pointList.size() == 1) return node; if(median > 0) node.left(CreateKDTree(pointList.subList(0, median), depth + 1); if(median + 1 < subList.size()) node.right(CreateKDTree(pointList.subList(median + 1, subList.size()), depth + 1); return node; }
+1
source

The solution is to try using the "Divide and Conquer" method. In iteration 1, you have a rectangle. Divide the rectangle into two smaller ones. The way to do this is as follows. Assume that the rectangle is 100x50. Choose a random number between 0-100 (rectangle length). Let's say the random number is 20. Then you can spit out the rectangle with two smaller sizes 20x50 and 80x50. The same procedure is applied recursively for these two new rectangles (therefore, at iteration 2 you will have 4 rectangles). Do it n -times and you will have 2 ^ n rectangles. Also, at each iteration, you can randomly choose whether to spit along the length (vertical) or width (horizontal) of each rectangle.

hope this helps!

+4
source

Randomly divide the length into x parts

Now arbitrarily split each smaller rectangle into separate parts

Here is some ActionScript code (written in notepad, you will need to check for errors). It takes the width and height of the input rectangle and returns an array with the vertices of the divided rectangles

 private function divRect(w:Number, h:Number):Array { var rw:Number=0, rh:Number=0; var wa:Array=[0], rv:Array=[]; while(rw < w) { var r:Number=Math.random() * (w-rw); wa.push(r+rw); rw+=r; } for(var i:int=1; i<wa.length; i++) { while(rh < h) { var o:Object={x: wa[i-1], x2: wa[i]}; var s:Number=Math.random() * (h-rh); oy=rh; rh+=s; o.y2=rh; rv.push(o); } } }
+1
source

More articles:


All Articles