在XKCD comic 195中,建议使用Hilbert curve来设计因特网地址空间的映射,以便将来自相似IP地址的项聚集在一起。
给定一个IP地址,我如何在这样的地图上计算其2D坐标(在0到1的范围内)?
发布于 2009-12-30 05:14:30
从本质上讲,您将使用位对MSB到LSB来分解数字。这对位告诉您位置是在左上(0)、左下(1)、右下(2)还是右上(3)象限中,比例随着数字的移动而变得更精细。
此外,您还需要跟踪“方向”。这是在您所处的比例下使用的缠绕;初始缠绕如上所述(UL、LL、LR、UR),根据您最终所在的象限,下一次缩放时的缠绕将从当前缠绕(旋转-90、0、0、+90)开始。
因此,您可以累积偏移量:
假设我从0,0开始,第一对给我2,我把偏移量移到0.5,0.5。右下角的缠绕和我最初的一样。下一对缩小了比例,所以我的调整长度将是0.25。
这对是3,所以我只平移我的x坐标,我在.75,.5。绕组现在被旋转了,我的下一次缩放将是(LR,LL,UL,UR)。小数现在是.125,依此类推,直到我的地址中的位数用完。
发布于 2009-12-30 05:16:17
我希望基于wikipedia code for a Hilbert curve,您可以跟踪您的当前位置(作为(x,y)坐标),并在访问了n个单元格之后返回该位置。然后,缩放到0..1的位置将取决于希尔伯特曲线在完成时的高度和宽度。
from turtle import left, right, forward
size = 10
def hilbert(level, angle):
if level:
right(angle)
hilbert(level - 1, -angle)
forward(size)
left(angle)
hilbert(level - 1, angle)
forward(size)
hilbert(level - 1, angle)
left(angle)
forward(size)
hilbert(level - 1, -angle)
right(angle)
诚然,这将是一种暴力解决方案,而不是封闭形式的解决方案。
https://stackoverflow.com/questions/1976864
复制相似问题