Monte-Carlo

[Igors]

Добрый день

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

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

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

- для каждого квадрата вызывается ф-ция

Код:

bool Test(float x, float y);

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

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

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

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

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

Спасибо 

[Sancho_s_rancho]

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

[Sancho_s_rancho]

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

[Sancho_s_rancho]

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

[m_ax]

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

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

[Igors]

К примеру 3 квадрата входят в него полностью, а один на треть.

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

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

[ieroglif]

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

[Sancho_s_rancho]

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

[Igors]

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

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

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

Представьте напр. такое изложение

"Есть имедж наложенный сферически (light environment). На основании данных имеджа сфера разделена на телесные углы. А еще имедж может быть cubic map тогда.. и.т.д  и.т.п. (еще 5 страниц текста)"

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

[Igors]

по моему пониманию, ситуация следующая:
есть оуеть каких размером Image. (ну пусть 10к на 10к точек). кажому пикселю мы по какому-то божъему проведению назначили его число и назвали энергией.

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

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

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

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

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

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

[ieroglif]

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

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

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

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

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

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

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

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

[Igors]

а) откуда "вновь созданные квадраты"? квадраты твои. энергию ты для них уже расчитываешь.

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

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

Ага

Если бы это было летом, если бы у нас был доберман-пинчер..

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

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

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

[ieroglif]

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

[ieroglif]

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

[Igors]

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

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

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