Obscured Monte-Carlo

[Igors]

Добрый день

Большая и старая задача которую я (увы) пока не решил. В тему призываются научные работники (хотя надежд не питаю - заняты кушанием синтаксического сахара).

Есть круг радиуса R внутри которого N случайных точек. Требуется оценить плотность в центре круга, в простейшем случае это

d = N / (Pi * R * R)

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

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

b) Искать/гуглить теорию. Хорошо бы конечно, но где ее взять? Гуглить просто "Monte-Carlo" точно безнадюга, "стрельба по площадям". Есть правда Cluster(ed) Monte-Carlo, глянул неск статей но не пойму о чем там речь и чему это посвящено.

Что посоветуете?

Спасибо

[ssoft]

Есть круг радиуса R внутри которого N случайных точек. Требуется оценить плотность в центре круга ...

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

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

Я бы  построил триангуляцию Делоне и удалил ребра, которые больше заданного критерия (например, в 1.5 раза больше ребра для равносторонних треугольников при равномерном заполнении всего круга).
Для оставшихся треугольников рассчитал их площадь. Ну и среднюю плотность точек.

[Igors]

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

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

Я бы  построил триангуляцию Делоне и удалил ребра, которые больше заданного критерия (например, в 1.5 раза больше ребра для равносторонних треугольников при равномерном заполнении всего круга).
Для оставшихся треугольников рассчитал их площадь. Ну и среднюю плотность точек.

Не очень понял с удалением ребер, но интерес академический - Делоне просто неприемлем по скорости. Может чуть лучше convex hull, но конвексности никто не обещал (см напр картинку 3). Это расчет освещенности с помощью фотонных карт. Когда используется просто площадь круга возникают стандартные артефакты "dark edges & corners" - вот с ними и боремся.

[m_ax]

Я бы сделал так: Разбиваем круг на сектора (или на какую другую сетку). Для каждого сектора вычисляем плотность (локальная плотность).
Если пустот в круге особо нет, то значение плотности локальной от сектора к сектору будет не сильно флуктуировать около некоторого среднего. Если есть существенные области, где точек нет, то и локальная плотность там просядет (см рис). Для рассчёта итоговой средней плотности мы выкидываем просевшие значения, а оставшиеся усредняем.

Да, по сути это вариант (a).

Но как строить эти сектора? И сколько их брать? В общем, обычные проблемы велика - резвый старт, а потом завяз/захлебнулся

Очень просто. Площадь сектора (и, соответственно, их число) можно оценить так: N_sect = n*S_sect, где N_sect - среднее число точек на сектор, которое мы задаём руками, например N_sect = 2; n - средняя плотность: общее число точек на площадь круга и S_sect - площадь сектора.
Т.е. S_sect = N_sect/n.   

[Igors]

Если пустот в круге особо нет, то значение плотности локальной от сектора к сектору будет не сильно флуктуировать около некоторого среднего. Если есть существенные области, где точек нет, то и локальная плотность там просядет (см рис). Для рассчёта итоговой средней плотности мы выкидываем просевшие значения, а оставшиеся усредняем.

Да, идея понятна, но при обдумывании находится немало всяких "мелочей". Напр картинка 2 исходного поста - совсем уж пустые сектора там вряд ли найдутся. Или "инверсия" той же картинки 2 (точки только там где сейчас пусто). Думал по каждому сектору отслеживать min/max радиус, но потом их надо как-то "сопрягать"...

Рассмотрим проблему чуть подробнее. См аттач, слева направо

1) Исходные точки (как говорится "квази" случайные)
2) Результат осреднения (плотность визуализирована цветом). Вот они, те самые "dark edges & corners". В центре все хорошо, круг полностью заполнен. А вот на краях просто нет поверхности где точки можно сохранить, выходит площади половина. А на углах вообще четвертушка.
3) Пара конкркетных точек чисто для иллюстрации/понимания

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

[ssoft]

Часто больно форум валится в последнее время.
Картинки, поясняющие триангуляцию прикладываю ниже.
Сложность алгоритма построения N log(N), если мне память не изменяет).
При большом количестве точек может оказаться и трудоемко.

Предложение m_ax разделить на какую-либо сетку более простое. Можно и сетку взять декартовую равномерную для простоты.
Трудоемкость пробежаться по всем точкам и сопоставить с конкретной ячейкой будет порядка N.

[ViTech]

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

[Igors]

При большом количестве точек может оказаться и трудоемко.

Каким обычно бывает N (рабочий диапазон) назначается юзверем, он указывает напр что если в круг радиуса 5.0 попало 100 точек - это соответствует плотности 1.0. Обычно "собирается" 50-200 точек, но меньшее число, вплоть то нуля, также должно отрабатываться, и такие случаи обязательно будут (подробности ниже)

Картинки, поясняющие триангуляцию прикладываю ниже.
Сложность алгоритма построения N log(N), если мне память не изменяет).

Да, спасибо, понял идею. Действительно, Делоне будет делвть длинные ребра там где пустоты. Почему оцениваю как неприемлемо, ведь число точек не так уж велико. Дело в том что расчет этот выполняется для каждой точки шейдинга, поэтому прямолинейная реализация не тянет даже сейчас, когда надо только посчитать число попавших в круг, используется традиционное (или классическое) kd-tree. Приходится "запекать" (baking) а там ворох новых проблем.

Не уверен 100%, но просто "анализ расклада точек" по-моему вообще не катит, попробую показать почему. Вот картинка (аттач), ну конечно таким давно не удивить, но важно как она получена: простым N / S, больше никаких средств  не использовалось. Ни шейдеров, ни теней (техника моделирования точками их создает сама), ни даже дыффузного косинуса (тоже сам выходит). Заметим небольшую подсветку на попке сферы, так называемая "reverse illumination" - она тоже "на халяву", обычно этот эффект дорогущий.   

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

Так что, выходит просто "анализом точек" никак не отделаться, нужна обязательно доп инфа о геометрии/пересечениях? И решать выходит только аналитически, проскочить секторами никак? "Абыдно, слюшай", тем более что артефакты типа "ложки дегтя", мест где они возникают намного меньше 1%

[Igors]

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

См аттач, отсекаемые площади показаны розовым. Левый круг - ну вроде ничего сложного, храним ур-е секущей плоскости (4 числа), подставляем в него центр и каждую точку. Знаки разные - точку выбрасываем. Ну отнять площадь отсеченной хорды тоже несложно.

Возьмем расклад чуть посложнее - правый круг. Тут оптимизм быстро проходит.

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

Во-вторых, эти ребра - вовсе не бесконечные плоскости, они могут образовывать всякие полилинии - и как тогда выбрасывать точки и отсекать площадь?

В общем, пока все выглядит пугающе сложно/мудрено. Или я неправ?

Да, и вот что. Я же совсем не спрашиваю о каком-то полном, объемлющем решении, это не та задача где такое возможно. А может решения и объективно нет, и всю технику N/S пора сдавать в архив. Смелее, товарищи, "правельный ответ" никто не требует и претензий предъявлять не будет. Высказывайте свои мысли если таковые имеются. Спасибо за понимание.

[Igors]

Ну вот, и опять дубль-пусто  Ну ладно, понимаю, как говорил незабвенный Вересюшка

А откуда я это могу знать?

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

Ну во-первых, почему бы и не обсудить серьезную задачу на профессиональном форуме (программисты по-любому лучше чем теоретики). А во-вторых, ну конечно гуглилось, и немало, вот только найти ничего внятного не удается. Ситуевина примерно такая.

Конечно не я придумал этот метод (photon maps), теория была разработана еще во второй половине 90-х, а в первой половине нулевых все кто хотел его уже имели. Теория есть, и довольно обширная. Хорошо изучено как точки (фотоны) испускать, пере-излучать, выбирать радиус, собирать в нем точки и многое другое. Правда до "собрать готовое" дело не доходит, но не беда. разработаны структуры данных, напр что хранить в точке, как их искать и.т.п, есть достойные open-sources, поэтому реализовать самому несложно. Эти известные вещи весьма охотно (и довольно бездумно) перепечатывается из одной статьи в другую.

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

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

В общем в очередной раз убеждаюсь что тезис

Все уже давно написано

= полная брехня

[m_ax]

Кстатии, на днях решал задачку связанную с равномерным случайным распределением точек с плотностью n - число точек на единицу площади.
Вопрос: Каково в среднем растояние между двумя ближайшими точками?  Т.е. мы выбираем любую точку и смотрим на каком расстоянии от неё находится ближайшая к ней. И проводим этот эксперимент много-много раз и находим среднее значение) Каково это среднее значение, если плотность точек = n?

Очень прикольная пятничная задачка)

[Igors]

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

len = 1.0 / sqrt(n);

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

min_dist = k / sqrt(n);

Ну и написать строк 20 для экспериментального вычисления k - это будет куда быстрее чем лазание по гугле. Подозреваю k = 0.5 (угадал ?)

А услышать теорию было бы конечно интересно. Спасибо

[m_ax]

Подозреваю k = 0.5 (угадал ?)

Да. Но вопрос как это аналитически показать)