Удалить близкие точки

Добрый день

Есть массив/контейнер точек, напр
Требуется удалить часть точек так чтобы расстояние между любыми двумя не превышало заданное, напр 1.0e-5

Спасибо

0

Сообщение от Royal_X какое может быть прикладное значение у данного задания.

Например, кластеризация векторов признаков в ML, близкие вектора заменяются усредненным или образцовыми векторами. Или приведение набора изображений к единой палитре. Возможно это что-то из обработки облака точек в результате 3d сканирования. Лучше задайте этот вопрос ТС.

0

Сообщение от u235 Лучше задайте этот вопрос ТС.

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

0

Также не оговаривается случай, если, например, три или более точки находятся близко, какие из них удалять?

Сообщение от alexu_007 А в задании не указано удалить так, чтобы в результате их осталось максимальное количество?

Об этом разговор уже был выше.

Стандартные системы рисования требуют дублирования точек (вертексов) в случае если атрибуты (обычно нормали) отличаются. Поэтому простейший кубик имеет 24 вертекса, по 4 на каждую грань. Такое представление данных наиболее популярно. Но иногда нужен "человеческий" кубик с 8 точками (углами). Поэтому коротко задание звучит так: сделать из 24 точек 8, но так чтобы кубик остался кубиком. При этом предполагается что точки в углах совпадают/равны, поэтому какие удалять - вопрос не стоит, любую(ые). К сожалению, на практике это не так, точки могут не совпадать точно, равенства нет. Также не сказано что нужно удалить минимальное число точек. Напр при достаточно (или слишком) малом минимальном расстоянии может оказаться что из 3 угловых точек можно удалить одну (а не 2). Но в данной задаче это не нужно и даже нежелательно, должна остаться только одна, т.е. кубик остается кубиком. Удаление должно сопровождаться пере-индексированием фейсов/граней

Специфика:
- минимальное расстояние на порядки меньше нормального, напр между углами кубика

- близких/совпадающих точек обычно мало, типа 5-10%, часто вообще нет. Но бывают и модели у которых близких много, часто учебные формы, тот же кубик. А вот у учебного чайника их мало

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

В общем это банальная/тривиальная задачка которую решает каждый кто начинает заниматься полигонной 3D геометрией. Типа "мама мыла раму". Ожидается решение в 100-150 строк написанное за день-два (лучше сегодня). Кстати оно возможно, нейросеть об этом упомянула (см выше). Но и более сложные варианты интересны

Добавлено через 1 час 12 минут

Сообщение от TheCalligrapher Приведенные мною алгоритмы и из анализ известны с семидесятых годов.

А Вы заметили что старый алгоритм плохо дружит с современными плюсами? Напр

Сообщение от TheCalligrapher using Mesh = std::unordered_map<MeshKey, std::vector<Points::iterator>, MeshKey::Hash>;

Вместо гордых контейнеров и итераторов (std::vector<Points::iterator>) лучше было отделаться скромной структурой
Это сократило бы расход памяти в полтора-два раза, а может и больше.

0

Сообщение от Igor3D А Вы заметили что старый алгоритм плохо дружит с современными плюсами? Напр

Вы постоянно генерируете какие-то туманные фразы, которые мне совершенно непонятны. Где вы тут увидели "алгоритм не дружит с плюсами" - в упор не ясно.

Сообщение от Igor3D Вместо гордых контейнеров и итераторов (std::vector<Points::iterator>) лучше было отделаться скромной структурой ... Это сократило бы расход памяти в полтора-два раза, а может и больше.

К алгоритмам неприменимо понятие сокращения "расхода пямяти в два раза". Это - чисто реализационная метрика. Но, я смотрю, тут просто как об стенку горох...

0

Сообщение от TheCalligrapher Где вы тут увидели "алгоритм не дружит с плюсами" - в упор не ясно.

Хорошо заметно что этот конкретный алгоритм лучше писать без std::, код был бы лучше и быстрее, а если и длиннее - то не намного

Сообщение от TheCalligrapher К алгоритмам неприменимо понятие сокращения "расхода пямяти в два раза".

Очень даже применимо, всегда оценивается сколько ресурсов он жрет

0

Сообщение от u235 pairs - упорядоченные пары индексов точек, у которых расстояние менее заданого. Т.е. можно удалить только точки, соответствующие первым индексам из пар (как я и сделал).

Да, по смыслу "удалить первую" мне подходит. Хорошо, ну и как задействовать "готовое проверенное решение"?

Сообщение от u235 Исходники на C++, функции query_pairs можно посмотреть на github.

Не нашел, плиз "ткните носиком". Скачал исходники SciPy на пытоне, но там реализации не видно, возможно сделана как внешняя на С, есть хедер. Некто Алиса говорит что исходников query_pairs на плюсах нет и советует посмотреть SciPyCpp - вариант для плюсов. Там не все реализовано, для kd-tree всего 3 ф-ции: создание, удаление и собсно поиск (с кучей аргументов). Причем может искать сразу много точек, хотя не знаю то ли это действительно "мультипоиск" то ли просто удобный цикл. Аналогичное решение (задействовать дуст) было предложено в посте #21. Ну и на (совсем уж) худой конец можно интегрировать пытон и вызывать скрипт.

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

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

0

Сообщение от Igor3D Скачал исходники SciPy на пытоне, но там реализации не видно, возможно сделана как внешняя на С, есть хедер.

Ты, наверное, видел Python-файл _kdtree.py из https://github.com/scipy/scipy... _kdtree.py. Однако, query_pairs в данном файле является лишь тонкой оберткой. Реальная тяжелая работа делается в C++ в модуле cKDTree (внутри пакета scipy.spatial.ckdtree).
Файл, который нужно смотреть, называется query_pairs.cxx и лежит по пути scipy/spatial/ckdtree/src/query_pairs.cxx
Ссылка на этот файл: https://github.com/scipy/scipy... _pairs.cxx
Но на этом файле логика не ограничивается.

Рядом в той же папке scipy/spatial/ckdtree/src/ лежат другие важные файлы, которые стоит смотреть вместе с ним:

ckdtree_decl.h / ckdtree.h - объявление структуры дерева
query.cxx - обычный query (поиск ближайших соседей)
query_ball_point.cxx, query_ball_tree.cxx - похожие по духу алгоритмы обхода дерева
distance.h - вычисление расстояний по разным нормам Минковского
rectangle.h - вспомогательная структура гиперпрямоугольников для отсечения веток дерева

Сам класс cKDTree (Python-обёртка над C++ структурой) находится в scipy/spatial/_ckdtree.pyx (Cython) - именно там query_pairs объявлен как метод и дергает C++ функцию query_pairs внутри.

Сообщение от Igor3D Некто Алиса говорит что исходников query_pairs на плюсах нет

бред.

В питоновском пакете scipy все тяжелые вычислительные части написаны на низкоуровневых компилируемых языках, а Python сверху просто соус. Причем, там используется не только С++, но и С и даже Fortran. А вот Cython, который компилируется в С или С++, выполняет роль прокладки, связывая Python и коды на остальных языках.
Конкретно KDTree/cKDTree написан именно на С++.

И вообще, scipy это же BSD опенсорс, весь код открыт, так что не нужно рассказывать байки, мол чего-то там нет. На гитхабе весь код доступен.

1

Сообщение от Igor3D и многократного удаления из вектора

а порядок точек в векторе имеет значение ? Или можно тусовать ?

0

Сообщение от Royal_X Файл, который нужно смотреть, называется query_pairs.cxx и лежит по пути scipy/spatial/ckdtree/src/query_pairs.cxx

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

Сообщение от Royal_X И вообще, scipy это же BSD опенсорс, весь код открыт, так что не нужно рассказывать байки, мол чего-то там нет.

Это Алиса меня ввела в заблуждение

Не пытайтесь искать прямую функцию query_pairs для C++ — её нет. Действуйте через Python: передавайте данные в SciPy,

Сообщение от Royal_X В питоновском пакете scipy все тяжелые вычислительные части написаны на низкоуровневых компилируемых языках, а Python сверху просто соус.

И это правильно, а то "на плюсах минута, а вот пытоновский скрипт секунда!". Звучит, мол, как пытон рулит! А он просто ловко устроился (пригрелась змея)

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

Сообщение от Алексей1153 а порядок точек в векторе имеет значение ? Или можно тусовать ?

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

0

Сообщение от TheCalligrapher заявления о том, что хэш-таблица реализует ассоциативный массив за невероятное O(1)

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

0

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

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

0

Сообщение от iifat которые хэш-функция отображала в один ключ.

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

Упростим задачу до уровня юзера: "удалить повторяющиеся точки". Да, в большинстве случаев это так, и юзер не знает что точки-то могут и не совпадать точно, хотя проверять будет именно на кубике с несовпадающими углами. Хорошо, как решать задачу с точным совпадением? Конечно напрашивается хеш, ведь

Что может быть быстрее О(1)?

Альтернатива - сортировка, ну она же O(nlog(n)) должна быть намного медленнее. Так вот ни фига, сортировка быстрее, причем ощутимо. Конечно можно придумать такие данные что хеш смотрится достойно, но для этого совпадений должно быть довольно много. А на 5-10% повторов сортировка быстрее в несколько раз. Почему? Не знаю. Возможно дело в реализации std::unordered_map

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

0

Сообщение от TheCalligrapher С каких это пор "данные, которые хэш-функция отображала в один ключ" являются чем-то примечательным или проблематичным?

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

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

Наверное, да, хотя в моём случае программа просто падала. Пятна на солнце, разумеется, есть, но если б они ежетысячелетне сжигали поверхность Земли дотла, мы б с вами не спорили о достоинствах гарантированно и если повезёт.

0

Сообщение от iifat С тех ровно самых пор, когда вместо неких процентов коллизий все данные отобразились в один ключ.

Ого! Аж все! Подозреваю, это был ключ 0x666666 (демонически смеется).

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

Сообщение от iifat В моём случает программа просто падала,

"У меня почему-то падала программа, я уверен дело в совпавших хэшах..."

0

Сообщение от TheCalligrapher Другими словами, дело было в кривых руках

Восхищён вашим терпением и сочуствую вашим мукам. Это ж надо было терпеть 53 сообщения, и только в 54-м провозгласить свой мощный ум и вселенскую мудрость! О да, разумеется, Вам, о Мудрейший, Тому, Чей Ясный Взор Пронзает Времена и Расстояния, всё ясно. Просто им на дешёвом рынке подсунули подгнившую хэш-функцию.
Глупо было бы желать вам удачи во всех ваших начинаниях: понятно, что удача сама бегает за вами, как жалкая собачонка.

0

Когда не покладая рук провозглашаешь свою Вселенскую Мудрость в каждом сообщении, а замечают это лишь к пятьдесят четвёртому...

0

Вот еще интересный момент

Сообщение от Igor3D C++ 1 2 3 4 5 std::vector<int> dups(points.size(), -1); ... #pragma omp parallel for for (int i = 0; i < points.size(); ++i)  dups[i] = find_dup(points, i);

Оцените эту попытку многопоточности. Попинайте, не стесняйтесь (желание поучать в природе человека )

0

Сообщение от TheCalligrapher Когда не покладая рук провозглашаешь свою Вселенскую Мудрость

В основном подтверждаешь собственную значимость сам для себя.
Удовлетворяешь своё самолюбие.
Искусственный интеллект всё испортил.
Он оказывается работает лучше и продуктивнее и пальцы веером не делает.

0

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

Сообщение от Наталья8 Он оказывается работает лучше и продуктивнее и пальцы веером не делает.

действительно, сейчас легче получить ответ от ИИ, нежели на форуме. Собственно, снижения активности на форуме тому яркое подтверждение.
Сейчас форум для меня что-то вроде Omegle, т.е. что-то вроде площадки для общения с анонимами на всякие темы.

0

Сообщение от Royal_X действительно, сейчас легче получить ответ от ИИ, нежели на форуме.

Ну так почему же нет ответа на мой простой вопрос (пост #57)? Как кстати и на предыдущий. Пользоваться ИИ я не запрещал

Сообщение от Royal_X действительно, сейчас легче получить ответ от ИИ, нежели на форуме. Собственно, снижения активности на форуме тому яркое подтверждение. Сейчас форум для меня что-то вроде Omegle, т.е. что-то вроде площадки для общения с анонимами на всякие темы.

Так это, вообще-то, правильно. Форумы предназначены для общения людей (а не для подтирания соплей нерадивым ученикам)

0