Построение квадри

Question

Я пытаюсь использовать quadtree (4-арное дерево) для хранения информации в данном BMP.
Я изо всех сил пытаюсь выяснить, как построить дерево, учитывая любой BMP.

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

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

Это на C ++, и в настоящее время мой файл quadtree.h содержит корень Node *, где узел определяется как структура с пиксельным элементом и 4 указателями на другие узлы. Каждый внутренний узел (неконечный узел) должен содержать среднее значение всех 4 значений RGB, к которым он приводит.

Я пытаюсь создать алгоритм, но думаю, что мне может понадобиться включить в файл .h одну или две структуры. Есть ли лучший / более чистый способ решения этой проблемы?

Answer 1

хорошо, в зависимости от того, как хранятся ваши растровые данные, вы можете делать что-то по-другому. Вы читаете это из файла и бросаете прямо в дерево? Если это так, файлы .BMP (если я правильно помню) сообщают вам их ширину и высоту прямо вверху, так что вы можете использовать их для точного определения количества уровней, которые могут вам помочь.

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

Если вы не хотите делать это в массиве, самое простое, на мой взгляд, было бы, чтобы каждый узел отслеживал свои координаты x, y. Это позволит вам сделать то же самое, что и с массивом, но вы не просто подключите индексы.

Это полезно? Как вы храните растровые изображения? Какова конечная цель?

Answer 2

STANN - лучшая на данный момент реализация с открытым исходным кодом.

http://sites.google.com/a/compgeom.com/stann/

Поговорите с мудрыми, используйте алгоритм построения квадродерева Берна и др. И воздержитесь от фанк-операций с деревьями.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf

1. Сортируйте все свои очки в порядке следования.
2. Рассчитать длину квадродерева между каждой парой последовательных точек.
3. Выполните вычисление всех ближайших наибольших значений, чтобы найти родителей / братьев и сестер.

Я сейчас занимаюсь разработкой библиотеки для OpenCl. Я опубликую ссылку, как только закончу тестирование.