假设我们有一个二维空间，通过 Voronoi Tessellation 分成多个簇:
我们有聚类轮廓、中点。在这样的空间中给定一个点(x，y 坐标)如何获取它的哈希值，以便我们可以确定它属于哪个集群？
我知道我们可以通过添加层来使我们的集群形成二叉树，并使用树搜索计算点所属的位置。我也知道我们可以将每个空间点(假设它是隐蔽的)映射到一个集群并获得 O(1) 存储数据负载。但我寻求一种使用无序 HashMap 样式从给定点获取集群的方法。如何(从算法上)做这样的事情？
最佳答案
构建kd-tree在 Voronoi 站点(单元格“中心”)上，您将在 O(NlogN) 时间内搜索最近的站点。
请注意，由于 Voronoi 图属性，点和最近的站点都属于同一个单元格
另一个选项 - 构建 trapezoid decomposition细胞(也许，更复杂的方式)
关于algorithm - 如何使用 HashMap 查找一个点属于哪个区域？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43517652/