Russian Qt Forum

Добрый день

Исходные данные: изначально есть имедж (картинка), каждый пиксель описывается float числом, которое может принимать любые неотрицательные значения (не только от 0 до 1). Имедж замещается упрощенной моделью данных:

- имедж разбивается на заданное число квадратов (обычно 200-1000).

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

- для каждого квадрата вызывается ф-ция которая принимает x. y  - центр квадрата в координатах имеджа и возвращает булеское значение - квадрат включен или выключен.

- запоминаем массив квадратов (для каждого координаты + энергия + флаг вкл/выкл). удаляем исходный имедж, он больше не нужен.

Обработка запросов: дается круг с центром и радиусом в координатах имеджа. Необходимо определить (приближенно) какая энергия находится внутри круга (с учетом того что некоторые квадраты могут быть выкл). Решается легко и приятно: для каждого включенного квадрата выбрасываем N случайных точек внутри него. Для каждой из N точек проверяем находится ли она внутри круга. Если да - добавляем энергию. Напр. N = 4. только одна из точек квадрата внутри круга. Значит к энергии круга добавляем энергию квадрата / 4

Проблема:Все работает хорошо пока круг достаточно велик и покрывает достаточно много квадратов. А вот с малым радиусом данных не хватает и результат получается "рваным". Можно увеличить N (число самплов Monte-Carlo) или даже находить площадь пересечения аналитически - но это ничего не дает, сами квадраты слишком велики.

Предлагается для обработки кругов назначить дополнительное число проверок. Допустим я раскидал в круге заданное число точек К. Для каждой я вызываю ф-цию Test и определить, активна ли точка. Я могу также определить в какой из квадратов попадает точка. А вот что делать дальше - не соображу :) Нужна энергия покрываемая кругом, а как ее посчитать?

Спасибо 

Не распарсил ваш поток сознания. Может картинку нарисуете?
п.с. Я серьезно, первая половина алгоритма понятна, а вторая - нет

Момент про выбрасывание случайных точек вообще загадка для меня. У нас есть некий радиус. К примеру 3 квадрата входят в него полностью, а один на треть. Проверяем включены ли квадраты. Допустим все включены. Тогда энергия1 + энергия2 + 0,3 энергия3. Зачем какие-то точки трогать?

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

Мне это навеяло тему про клеточные автоматы)) Как-то пришлось в универе писать))

Тож не совсем понятна логика и сама формулировка проблемы..
Можно поподробней?))

А как Вы определите что на треть? Будете высчитывать площадь пересечения прямоугольника с кругом? Это длинно и не подходит в др. вариантах (напр. если имедж налагается сферически или как "probe"). Куда проще выбросить N точек внутри квадрата и посчитать сколько из них попало в круг (вычисление площади методом Monte-Carlo)

Пример приаттачил. На расквантованном имедже квадраты показаны малиновым, их центры - желтыми точками.  Нужно вычислить энергию покрываемую красным кружком. Видно, что он пересекает всего 2 квадрата, которые могут быть вкл/выкл - результат слишком грубый, как бы точно ни были посчитаны площади. Хорошо, давайте возьмем еще 20 (назначается пользователем) тестов вкл/выкл - уже внутри круга, но зато посчитаем точнее. Но как эти тесты сопоставить с энергией?

по моему пониманию, ситуация следующая:
есть оуеть каких размером Image. (ну пусть 10к на 10к точек). кажому пикселю мы по какому-то божъему проведению назначили его число и назвали энергией.
на этот image мы кидаем кружок в любое место/любых размеров. и нам надо посчитать сколько энергии этот кружок закрыл.
что бы не париться с обсчётом такого количества данных (а может просто интереса ради) мы не будем держать всё это немерянное количество "энергопикселей", а упростим задачу, разбив исходную картинку сеткой квадратов по собственному желанию.
для каждого квадрата мы считаем его общую "ёмкость", его положение, назвначаем этот квадрат включеным или выключеным и исходную картинку посылаем в Пакистан (что бы память нам тут не занимала).
Получили 200-1000 элементов данных, которые обсчитываются уже достаточно быстро, но столкнулись с проблемой:
Если круг у нас получился меньше минимального квадрата сетки, или боле-менее с ним соизмерим, то залезая в квадрат сетки маленьким краешком мы докидываем в суммарную "энергию" слишком большое число и результат нас не устраивает.
Вопрос - кто виноват и что делать? :)
лично я бы, наверное, постарался сделать так:
1. находим все квадраты на которые лег круг. наверное так:
1.0. работаем не с кругом, а с квадратом, описывающим этот круг.
1.1. находим квадрат лево-верх
1.2. находим квадрат право-низ.
1.3. немного думаем и в итоге высчитываем с погрешностью в большую сторону квадраты на которые у нас "лёг" круг. пусть мы захватим не существующие (на углах), но они отметутся потом.
2. разбиваем КРУГ сеткой из получившихся в п.1 квадратов. тупо аналитически. в результате мы получим круг, "разрезаный" на куски.
3. той же аналитикой находим площади получившихся кусков.
4. после этого мы чётко знаем квадраты в которых лежат куски, знаем площади, которые занимают куски в этих квадратах - не сложно от каждого квадрата взять по нужной доле "энергии".
5. при ситуации, что наш круг находится внутри одного квадрата - проблема так же отпадает.

Начальная задача была про квадраты, а тут я вижу прямоугольники. Это немного разные вещи. Про сферическое изображение не понял вообще. Мы говорили про 2d матрицу и тут внезапно переходим к 3d.

На жаль бананiв нема  :)

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

Имеджи как правило скромные (типа 2к х 1к) и расход памяти не проблема. Ключевой момент: нам нужен Test (определение вкл/выкл) а вызов этой ф-ции операция дорогостоящая, поэтому нам нечего делать на уровне пикселей.

Разумно, но неясны моменты

a) как посчитать энергию вновь созданных квадратов?

b) реализация "лево-верх, право-низ" и.т.п. быстро превратится в "ловлю блох" т.е. написание длинного, сложного но неэффективного алгоритма. Нужно что-то проще

с) существующий метод совсем неплох. Напр. если поместить кружок там где квадраты натыканы густо - все хорошо. Как совместить это с новым методом?

а) откуда "вновь созданные квадраты"? квадраты твои. энергию ты для них уже расчитываешь.
b) не согласен.
имеем: Cx,Cy,Cr - данные круга. позиция центра и радиус.
соответсвенно находим левый верхний квадрат: точка Cx-Cr,Cy-Сr будет указывать на нужный квадрат. правый нижний Cx+Cr,Cy+Cr.
после этого находим все квадраты которые будут перекрываться этим прямоугольником.
Согласен, при текущем разбиении имаджа это будет крайне не удобно.
Поэтому я бы предложил разбивать его равной сеткой по размеру минимального квадратика.
тогда получить квадраты от левого верхнего, до правого нижнего - дело 5и копеек =)

Кстати, откуда вообще такое разбиение? Оно статическое? Или должно генериться динамически да ещё и постоянно?

c) ну, лично я бы просто разбивал бы всегда квадратной сеткой, а юзверю бы позволял только задавать размер этой сетки - тогда всё будет хорошо

Каким образом?

Ага(Если бы мне дали такую задачу которую мне легко делать... :)

Статическое, выполняется один раз на старте, затем интенсивно используется. Разбиение выполняется адаптивно - меньшие квадраты для областей с большей энергией и наоборот, так чтобы энергии квадратов были примерно одинаковы. Разбивка используется для многих целей, вычисление "что попало в круг" лишь одна из них.

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

upd: тем более что смотреть надо будет не все площади,а только прямоугольник описаный вокруг круга.

Ну почему "тупо"?  :) Нормальное "численное решение". Вот как бы его сделать чтобы поменьше париться с пикселями и.т.п. И по-хозяйски экономно с вычислениями - ведь возможны ситуации когда дополнительные тесты вкл/выкл не требуются

Кстати: а понятно чему соответствует круг (для чего он в задаче)?

я бы завёл :
1. "превьюшку" (тут всё ясно)
2. QMap<QColor,int> в котором бы хранились площади каждого цвета ( == каждого квадрата).
и то и другое я бы обсчитывал при каждом изменении разбиения.. в целом, процесс не сложный.
3. при появлении круга я бы его рисовал на "картинке" таких же размеров как и "превьюшка", в результате чего у меня бы были две картинки - одна из разноцветных квадратиков, другая "белая" (или любого другого одного цвета) с "красным" (ну или каким ты его цветом рисуешь) кружком.
4. цикл по прямоугольнику в который вписан этот "круг".
заводим ещё один QMap<QColor,int> square;
если цвет точки не белый - square[ QColor(превьюшка,i,j) ]++;
таким образом мы чётко получим - какие цвета и сколько пикселей у нас перекрыты кругом.
ну а после этого всё примитивно :)
не понял. варианты: игровые действия, распознование объектов. =)

Все понятно но громоздко и (увы) медленно. Надо искать лучшее решение

Нет, все раз в 10 проще, это посвящено очень популярному/известному атрибуту (свойству материала) в 3D, Вы его 100 раз видели и прекрасно знаете. Просто подумайте немного, а не хотите - скажу ответ  :) 

хм....
а что, нету разве готовых алгоритмор расчётов освещённостей? честно говоря - не верю.
или в чём прикол? :)

Не пытаюсь я никого приколоть, ладно, проехали  :)

Igors, может я что и неправильно понял, но вот пришла в голову такая идея. Если бред, сильно не бить :)

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

Не буду, это не та задача, ответ на которую есть в Assistant. Обычно решение находится после многих проб (и ошибок), это нормально

Проходим по всем квадратам (мне все равно это надо делать). Для каждого квадрата легко определить может ли он вообще пересечь круг. Не может - пошли дальше. Может - накидываем в квадрат "достаточно много" точек и смотрим сколько из них внутри круга. В этом прелесть Monte-Carlo - все расчеты получаются очень простыми.

Проблема в другом - как бы точно мы площади пересекаемых квадратов ни оценили (пусть даже идеально, аналитически) все равно попавших квадратов может быть мало. А тест вкл/выкл выполняется (предвычислен) для каждого квадрата. Если у нас 2-3 теста вкл/выкл для круга - результат грубый/рваный. Поэтому при нехватке данных надо как-то (не знаю как) создать N новых, меньших квадратов уже внутри круга и каждый из них прощупать на вкл/выкл. Но как это сделать? ieroglif по существу предложил вернуться к исходному имеджу. Конечно это будет работать но уж очень медленно/уныло  :)

честно говоря я не вижу медленности моего метода.
мне кажется что он будет работать быстрее не смотря на то, что там пробегается средний цикл по квадрату пикселей описаный вокруг круга и маленький цикл по высчитыванию энергии круга из уже составленной "карты объёмов цветов" составляющей этот круг.

а ещё подумал что так же можно составлять просто массив двухмерный по размеру картинки, но держать там int номер квадрата.
в общем всё получается быстро
1. цикл по двухмерному массиву "пикселей". если точка входит в круг, то увеличиваем на единичку QHash<int номерКвадрата,int числоПопаданий>
2. цикл по получившемуся QHash где мы суммируем результирующую энергию круга сравнивая значение с заранее составленным QHash<int номерКвадрата,int количествоПикселейКвадрата> и вычисляем энергию круга в этом квадрате учитывая так же заранее составленный QHash<int номерКвадрата,qint64 энергияКвадрата>.

в общем, мне пока кажется этот метод достаточно быстрым.
аль не катит? задачи более серъёзные?

так и чего сложного медленного и унылого? ;)

upd: а ещё я подумал - раз уж нам не так важна точность, то что мешает бежать первый цикл с шагами, скажем, не i,j++ а, к примеру, i,j+=3.
с учётотом того что это у нас круг вписаный в квадрат - мы получим достаточно чёткую результирующую картину значительно ускорив цикл.
или вообще высчитывать шаг как-то отдельно в зависимости от размера радиуса круга?, что бы к примеру, брать всегда 100 равномерно распределённых точек по этому квадрату?

в общем, тот же метод монте карло, просто применяется не к квадратам разбивки картинки, вычисляя - вошла ли точка в круг а к квадрату описанному вокруг окружности, вычисляя - какой квадрат вошёл в круг? :)

А можно поподробнее насчет теста вкл/выкл? В чем он заключается? :)

"Излучающий" имедж разбивается один раз и используется для расчета освещенности в каждой точке. Однако часть света может быть перекрыта др. объектами в сцене (тень упала, зайца убила). Поэтому расчет в точке начинается с (дорогостоящей) проверки каждого квадрата на активность. "Если нет переркытия точка - центр квадрата - включен, иначе выключен"

Хммм.. сумбурно но интересно  :)  Попытаемся связать это с имеющейся схемой. Может лучше не работать  с 2 раскладками (что весьма хлопотно) а сделать имеющуюся раскладку в виде дерева. Артефакты возникают в местах где квадраты велики, значит у больших квадратов надо создать (предрасчитать) child квадраты (возможно несколько уровней). Если круг велик, самплим квадраты верхнего уровня, иначе спускаемся. Тоже конечно не блещет простотой, но как-то приличнее  :)

А нам обязательно возвращаться к полному исходному имеджу? Если прикинуть по центрам возле каких квадратов может быть кружочек и оставить только кусок изображения? Или так алгоритм проверки вкл/выкл не катит?

Тест вкл/выкл (сам по себе) катит всегда. Можно вообще выбросить N точек для тестов внутри круга. Но как узнать какая часть энергии выключается каждым тестом? Придется делать разбиение вырезанного куска, а он может быть велик. И делать это надо для каждой точки а не раз. Впрочем так и получаются наукообразные расчеты которые длятся сутками  :)

А если один раз прогонять Монте-Карло, а дальше для энергии брать что-то иное? Мы ведь в общем-то можем применить этот алгоритм только с целью поиска возможных пересечений? Насколько четко он вообще определяет эти вещи в случаях "большой квадрат и маленький круг"? А после того, как вырезали область, уже для нее гнать что-то целочисленное и более медленное - делить квадраты, считать площади и тому подобное.