algorithm - 如何构建连续值之间具有最大平均距离的阈值图？

Question

我有一个预生成的 2D 点云，例如:

假设网格包含 64 个点。对于每个点，我想在 [0,63] 范围内分配一个值，这样:

• 没有已分配值的点(简单)
• 对于具有给定值的给定点，连续数字之间的平均距离尽可能大，并确保表格在边缘“环绕”

基本上，它与应用于 Bayer Matrix 的算法相同, 除了我的点不在轴对齐的网格中。

Arbitrary size threshold maps can be devised with a simple rule: First fill each slot with a successive integers. Then reorder them such that the average distance between two successive numbers in the map is as large as possible, ensuring that the table "wraps" around at edges.

我试图搜索生成两个矩阵的非幂的算法，但没有找到任何相关算法。

如何实现才能满足第二个条件？

编辑 1:

云中的点计数不是二的幂!

编辑 2:

这是结果，如您所见，某些范围似乎是轴对齐分布的，如果我只想使用某些范围，这对我来说并不是真正有效的。

我会尝试找到一种方法来添加一些抖动。你有什么技巧可以实现吗？

范围 [0,0.1][ ] 3

范围 [0.1,0.2][ ] 4

范围 [0.8, 0.9][ ] 5

范围 [0, 1][ ] 6

Answer 1

给定 4^k 个不在网格中的点，您可以将它们分配给 2^k x 2^k 网格中的点，然后用拜耳矩阵中的关联值标记每个点。分配过程类似于 k-d tree 的构造.您将点集划分为大小相等的子集，其中一个子集完全位于另一个子集的左侧。左子集中点的 x 坐标以二进制表示从 0 开始；右侧子集中点的 x 坐标从 1 开始。然后递归地用 y 坐标分割每个子集，确定网格中 y 坐标的第一位。然后对子集进行递归调用以找到其余位。

Python代码:

import operator


def threshold_map_recursive(points, base, increment, result):
    if len(points) == 0:
        return
    if len(points) == 1:
        result[points[0]] = base
        return
    n3, r = divmod(len(points), 4)
    n0 = n3 + (r > 0)
    n2 = n3 + (r > 2)
    points.sort(key=operator.itemgetter(0))
    left = points[: n0 + n3]
    left.sort(key=operator.itemgetter(1))
    threshold_map_recursive(left[:n0], base, 4 * increment, result)
    threshold_map_recursive(left[n0:], base + 3 * increment, 4 * increment, result)
    right = points[n0 + n3 :]
    right.sort(key=operator.itemgetter(1))
    threshold_map_recursive(right[:n2], base + 2 * increment, 4 * increment, result)
    threshold_map_recursive(right[n2:], base + increment, 4 * increment, result)


def threshold_map(points):
    result = {}
    threshold_map_recursive(list(points), 0, 1, result)
    return result


def test(n, m):
    tm = threshold_map((x, y) for x in range(n) for y in range(m))
    for k in range(1, n * m):
        for y in range(m):
            print("".join("@" if tm[x, y] < k else "." for x in range(n)))
        print()


test(5, 5)