Monte-Carlo

[ieroglif]

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

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

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

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

не понял. варианты: игровые действия, распознование объектов. =)

[Igors]

я бы завёл :
1. "превьюшку" (тут всё ясно)
2. QMap<QColor,int> в котором бы хранились площади каждого цвета ( == каждого квадрата).
...

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

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

не понял. варианты: игровые действия, распознование объектов. =)

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

[ieroglif]

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

[Igors]

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

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

[Mityai]

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

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

[Igors]

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

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

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

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

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

[ieroglif]

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

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

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

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

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

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

[Mityai]

Проблема в другом - как бы точно мы площади пересекаемых квадратов ни оценили (пусть даже идеально, аналитически) все равно попавших квадратов может быть мало. А тест вкл/выкл выполняется (предвычислен) для каждого квадрата. Если у нас 2-3 теста вкл/выкл для круга...

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

[Igors]

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

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

[Igors]

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

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

[Mityai]

ieroglif по существу предложил вернуться к исходному имеджу. Конечно это будет работать но уж очень медленно/уныло 

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

[Igors]

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

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

[Mityai]

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

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