Как построить карту порогов с максимальным средним расстоянием между последовательными значениями? - PullRequest
Новая
       29

Как построить карту порогов с максимальным средним расстоянием между последовательными значениями?

2 голосов
/ 02 октября 2019

У меня есть предварительно сгенерированное облако 2D-точек, например: enter image description here

Допустим, сетка содержит 64 точки. Каждой точке я бы хотел присвоить значение в диапазоне [0,63], чтобы:

  • не было точек с уже назначенным значением (просто)
  • дляДля заданной точки с заданным значением среднее расстояние между последовательными числами должно быть как можно больше И обеспечить, чтобы таблица «свернулась» по краям

По сути, это тот же алгоритм, который применяется к Матрица Байера , за исключением того, что мои точки не находятся в сетке, ориентированной по оси.

Карты порогов произвольного размера можно разработать с помощью простого правила: сначала заполните каждый слот последовательными целыми числами,Затем переупорядочьте их так, чтобы среднее расстояние между двумя последовательными числами на карте было как можно большим, гарантируя, что таблица «оборачивается» по краям.

Я пытался найти алгоритм для генерации неСила двух матриц, но я не нашел никакого соответствующего алгоритма.

Как мне достичь, чтобы удовлетворить вторым условиям?

РЕДАКТИРОВАТЬ 1:

Количество точек в облаке не является степенью двойки!

РЕДАКТИРОВАТЬ 2:

Вот результат, поскольку вы можете видеть, что некоторый диапазон, кажется, выровнен по осираспределено, и это не совсем верно для меня, если я хочу использовать только некоторые диапазоны.

Я попытаюсь найти способ добавить немного дрожания. Есть ли у вас какие-либо советы для достижения этого?

Диапазон [0,0,1] [enter image description here]] 3

Диапазон [0,1,0,2] [enter image description here] 4

Диапазон [0,8, 0,9] [enter image description here] 5

Диапазон [0, 1] [enter image description here] 6

1 Ответ

1 голос
/ 02 октября 2019

Учитывая, что 4 ^ k точек отсутствуют в сетке, вы можете назначить их точкам в сетке 2 ^ k на 2 ^ k, а затем пометить каждую точку соответствующим значением в матрице Байера. Процесс назначения напоминает построение дерева kd . Вы разделяете набор точек на подмножества одинакового размера, где одно подмножество находится полностью слева от другого. Координаты 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)
...