Структуры данных для поиска

[Igors]

..соответственно выравнивается по 4 байта и имеет вполне съедобную структуру, при прямом обращении к памяти скорость просто шикарна.

Тебе нужны LODы? Ну так сделай пару лодов, и выбирай их в зависимости от необходимой точности.

Спасибо конечно, но давайте не тратить время на обсуждение как упростить и/или изменить постановку задачи. Если бы такая возможность у меня была - я бы ее охотно использовал. Мне нужен (быстрый) поиск а не тупой перебор.

Память брать можно. Сейчас пиксель под 100 байт, может будет больше, ничего, переживу, это мои проблемы.

[m_ax]

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

1) По всем - это вообще по всем 10^6 или по маркерованным?
2)  для каждого смотрим маркированных ближайших соседей. В смысле?
3) Допустим все они оказались одного (или близкого) цвета. Кто они? Ближайшие маркированные соседи или просто ближайшие соседи?
4) Все хорошо, пошли дальше. Если нет - надо маркировать новый пиксель. Какой именно?
5) Это изменит расклад как для последующих так и для предыдущих - теперь новая точка может оказаться ближайшей вместо старой.  Этого я вообще не понимаю..

Какая то запутанная логика(

Можно на каком нить миниатюрном примере: Что вначале было и что в конце должно быть?

[V1KT0P]

Спасибо конечно, но давайте не тратить время на обсуждение как упростить и/или изменить постановку задачи. Если бы такая возможность у меня была - я бы ее охотно использовал. Мне нужен (быстрый) поиск а не тупой перебор.

Пока подробнее какие именно пиксели надо искать не напишешь, врятли получишь ответ.
Это тоже самое что спросить какой лучше алгоритм сжатия использовать, не объяснив какие данные необходимо сжать. Может это текст(PPMD), звук(flac), бинарные файлы(upx) и т.д.

[QuAzI]

По сабжу - ну будет там скучная собственная структурка, в которой будет три переменных: вертикаль, горизонталь, цвет пихеля. Дёшево и сердито. Никаких деревьев и прочих плясок с бубнами. И в итоге всё равно получается "тупой перебор". Выигрыша от "распоточить", не будет, там же не рассчёты, а тупой поиск в примерно одной области памяти, больше затраты будут на поддержку "многопоточности" и сохранение атомарности для списка, в который структурка пишется.

[Igors]

Псевдокод

Код

C++ (Qt)
bool ValidatePixel( const CPixel & target, const std::vector <CPixel *> & markedNeighbours )
 

Аргументы

- target - немаркированный пиксель подлежащий проверке
- markedNeighbours - вектор всех маркированных пикселей которые влияют на target (т.е. target лежит внутри круга захвата для каждого элемента вектора)

Возвращаемое значение: true если с target'ом "все хорошо" и баланс достигнут. Иначе false

Что значит "все хорошо"? Здесь уже используется масса вариантов, некоторые из них отпадут, новые добавятся. По существу это еще одна (другая) задача. Простейший пример: вычисляем средний цвет по всем markedNeighbours и сравниваем его с цветом target. Разница не превышает заданный порог - вернули true, иначе false. Наша тема - поиск, и с этой точки зрения нам важно только одно - изменился вектор источников - валидность пикселя возможно изменилась. Расчет закончен если для всех немаркированных пикселей ValidatePixel вернула true.

[m_ax]

А в чём проблема то? Всё равно ж тогда по всем не маркированным пикселям нужно пробежаться.. 

[Igors]

А в чём проблема то? Всё равно ж тогда по всем не маркированным пикселям нужно пробежаться.. 

А проблемы такие

1) Пробегаясь для каждого немаркированного надо как-то собрать маркированных соседей

2) Это в первый раз по всем. Потом маркируя пиксель мы можем получить изменение расклада соседей в относительно небольшой окрестности и лупить по новой весь мульон раз за разом выглядит глупо.

[m_ax]

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

По первому пункту: не понятно, что значит: надо как то собрать маркированных соседей? 

[Igors]

По первому пункту: не понятно, что значит: надо как то собрать маркированных соседей? 

Ну тот вектор markedNeighbours (пост #19) надо же как-то получить, он ведь разный для каждого проверяемого

[m_ax]

Ну тот вектор markedNeighbours (пост #19) надо же как-то получить, он ведь разный для каждого проверяемого

Ну так модифицируйте его при каждом проходе.. 

[Tonal]

Вроде как напрашивается граф: к маркированной точке приделываем список ближайших маркированных точек с расстояниями.
Далее проверяем только их - обход графа в ширину.

[Igors]

А чего это мы так отчаянно (и неумело) велосипедим?  Может это... стоит открыть книжки?