Бинарный поиск через квад-дерево

Question

У меня есть четырехугольное дерево, где листовые узлы представляют пиксели. Есть метод, который сокращает дерево квадов, и другой метод, который вычисляет число листьев, которые остались бы, если дерево должно было быть сокращено. Метод prune принимает целое число tolerance, которое используется как предел разницы между узлами, чтобы проверить, следует ли удалять или нет. В любом случае, я хочу написать функцию, которая принимает один аргумент leavesLeft. Для этого необходимо рассчитать минимальный допуск, необходимый для обеспечения того, чтобы после обрезки в дереве оставалось не более leavesLeft. Подсказка состоит в том, чтобы использовать бинарный поиск для этого. Мой вопрос заключается в том, что я не могу установить связь между бинарным поиском и этой функцией, которую мне нужно написать. Я не уверен, как это будет реализовано. Я знаю, что максимально допустимое отклонение составляет 256 * 256 * 3 = 196 608, но кроме этого я не знаю, с чего начать. Кто-нибудь может направить меня в правильном направлении?

Answer 1

Вы хотите найти квадратное дерево Ника и кривую Гильберта.

Answer 2

Скажем, вы подключили допуск = 0. Тогда вы получите экстремальный ответ, например, нулевые листья слева или все оставленные листья (не уверен, как это работает из вашего вопроса). Допустим, вы включили допуск = 196 608. Вы получите ответ на другой крайности. Вы знаете, что ответ, который вы ищете, находится где-то посередине.

Таким образом, вы добавляете номер допуска на полпути между 0 и 196 608: допуск 98 304. Если число оставленных листьев слишком велико, то вы знаете, что правильный допуск находится где-то между 0 и 98,304; если оно слишком низкое, правильный допуск находится где-то между 98 304 и 196 608. (Или, может быть, верхние / нижние части поменялись местами; я не уверен из вашего вопроса.)

Это бинарный поиск. Вы продолжаете сокращать диапазон возможных значений пополам, проверяя одно в середине. В конце концов вы сузите его до правильного допуска. Конечно, вам нужно искать бинарный поиск, чтобы правильно его реализовать.

Answer 3

1. Напишите метод, который просто пробует все возможные значения допусков и проверяет, оставит ли это точно достаточно узлов.
2. Напишите тестовый пример и посмотрите, работает ли он.
3. Не делайтеШаг 1. Используйте бинарный поиск по всем возможным значениям допуска, чтобы сделать то же, что и на шаге 1, но быстрее.

Если вы не знаете, как реализовать бинарный поиск, попробуйте лучшесначала это простой целочисленный массив.В любом случае, если вы выполните шаг 1, просто сохраните количество листьев, оставленных в массиве (с допуском в качестве индекса).А затем выполните бинарный поиск по этому вопросу.Чтобы превратить это в шаг 3, обратите внимание, что вам не нужен весь массив.Просто замените массив функцией, которая вычисляет значения, и все готово.