Прореживание облака точек

Здравствуйте

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

Есть облако из N точек в пр-ве. Нужно выкинуть из него некоторое кол-во точек чтобы сделать плотность более равномерной. Пользователь хочет сделать это 2 разными способами (2 подзадачи)

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

- выкинуть заданное кол-во точек чтобы получить облако из M точек (M < N).

Интересует в первую очередь "дешевизна" решения, это всего лишь 2 малюсенькие опции. Разумеется "каждый с каждым" не проходит уже на 10K точек, а их может быть и намного больше

С уважением
Игорь

0

Поступите проще. Разбейте вашу область на квадраты с
таким рассчётом, чтобы в квадрате была одна точка.
Лишнее выбросьте. А если попадется квадрат без точки, то
добавьте точку в его центр

0

Сообщение от echs Поступите проще. Разбейте вашу область на квадраты с таким рассчётом, чтобы в квадрате была одна точка. Лишнее выбросьте. А если попадется квадрат без точки, то добавьте точку в его центр

Это можно понимать всяко-разно. К тому же в пр-ве это не квадрат а куб. Вероятно Вы имели ввиду использовать ассоциативный контейнер, напр так

- из координат данной точки получить "ключ" (напр поделить x, y, z на сторону и округлить)
- если по этому ключу уже есть точка, то данную выкидываем, иначе оставляем

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

0

Igor3D
Вы меня в целом правильно поняли. Хорошо пусть
будет областью куб (это не принципиально). Суть
разбиения состоит в том, что "куб" - это как бы "большая"
точка. То есть мы переходим от очень большого количества
точек к меньшему количеству. Вот вы говорите, что может
получится где-то не очень равномерно. Да. Вы правы. Вы
тысячу раз правы!! Но ни один алгоритм не даст вам такой
гарантии. Погрешность в плотности была, есть и будет...
...
Есть и другой вариант, при котором в принципе не будет рядом
стоящих точек. Итак предполагается, что все пространство разбито
на кубики. Диаметр кубиков должен быть равен заданному вами
расстоянию minD. В этом случае вы берете первый (по счету) кубик
и оставляете в нем одну точку, во всех остальных кубиках, соприкасаемых
с данным (их 26 штук) точки полностью выбрасываются.
...
Если у вас задан трёхмерный массив, то все операции удобно
провести в трёхкратном цикле с шагом равным 2.
Вы понимаете, кубик с точкой будет отделен от другого кубика с точкой
пустым кубиком. И условие плотности будет соблюдено.

0

Сообщение от echs Хорошо пусть будет областью куб (это не принципиально).

"Размер(ность) имеет значение", дальше речь пойдет в основном о ней

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

Проще проверять соседние кубы и выкидывать точки расстояние до которых (от точки данного куба) < minD. Но даже это совсем не "дешево" для реализации.

Сообщение от echs Если у вас задан трёхмерный массив,

Применимость таких структур (lattice) весьма ограничена в 3D вследствие потенциально большого объема хранимых данных. Напр все точки как точки а один урод отлетел на километр - получите "sparse". Поэтому хранят обычно лишь "живые" кубы (в которых есть точки), но тогда придется делать двоичный поиск для каждого из 26 соседей. В общем забот там предостаточно, начинать эту длинную песню мне совсем не хочется.

Да, и по-прежнему ничего не видно для второго варианта (удалить заданное число точек)

0

Igor3D
Есть другой вариант, который тоже основан на принципе
"разделяй и властвуй". Надо трёхмерное пространство
разрезать на слои как пирог. Расстояние между слоями
должно быть по определению minD. Надеюсь вы уже
догадались, что слои должны чередоваться. Слой, который
содержит точки лежит на слое, в котором нет точек (а если
они есть, то все точки выкидываются).
Затем каждый слой (некоторое подобие плоскости имеющей
толщину) делится параллельными линиями на части. Расстояние
между линиями равно minD. Здесь тоже полоски делятся на
те, что содержат точки и те, в которых их быть не должно.
(если точки есть, то выбрасываются). Эти полосы чередуются...
...
Вам в принципе может хватить одного линейного массива
если, конечно все данные хранятся в файле (а где же еще
если их к примеру миллион)

0

Сообщение от Igor3D расстояние между любыми двумя точками не должно быть меньше заданного minD, сколько точек выкинуть без ограничений

Если нужно/хочется при этом убирать шум и выбросы - то нейросетка типа SOINN/ESOINN.

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

0

Сообщение от echs (а если они есть, то все точки выкидываются).

"Дешевое" решение совсем не значит что можно делать "все что хочу". Напр захотели выкинуть точки - и выкинули. Так нельзя, напр если все исходные точки достаточно далеко друг от друга (подзадача 1), то ничего и не выкидывается

Сообщение от VTsaregorodtsev Если нужно/хочется при этом убирать шум и выбросы

Не нужно

Сообщение от VTsaregorodtsev то метод серединного сечения многомерного пространства,

А что это за метод? (гугл дает только что-то о лесозаготовках)

Ну и попробую еще раз: может как-то планировать чтобы код/решение были общими для обеих подзадач?

0

Сообщение от Igor3D А что это за метод?

https://en.wikipedia.org/wiki/Median_cut
На русском по методу медианного сечения тоже нагугливается немного.

Просто 20 лет назад, в русском PC Magazine 7/95, переводилось именно как серединное сечение. А импринтинг - вещь заразная

0

Все данные точки записать в массив известной длинны. Опция разрежение это количество запросов к рендом генератору. Например задаем разрежение 1000.

От случайного генератора 1000 раз спрашиваем индекс в массиве точек которую удаляем.

0

Сообщение от VTsaregorodtsev https://en.wikipedia.org/wiki/Median_cut На русском по методу медианного сечения тоже нагугливается немного.

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

Сообщение от Excalibur921 Все данные точки записать в массив известной длинны. Опция разрежение это количество запросов к рендом генератору. Например задаем разрежение 1000. От случайного генератора 1000 раз спрашиваем индекс в массиве точек которую удаляем.

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

0

Переводим случайное число в номер индекса в массиве известной длинны и удаляем эту точку.

0

Сообщение от Igor3D расстояние между любыми двумя точками не должно быть меньше заданного minD, сколько точек выкинуть без ограничений

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

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

0

Сообщение от Shamil1 Задача сформулирована некорректно (неполно).

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

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

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

0

Igor3D,
А по существу?

Сообщение от Shamil1 Устроит ли это Пользователя?

0

Сообщение от Shamil1 А по существу?

Прибегаете к дешевым приемам

Сообщение от Shamil1 Цитата Сообщение от Shamil1 Посмотреть сообщение Устроит ли это Пользователя?

А чего Вы это спрашиваете у меня/юзера? Сами решайте, Вы же программист (алгоритмист)

0

Сообщение от Igor3D Прибегаете к дешевым приемам

Вы ищете подвох там, где его нет. Я предложил алгоритм, но отметил недостатки, присущие результату.

Сообщение от Igor3D Сами решайте, Вы же программист (алгоритмист)

Каким образом я могу решать, какой результат Вам нужен?

Что касается "инициативы", то есть две разные работы: постановка задачи и решение задачи. Для выполнения первой мне бы понадобился ответ на вопрос "Для чего пишется эта программа". Краткий ответ на этот вопрос занял бы приблизительно 10 страниц А4. Более компактный ответ, скорее всего, лишь породил бы дополнительные вопросы. Поэтому мне тупо лень этим заниматься (тем более, что телепаты в отпуске).

0

Сообщение от Shamil1 есть две разные работы: постановка задачи и решение задачи. Для выполнения первой мне бы понадобился ответ на вопрос "Для чего пишется эта программа". Краткий ответ на этот вопрос занял бы приблизительно 10 страниц А4. Более компактный ответ, скорее всего, лишь породил бы дополнительные вопросы. Поэтому мне тупо лень этим заниматься (тем более, что телепаты в отпуске).

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

0

Похоже, что Вы не прочитали алгоритм, который я предложил.

0

Сообщение от Shamil1 Похоже, что Вы не прочитали алгоритм, который я предложил.

Это я о нем тактично умолчал, т.к. знаю что Вы способны на гораздо большее.

Мои соображения. Думаю что неизбежен какой-то "базовый поиск" который надо повторить для всех N точек. Всякий раз базовый поиск выдает какое-то число "пар" (точка-точка) которые надо сохранить, и на основании всех этих пар уже решать кого удалять. И тут начинаются неясности. В первой подзадаче нужно сохранять все пары с расстоянием < minD, число сохраненных может оказаться слишком велико. Во второй наоборот мало если ограничить число пар числом удаляемых - ведь одна точка может входить в неск пар. Решать это за 2 и более прохода не хотелось бы.

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

0