如何使用哈希映射查找一个点属于哪个区域？
How to find to which area a point belongs using hash maps?
假设我们有一个 2d space 分成簇说通过 Voronoi Tessellation:
我们有聚类轮廓、中点。给定这样的一个点（x，y 坐标）space 如何获取它的散列，以便我们可以确定它属于哪个集群？
我知道我们可以通过添加层来使我们的集群形成二叉树，并使用树搜索计算点所属的位置。我还知道我们可以将每个 space 点（假设它是隐蔽的）映射到一个集群并获得 O(1) 存储数据负载。但我寻求一种使用无序哈希映射样式从给定点获取集群的方法。如何（从算法上）做这样的事情？
在 Voronoi 站点（单元格 "centers"）上构建 kd-tree，您将在 O(NlogN) 时间内搜索最近的站点。
请注意，由于 Voronoi 图属性，点和最近的站点都属于同一个单元格
另一种选择 - 构建 trapezoid decomposition 细胞（也许，更复杂的方式）
在 Voronoi Tessellation 中，每个 "cluster" 都是点的轨迹，这些点的最近邻点是对应的中点。
因此，您感兴趣的实际上是找到新点的最近邻居（在所有中点中）。
如果您打算为此目的使用散列，也许您应该阅读有关 Locality-sensitive hashing 的内容。
假设我们有一个 2d space 分成簇说通过 Voronoi Tessellation:
我们有聚类轮廓、中点。给定这样的一个点（x，y 坐标）space 如何获取它的散列，以便我们可以确定它属于哪个集群？
我知道我们可以通过添加层来使我们的集群形成二叉树，并使用树搜索计算点所属的位置。我还知道我们可以将每个 space 点（假设它是隐蔽的）映射到一个集群并获得 O(1) 存储数据负载。但我寻求一种使用无序哈希映射样式从给定点获取集群的方法。如何（从算法上）做这样的事情？
在 Voronoi 站点（单元格 "centers"）上构建 kd-tree，您将在 O(NlogN) 时间内搜索最近的站点。
请注意，由于 Voronoi 图属性，点和最近的站点都属于同一个单元格
另一种选择 - 构建 trapezoid decomposition 细胞（也许，更复杂的方式）
在 Voronoi Tessellation 中，每个 "cluster" 都是点的轨迹，这些点的最近邻点是对应的中点。
因此，您感兴趣的实际上是找到新点的最近邻居（在所有中点中）。
如果您打算为此目的使用散列，也许您应该阅读有关 Locality-sensitive hashing 的内容。