Алгоритм разделения трехмерных поверхностей

Question

Фон

У меня есть 3D-сцена, и я хочу дискретизировать ее пространство так, чтобы каждая координата (x, y, z) принадлежала определенной ячейке.
Координаты, близкие друг к другу, принадлежат одним и тем же ячейкам. Когда я ввожу координату, лежащую на поверхности одного из моих трехмерных объектов (в основном, сфер), мне нужно получить ячейку, которой она принадлежит.
Для тех, кто знаком с изучением подкрепления, эта операция будет использоваться для Q-Learning, чтобы отобразить состояния (ячейки в зависимости от координат) в Q-значения
Это пример того, чего я пытаюсь достичь:

Возможные решения

Я знаю, что диаграмма Вороного может помочь в этом, но я также читал, что реализовать ее с нуля сложно. Я нашел некоторые библиотеки в C ++, чтобы справиться с этим, но в основном это Вороной 2D ( CGAL ). Вороной мне не нужен, мне нужно только разумно дискретизировать пространство и искать библиотеки / реализации для него, я наткнулся на диаграммы Вороного.

Вопрос Кто-нибудь знаком с библиотеками или публичной реализацией для достижения этой дискретизации в C ++?

Answer 1

В зависимости от ваших требований, может быть много решений. Самое простое, что я могу придумать, - это разделить пространство, используя равномерную сетку. Тогда ячейка точки (x,y,z) просто (floor(x),floor(y),floor(z)). Вы можете масштабировать координаты, чтобы получить более точную сетку. Если вам нужен отдельный индекс, используйте хеш-функцию или индексируйте все ячейки конечной сетки внутри ограничительной рамки. Библиотеки не требуются, но это не адаптивно к количеству точек в области.

Диаграммы Вороного - еще одно возможное решение, но их гораздо сложнее реализовать, если вы хотите получить точную форму всех ячеек. Если вам нужно только найти ближайшую точку сайта, используйте Kd-Trees, поскольку они намного проще в реализации и предоставляют необходимую информацию. Вы можете найти реализацию обоих этих алгоритмов в GEOGRAM , бесплатной и открытой (вы можете использовать ее в коммерческих приложениях) библиотеках C ++ для выполнения быстрых геометрических вычислений. Он работает довольно хорошо и прост в использовании. Он также переносим, ​​работает на Linux, Windows, Mac OSX и Android.