1

我一直在阅读有关 L-Systems 的文章，特别是 Hilbert Space 填充曲线。我有兴趣编写一个函数来将上三角矩阵坐标转换为一维空间填充曲线坐标。

通常的希尔伯特曲线是用一阶曲线推导出来的：

一阶希尔伯特曲线

然后迭代应用一系列产生式规则，得到一个可逆的一维坐标系。

希尔伯特曲线产生规则 二阶希尔伯特曲线 三阶希尔伯特曲线

我已经成功实现了维基百科上列出的映射算法，

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }

        //Swap x and y
        int t  = *x;
        *x = *y;
        *y = t;
    }
}

//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
    }
    return d;
}

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

但是，我需要在此过程中再添加两条一阶曲线：一条是直角，另一条是楔形。这两条新曲线不需要旋转或反射，结合通常的希尔伯特一阶曲线（带有旋转和反射），可以填充一个上三角矩阵（见我下面的草图）：

在此处输入图像描述

即红色直角的左上角再次变成直角，右上角变成希尔伯特曲线，直角的右下部分变成楔形，以此类推。

我想实现上面提出的 L-System 转换，但是关于 L-Systems 的每个教程都是关于从零开始，然后绘制一条填充空间而不交叉自身的线（即编写一串步骤来跟踪整个空间，而不是将空间中的坐标子集转换为一维对应物）。

谁能提供任何关于我如何将这些新的基本曲线合并到现有代码中的直觉？是否有任何资源可以解释 L-System 转换（相对于绘图系统），以及如何在代码中构建它们？

4

0 回答 0