c++ - 3D 曲面细分算法

Question

背景

我有一个 3D 场景，我想离散化它的空间，以便每个坐标都(x, y, z)属于一个特定的单元格。
彼此靠近的坐标属于相同的单元格。当我输入一个位于我的三维对象（主要是球体）表面上的坐标时，我需要检索它所属的单元格。
对于那些熟悉强化学习的人，此操作将用于 Q-Learning，将状态（取决于坐标的单元格）映射到 Q 值
这是我试图实现的一个示例：

可能的解决方案

我知道 Voronoi 图可以帮助解决这个问题，但我也读到从头开始实现它很复杂。我在 C++ 中找到了一些库来处理这个问题，但它们主要是 Voronoi 2D ( CGAL )。我并不特别需要 Voronoi，我只需要以合理的方式离散化空间并为其寻找库/实现我偶然发现了 Voronoi 图。

问题 有没有人熟悉库或公共实现来在 C++ 中实现这种离散化？

标签： c++geometryvoronoiq-learning

Answer 1

根据您的要求，可能有许多解决方案。我能想到的最简单的方法是使用统一的网格来划分你的空间。那么，一个点的单元格(x,y,z)就是(floor(x),floor(y),floor(z))。您可以缩放坐标以获得更精细的网格。如果您需要单个索引，请使用哈希函数或索引边界框内有限网格的所有单元格。不需要库，但它不适应区域中的点数。

Voronoï 图是另一种可能的解决方案，但如果您想要所有单元格的确切形状，它们的实现要复杂得多。如果您只需要找到最近的站点点，请使用 Kd-Trees，因为它们实现起来要简单得多，并且可以为您提供所需的信息。您可以在GEOGRAM中找到这两种算法的实现，这是一个免费且开放的（您可以在商业应用程序中使用它）C++ 库，用于进行快速几何计算。它工作得很好，而且很容易使用。它也是便携式的，可以在 Linux、Windows、Mac OSX 和 Android 上运行。