将一个正方形或长方形分解为大量随机大小的正方形或长方形

Question

我试图将一个正方形或矩形分解为大量随机大小的正方形或矩形，以便没有一个重叠。

好吧，当然其他人问过这个问题，我发现的最好的帖子是 如何用较小的正方形/矩形填充正方形？

解决方案似乎是通过装箱或某种树形图。

但我正在寻找的是 Java、Javacript、actionscript 甚至 C 中的实际算法。

Answer 1

提供的代码创建一个kd 树。您可以使用它在矩形上绘制线条，将其分成更小的矩形。获得树后，您可以按如下方式使用它来将区域划分为这些矩形：

1. 选择树根处的节点。
2. 通过该点画一条垂直线。
3. 选择它的左子项，在您刚刚通过其父项绘制的线的左侧通过该点绘制一条水平线（这条线在您刚刚绘制的线处停止）。
4. 选择它的右子项，在您刚刚通过其父级绘制的线的右侧通过该点绘制一条水平线（这条线也停在您通过父级绘制的线处）。
5. 递归地执行此操作，在树的每一层的垂直线和水平线之间切换。

代码：

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 K-D 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; 
}