math - 用尺寸减小的数字填充网格

Question

有一个有趣的游戏，在网格中有数字，每个数字的字体逐渐变小。玩家的任务是连续点击数字。

我对为数字创建框的算法感兴趣，我想不出它的工作方式。

显然网格有 N 个数字（除了图中的 1.88），数字 1 的字体最大，字体大小依次减小。然后以某种方式将数字放置在网格上，并在它们周围增长盒子。但它似乎并不完全随机，因为有一些水平线穿过整个网格。

你知道这可能如何工作吗？

Answer 1

在我看来，这些盒子好像是通过连续划分生成的。即从整个矩形开始，放置一条分割线（水平或垂直），然后将得到的两个矩形依次细分，直到有足够的矩形供游戏使用。

这是我将尝试的第一个算法的草图。N是我想将原始矩形划分成的矩形数量，A是用于阻止小矩形变得太窄的关键纵横比。（也许A = 1.5 会是一个好的开始。）

1. 创建一个空的优先级队列并将整个矩形添加到其中。

2. 如果优先队列的长度大于或等于N，则停止。

3. 从优先级队列中删除最大的矩形R 。

4. 选择是水平分割还是垂直分割：如果它的纵横比（宽/高）大于A，则垂直分割；如果小于 1/ A，则将其水平划分，否则随机选择。

5. 决定在哪里放置分界线。（可能沿所选维度随机介于 40% 和 60% 之间。）

6. 这将R分成两个较小的矩形。将它们都添加到优先级队列中。转到第 2 步。

当这个算法完成时，队列中有N个矩形。将数字 1 放在其中最大的位置，将数字 2 放在第二大的位置，依此类推。

事实证明，将数字放入框中并不像我第一次尝试时想象的那么简单。面积度量可以很好地细分矩形，但它不适用于将数字放入框中，因为要将文本放入框，高度和宽度都必须考虑（面积不是这样）有用）。

我不会解释将数字放入框中的算法，而是给你一些 Python 示例代码，让你对其进行逆向工程！

import heapq, itertools, random 
import Image, ImageDraw, ImageFont

# ALGORITHM PARAMETERS
aspect_max = 1.5                # Above this ratio, always divide vertically
aspect_min = 1.0                # Below this ratio, always divide horizontally
div_min = 0.4                   # Minimum position for dividing line
div_max = 0.6                   # Maximum position for dividing line
digit_ratio = 0.7               # Aspect ratio of widest digit in font
label_margin = 2                # Margin around label (pixels)

class Rectangle(object):
    def __init__(self, x, y, w, h):
        self.x = x
        self.y = y
        self.w = w
        self.h = h
        self.area = self.w * self.h
        self.aspect = float(self.w) / self.h

    def __le__(self, other):
        # The sense of this comparison is inverted so we can put
        # Rectangles into a min-heap and be able to pop the largest.
        return other.area <= self.area

    def __repr__(self):
        return 'Rectangle({0.x}, {0.y}, {0.w}, {0.h})'.format(self)

    def divide(self, n):
        """
        Divide this rectangle into `n` smaller rectangles and yield
        them in order by area (largest first).
        """
        def division(l):
            return random.randrange(int(l * div_min), int(l * div_max))
        queue = [self]
        while len(queue) < n:
            r = heapq.heappop(queue)
            if (r.aspect > aspect_max 
                or r.aspect > aspect_min
                and random.random() < 0.5):
                # Vertical division
                w = division(r.w)
                heapq.heappush(queue, Rectangle(r.x, r.y, w, r.h))
                heapq.heappush(queue, Rectangle(r.x + w, r.y, r.w - w, r.h))
            else:
                # Horizontal division
                h = division(r.h)
                heapq.heappush(queue, Rectangle(r.x, r.y, r.w, h))
                heapq.heappush(queue, Rectangle(r.x, r.y + h, r.w, r.h - h))
        while queue:
            yield heapq.heappop(queue)

    def font_height(self, n):
        """
        Return the largest font height such that we can draw `n`
        digits in this rectangle.
        """
        return min(int((self.w - label_margin * 2) / (digit_ratio * n)),
                   self.h - label_margin * 2)

def draw_rectangles(rectangles, fontfile):
    """
    Create and return an Image containing `rectangles`. Label each
    rectangle with a number using the TrueType font in `fontfile`.
    """
    rectangles = list(rectangles)
    im = Image.new('RGBA', (1 + max(r.x + r.w for r in rectangles),
                            1 + max(r.y + r.h for r in rectangles)))
    draw = ImageDraw.Draw(im)
    for digits in itertools.count(1):
        rectangles = sorted(rectangles,
                            key = lambda r: r.font_height(digits),
                            reverse = True)
        i_min = 10 ** (digits - 1)
        i_max = 10 ** digits
        i_range = i_max - i_min
        for i in xrange(i_range):
            if i >= len(rectangles): return im
            r = rectangles[i]
            draw.line((r.x, r.y, r.x + r.w, r.y, r.x + r.w, r.y + r.h,
                       r.x, r.y + r.h, r.x, r.y),
                      fill = 'black', width = 1)
            label = str(i + i_min)
            font = ImageFont.truetype(fontfile, r.font_height(digits))
            lw, lh = font.getsize(label)
            draw.text((r.x + (r.w - lw) // 2, r.y + (r.h - lh) // 2),
                      label, fill = 'black', font = font)
        rectangles = rectangles[i_range:]

这是一个示例运行：

>>> R = Rectangle(0, 0, 400, 400)
>>> draw_rectangles(R.divide(30), '/Library/Fonts/Verdana.ttf').save('q10009528.png')

Answer 2

切割的模式看起来是递归的。也就是说，将区域划分为矩形的过程包括将矩形一分为二，一遍又一遍。有两个切口将整个矩形区域分开（上方和下方的水平切口1），因此我们无法判断哪个切口先出现，但我们将切口视为一种树：分开的切口1产生10了一个大矩形在它下面（20、21、4、10等），然后被 和 之间的垂直切割分割21，4包含的矩形4后来被分隔4和的切割分割14，依此类推。有 N 个切割产生 N 个区域加上一个剩余区域（“1.88”），这不是必需的，但可能会给我们一个线索。

现在我们只需要弄清楚切割的顺序，比例的选择和方向的选择。

连续的数字很少是邻居，所以看起来好像没有随着切割的进行分配数字。相反，该区域被切成矩形，矩形按大小排序，然后分配数字（注意20和21是相邻的，但它们是由分割它们之后的其他切割形成的）。

切割顺序的一个合理假设是算法总是切割最大的矩形。如果这不是真的，我们可能会看到，例如，14大于15和18合并，我看不到这样的例子。

比例...通过仔细测量，我们可以看到比例的实际分布，但我不想做那么多工作。我们没有看到很长、很细的矩形，也没有 50/50 的切割，所以我猜测算法是随机选择的，在 [0.6, 0.8] 这样的范围内。也许它试图避免使矩形非常接近已经存在的矩形的大小。在所有切割之后，选择留下的矩形（“1.88”）既不是最大的也不是最小的；也许它是随机的，也许它是第二大的，也许是别的东西——更多的例子会很有用。

方向似乎强烈倾向于在其狭窄宽度上切割矩形，而不是“纵向”。这具有产生更像正方形而不像书架上的书的矩形的效果。我能看到的唯一可能的例外是1-9切割，它可能会分割右下角数字为1纵向的块。但这取决于上方和下方的切割顺序1，因此它会导致一个假设：算法总是沿其较短的维度切割一个矩形，而1-9切割实际上是第一个。

这大概是我能做到的，没有打破尺子和计算器。