二维空间中是否存在各点唯一且可用于计算两点间距的点属性?
问题解答
存在满足要求的点属性,这类属性本质是n维空间到一维实数域的单射映射,仅当输入点完全相同时,映射得到的数值才相等。如果需要满足「已知两个属性值即可计算两点距离」的要求,只需要额外保证这个映射是可逆的,能从数值还原出原始坐标即可,常见的实现方案有以下几种:
- 二进制交错编码(Z阶编码)
适用于任意维度的实数/整数坐标场景,以二维点(x,y)为例:将两个坐标的二进制位按顺序交错拼接,得到的新二进制数对应的十进制值就是目标属性。比如坐标(3,5)转二进制为011和101,交错后得到011011,对应十进制值27。
该编码是严格单射,仅当两点坐标完全一致时编码值相同。需要计算距离时,将编码值按位拆分即可还原两个点的原始坐标,代入距离公式即可得到结果。 - 康托配对函数
适用于二维非负整数坐标场景,函数公式为:π(x,y) = (x + y) * (x + y + 1) / 2 + y
该函数已经被证明是双射,不同的整数坐标必然对应不同的非负整数值,也可以通过编码值反向解码得到原始坐标,满足距离计算要求。 - 希尔伯特曲线编码
属于空间填充曲线的一种,同样是将n维坐标映射为一维数值,除了满足唯一性、可逆性的要求外,还能保证空间中相邻的点对应的编码值也相邻,适合需要做空间索引的场景。
注意:如果使用固定精度的数值类型(比如双精度浮点数)存储编码值,高维坐标或者高精度坐标场景可能会出现精度溢出导致的碰撞问题,这种情况可以改用任意精度数值类型存储解决。
内容的提问来源于stack exchange,提问作者Khamyl
相关产品推荐
相关产品推荐

