Выброс точек с прореживанием

@Igor3D · Регистрация: 01.10.2012

Студворк — интернет-сервис помощи студентам

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

Есть генератор последовательно выбрасывающий точки (x, y, z) в пр-ве. Требуется всего-навсего выкидывать точку если расстояние от нее до любой из имеющихся меньше заданного (d). Иначе точка принимается и становится значимой для следующих выбросов. Просто перебор заметно притормаживает т.к. точек прилично.

Понятно что в теории решений немало, но хотелось бы сделать это "малой кровью", не влезая в развесистые деревья и.т.п. Это всего лишь маленькая деталь/подзадача

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

@SlavaSSU · 23.11.2015, 18:25

Igor3D, расскажи свое решение, к-ое "просто перебор", и координаты до скольки бывают?

echs · 23.11.2015, 18:54

1.
Есть такой вариант. Задается матрица. Каждая точка занимает
в этой матрице свое место только в том случае, если окружающие
элементы матрицы пусты. Величину расстояния вы задаете сами.
2.
Теперь если матрица маловата. Тогда эта матрица помещает точку
еще при одном дополнительном условии. Координаты точки уменьшаются
в Эн раз . И далее такая же проверка на близость. Это очень быстрый
алгоритм. Скорость обработки матриц велика.
3.
Здесь только один минус. Требуется вместить столько точек, что ни в
какой массив они не поместятся. Можно использовать файл прямого доступа
Размер большой, а скорость падает (что взять с файла?)

Добавлено через 3 минуты
Возьмите кубическую матрицу.

Добавлено через 5 минут
Матрицы можно использовать для предварительного разрежения.
Пусть она подсчитывает число точек. Если число точек велико, то
это будет запрет на помещение туда любых точек.

@Igor3D · 24.11.2015, 06:57 **[ТС]**

Сообщение от SlavaSSU

Igor3D, расскажи свое решение, к-ое "просто перебор", и координаты до скольки бывают?

Реально до 1.0e+6. Сейчас это выглядит так

C++
1
2
3
float minDist2 = userDist * userDist;
for (int i = 0; i < particle.size(); ++i)
 if ((particle[i].position() - test).lengthSquare() < minDist2) return false;

Сообщение от geh

Есть такой вариант. Задается матрица

Ну не к месту здесь такого слона заводить

@SlavaSSU · 24.11.2015, 13:17

Igor3D, а координаты не целочисленные бывают?

ну есть тупая вещь, может ускорит хз. вот возьмем плоскость YOZ. теперь нарежем все пространство такими плоскостями, параллельными плоскости YOZ и проходящими через точки (0, 0, 0), (d, 0, 0), (2 * d, 0, 0) и т.д.
Тогда когда приходит точка, нам надо проверить кусочек пространства, в к-ом лежим она сама, кусочек "слева" и кусочек "справа" от нее.

@Igor3D · 25.11.2015, 09:48 **[ТС]**

Сообщение от SlavaSSU

Igor3D, а координаты не целочисленные бывают?

Координаты - только флоты

Сообщение от SlavaSSU

ну есть тупая вещь, может ускорит хз. вот возьмем плоскость YOZ. теперь нарежем все пространство такими плоскостями, параллельными плоскости YOZ и проходящими через точки (0, 0, 0), (d, 0, 0), (2 * d, 0, 0) и т.д.
Тогда когда приходит точка, нам надо проверить кусочек пространства, в к-ом лежим она сама, кусочек "слева" и кусочек "справа" от нее.

Это просто-напросто сортировка по оси X c дальнейшим поиском в сортированном контейнере вперед и назад до тех пор пока расстояние по X не превысит заданное d. Сам неск раз советовал его как быстрое (пусть и не лучшее) решение. На текущий момент да, по-прежнему не вижу лучшего. Проблемно какую ось брать (т.е. почему "X" а не "Y" или "Z" ?)

@SlavaSSU · 25.11.2015, 13:53

Igor3D, можно хранить сразу std::set<float> X, Y, Z - все иксы, игреки и зеты по отдельности. потом когда пришла точка (x, y, z), то сначала проверяем, нет ли в X значения, к-ое строго больше x + d или строго меньше x - d, аналогично для Y и Z. и если все они не выполнились, то только тогда начинать искать.

@Igor3D · 25.11.2015, 14:19 **[ТС]**

Сообщение от SlavaSSU

Igor3D, можно хранить сразу std::set<float> X, Y, Z - все иксы, игреки и зеты по отдельности. потом когда пришла точка (x, y, z), то сначала проверяем, нет ли в X значения, к-ое строго больше x + d или строго меньше x - d, аналогично для Y и Z. и если все они не выполнились, то только тогда начинать искать.

Тогда технически проще хранить три std::set <Point *> с разными хвункторами. Но смысл не понял. Ну есть напр по X значение которое "за границами диапазона" - и что? Ведь может быть и "в диапазоне", по тому же X

@SlavaSSU · 25.11.2015, 14:31

Igor3D, есть точка (x, y, z), и в нашем множестве уже есть точка (x2, y2, z2) и fabs(x - x2) > d. ну уже есть точка на расстоянии больше заданного, поэтому наша точка гарантированно останется.

..... Ой. Все, что я писал выше - неправда. Я не так прочел задачу, я прочитал до любой == до каждой(до всех)...

@Igor3D · 25.11.2015, 15:24 **[ТС]**

Сообщение от SlavaSSU

..... Ой. Все, что я писал выше - неправда

Переклинило - бывает

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

@Shamil1 · 25.11.2015, 16:02

Есть словарь "кубиков".
Ключём является тройка индексов кубика по осям координат.
Значением будет список точек, которые попадают в данный кубик. Чтобы вычислить, в какой кубик попадает точка, используем формулы вида: n_x = (int)(x/d). (Если отрицательные числа возможны и они округляются "неправильно" == вверх, то нужно использовать floor).
Если область выпадения точек достаточно компактна, то вместо словаря можно использовать трёхмерный массив.

Основной цикл:
1. Выбрасываем новую точку
2. Перебираем 27 ближайших кубиков (можно отсортировать их по расстоянию от центра кубика до новой точки). Если кубик есть в словаре, то проверяем расстояния до всех точек в списке.
3. Если точка подошла, то добавляем её в словарь кубиков (создавая "кубик", если его не было).

@VTsaregorodtsev · 26.11.2015, 00:09

Сообщение от Igor3D

Просто перебор заметно притормаживает т.к. точек прилично.

Что говорит профилировщик? Где самые тормозные места у приведённого кода программы (у его второй-третьей строки)?
А то если используется какая-то чужая (да или Ваша, но универсальная) либа - то там в реализациях мембер-функций и оператора [] может быть стооооолько ненужных именно этой задаче внутренних проверок, что тормоза и возникают.
Плюс, чужая либа скорее всего оттранслирована для совместимости с каким-то древним процессором. Т.е. вычисление расстояния там вполне может выполняться через скалярные fpu-команды, а не через векторные SSE. Ну или задействовать SSE нельзя потому, что данные невыравнены нужным образом.

@Igor3D · 26.11.2015, 09:21 **[ТС]**

Сообщение от Shamil1

Основной цикл:
1. Выбрасываем новую точку
2. Перебираем 27 ближайших кубиков (можно отсортировать их по расстоянию от центра кубика до новой точки). Если кубик есть в словаре, то проверяем расстояния до всех точек в списке.
3. Если точка подошла, то добавляем её в словарь кубиков (создавая "кубик", если его не было).

Тут нужно найти все 27 кубиков, вырисовывается 9 двоичных поисков. Также уязвимое место - выбор размера кубика. Ну и кода здесь немало. Но вообще хорошо, сами придумали?

Не по теме:

Писал этот алгоритм в 98 году. Много позже потребовалось апдейтить старый продукт, решил заменить свой велосипед на octree. Но ничего хорошего из этого не вышло, octree оказалось куда медленнее и памяти сожрало немеряно. Пришлось вернуть старый код :)

Сообщение от VTsaregorodtsev

Что говорит профилировщик?

Показывает общие затраты на этом цикле - и все. Т.е. все вызовы уже "разинлайнены". Приведение к С массиву и ++указателя дает прирост до 5%. SSE (AVX, AVX2)- может быть, но только в виде какой-то либы, самому - только грыжу наживать. Тогда тот же вопрос: а какой либы?

Хотелось бы адекватного решения, начинать "большую войну" из-за крохотной детали не тянет.

@Shamil1 · 26.11.2015, 12:44

Сообщение от Igor3D

Тут нужно найти все 27 кубиков, вырисовывается 9 двоичных поисков. Также уязвимое место - выбор размера кубика. Ну и кода здесь немало. Но вообще хорошо, сами придумали?

Словарь для меня - это хэштаблица. Поэтому двоичных поисков нет.
Размер кубика d, насколько я понял из условия задачи, фиксирован.
Кода на 1-2 экрана.
Придумал сам.

@Igor3D · 26.11.2015, 16:21 **[ТС]**

Сообщение от Shamil1

Словарь для меня - это хэштаблица. Поэтому двоичных поисков нет.

Вполне в стиле языка на котором Вы пишете

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

@Shamil1 · 26.11.2015, 20:22

Сообщение от Igor3D

Но так ли уж хорош хеш в данном случае?

Зависит от характера данных.

Сообщение от Igor3D

Я обратил внимание на особенность: в данном случае в кубике могут быть максимум 2 точки (

Я берусь с ходу уместить 6 точек в один кубик. А если подумать, то, возможно, и больше.

@Igor3D · 27.11.2015, 11:07 **[ТС]**

В общем виде выглядит так: есть N = 27 диапазонов данных (точек), для каждого есть ключ. И есть контейнер точек (какой - решаем сами). Найти в контейнере все точки принадлежащие всем диапазонам, вычисляя для каждой расстояние. Если расстояние меньше заданного - выход.

Очевидно что стандартное решение искать диапазон за диапазоном уже неоптимально, а в общем случае с ростом N может быть и просто плохо. Почему бы нам не искать сразу все 27? Как это сделать?

@Shamil1 · 27.11.2015, 23:16

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

@Igor3D · 28.11.2015, 12:12 **[ТС]**

Сообщение от Shamil1

Если верить, что хэш-таблица ищет за О(1), то нет разницы, искать 27 по очереди или сразу все 27.

Ох уж эти "О"

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

Однако я не вижу подходящего стандартного контейнера на плюсах. Вот если бы вставки не было (такие задачи тоже есть) - тогда просто сортированный массив/вектор, и на каждом поиске подрезаем диапазон поиска для следующего. Но я не вижу подходящего lower_bound в стандартных ассоциативных контейнерах std::set/map, выходит в них всякий раз поиск выполняется для всего дерева

Может здешние эксперты С++ помогут?

@VTsaregorodtsev · 29.11.2015, 23:05

Сообщение от Igor3D

Тогда тот же вопрос: а какой либы?

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

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

Новые блоги и статьи Все статьи Все блоги /
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Номеклатура. . .

@Igor3D 1970 / 826 / 115 Регистрация: 01.10.2012 Сообщений: 4,962 Записей в блоге: 2

	Выброс точек с прореживанием 23.11.2015, 13:49. Показов 1275. Ответов 20 Метки нет (Все метки) Здравствуйте Есть генератор последовательно выбрасывающий точки (x, y, z) в пр-ве. Требуется всего-навсего выкидывать точку если расстояние от нее до любой из имеющихся меньше заданного (d). Иначе точка принимается и становится значимой для следующих выбросов. Просто перебор заметно притормаживает т.к. точек прилично. Понятно что в теории решений немало, но хотелось бы сделать это "малой кровью", не влезая в развесистые деревья и.т.п. Это всего лишь маленькая деталь/подзадача С уважением Игорь 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	23.11.2015, 18:25
	Igor3D, расскажи свое решение, к-ое "просто перебор", и координаты до скольки бывают? 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	23.11.2015, 18:54
	1. Есть такой вариант. Задается матрица. Каждая точка занимает в этой матрице свое место только в том случае, если окружающие элементы матрицы пусты. Величину расстояния вы задаете сами. 2. Теперь если матрица маловата. Тогда эта матрица помещает точку еще при одном дополнительном условии. Координаты точки уменьшаются в Эн раз . И далее такая же проверка на близость. Это очень быстрый алгоритм. Скорость обработки матриц велика. 3. Здесь только один минус. Требуется вместить столько точек, что ни в какой массив они не поместятся. Можно использовать файл прямого доступа Размер большой, а скорость падает (что взять с файла?) Добавлено через 3 минуты Возьмите кубическую матрицу. Добавлено через 5 минут Матрицы можно использовать для предварительного разрежения. Пусть она подсчитывает число точек. Если число точек велико, то это будет запрет на помещение туда любых точек. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	24.11.2015, 13:17
	Igor3D, а координаты не целочисленные бывают? ну есть тупая вещь, может ускорит хз. вот возьмем плоскость YOZ. теперь нарежем все пространство такими плоскостями, параллельными плоскости YOZ и проходящими через точки (0, 0, 0), (d, 0, 0), (2 * d, 0, 0) и т.д. Тогда когда приходит точка, нам надо проверить кусочек пространства, в к-ом лежим она сама, кусочек "слева" и кусочек "справа" от нее. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	25.11.2015, 13:53
	Igor3D, можно хранить сразу std::set<float> X, Y, Z - все иксы, игреки и зеты по отдельности. потом когда пришла точка (x, y, z), то сначала проверяем, нет ли в X значения, к-ое строго больше x + d или строго меньше x - d, аналогично для Y и Z. и если все они не выполнились, то только тогда начинать искать. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	25.11.2015, 14:31
	Igor3D, есть точка (x, y, z), и в нашем множестве уже есть точка (x2, y2, z2) и fabs(x - x2) > d. ну уже есть точка на расстоянии больше заданного, поэтому наша точка гарантированно останется. ..... Ой. Все, что я писал выше - неправда. Я не так прочел задачу, я прочитал до любой == до каждой(до всех)... 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	25.11.2015, 16:02
	Есть словарь "кубиков". Ключём является тройка индексов кубика по осям координат. Значением будет список точек, которые попадают в данный кубик. Чтобы вычислить, в какой кубик попадает точка, используем формулы вида: n_x = (int)(x/d). (Если отрицательные числа возможны и они округляются "неправильно" == вверх, то нужно использовать floor). Если область выпадения точек достаточно компактна, то вместо словаря можно использовать трёхмерный массив. Основной цикл: 1. Выбрасываем новую точку 2. Перебираем 27 ближайших кубиков (можно отсортировать их по расстоянию от центра кубика до новой точки). Если кубик есть в словаре, то проверяем расстояния до всех точек в списке. 3. Если точка подошла, то добавляем её в словарь кубиков (создавая "кубик", если его не было). 0

@Igor3D 1970 / 826 / 115 Регистрация: 01.10.2012 Сообщений: 4,962 Записей в блоге: 2
	27.11.2015, 11:07 [ТС]
	В общем виде выглядит так: есть N = 27 диапазонов данных (точек), для каждого есть ключ. И есть контейнер точек (какой - решаем сами). Найти в контейнере все точки принадлежащие всем диапазонам, вычисляя для каждой расстояние. Если расстояние меньше заданного - выход. Очевидно что стандартное решение искать диапазон за диапазоном уже неоптимально, а в общем случае с ростом N может быть и просто плохо. Почему бы нам не искать сразу все 27? Как это сделать? 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	27.11.2015, 23:16
	Если верить, что хэш-таблица ищет за О(1), то нет разницы, искать 27 по очереди или сразу все 27. Тем более, что мы определяем, какие искать в первую очередь (сначала тот, в какой попали, затем те, что ближе), до того как начинаем искать. 0