Curva de Hilbert en Prolog

La curva de Hilbert es una curva fractal descubierta por David Hilbert en 1891. Es un tipo de curva de Peano. Estas curvas tienen la peculiaridad de que cubren todo el plano de forma continua. Esto les otorga propiedades muy interesantes, una curva de Hilbert de nivel N es la aproximación enésima al límite de la curva, ocupando el mismo espacio pero cada vez rellenando más huecos, así hasta el infinito, donde sería un cuadrado sólido. El objetivo de este post no es entrar en detalle de sus propiedades matemáticas ni de sus aplicaciones, sino como podemos generar curvas de Hilbert bonitas usando Prolog.

SVG y DCGs

Para generar la curva de Hilbert de nivel N vamos a usar dos elementos claves. Uno, es el formato de imágenes vectoriales SVG. SVG es un formato, estándar por la W3C, para representar gráficos vectoriales, es decir gráficos que no se definen píxel a píxel sino mediante comandos. Es un formato de texto, basado en XML. Nuestro programa generará un SVG, que luego podremos visualizar en un navegador web o editar posteriormente en programas como Adobe Illustrator o Inkscape.

Cuando nos encontramos ante la tesitura de generar texto en Prolog, siempre es muy interesante valorar las opciones de usar DCGs. Las DCGs nos permiten describir listas de forma muy cómoda tal y como ya vimos hace tiempo. Además, en algunos sistemas como Scryer Prolog, los strings son listas de caracteres.

Generar XML con DCGs

¿Cómo podemos generar un XML con DCGs? Fácil, podemos definir unos non_terminal para las etiquetas. De esa forma, las etiquetas y los atributos se escribirán siempre correctamente.

:- use_module(library(dcgs)).
:- use_module(library(format)).

tag(T, GRBody) -->
    format_("<~w>", [T]),
    GRBody,
    format_("", [T]).

Cuando usamos este non_terminal vemos como el string de salida respeta la sintaxis XML.

?- phrase(tag(text, "Hola"), X).
   X = "Hola".

De forma general, también nos interesará añadir atributos y tener etiquetas que se cierran sin tener contenido en su interior.

tag(T, GRBody) -->
    format_("<~w>", [T]),
    GRBody,
    format_("", [T]).
    
tag(T, Attrs, GRBody) -->
    format_("<~w", [T]),
    tag_attrs(Attrs),
    ">",
    GRBody,
    format_("", [T]).

closed_tag(T, Attrs) -->
    format_("<~w", [T]),
    tag_attrs(Attrs),
    "/>".

tag_attrs([]) --> "".
tag_attrs([Attr|Attrs]) -->
    { Attr =.. [Name, Value], chars_si(Value) },
    format_(" ~w=\"", [Name]),
    Value,
    "\"",
    tag_attrs(Attrs).
tag_attrs([Attr|Attrs]) -->
    { Attr =.. [Name, Value], integer_si(Value) },
    format_(" ~w=\"~d\"", [Name, Value]),
    tag_attrs(Attrs).

Con estos non_terminals ya podemos escribir cualquier XML de forma cómoda.

?- phrase(tag(svg, [width(50), height(50), xmlns("http://www.w3.org/2000/svg")], (closed_tag(circle, [cx(50), cx(50), r(50)]), closed_tag(rect, [width(30), height(30)]))), X).
   X = ""
;  ... .

La imagen generada es la siguiente:

La curva de Hilbert

La curva de Hilbert es fractal. Eso quiere decir que los niveles N de la curva se construyen usando como bloques los niveles previos de N de la curva. Es decir, para elaborar la curva Hilbert N=3, tendremos que juntar trozos de varias curvas de Hilbert N = 2. Y una curva N = 2 a su vez de compone de varias curvas N = 1. Lógicamente tiene sentido pensar en idear una recursión para generarlas.

Un detalle de la curva de Hilbert es que las curvas que usamos para componer la curva grande, están rotadas. En SVG existen comandos de rotación, pero en este caso vamos a implementar la rotación "manualmente". Es decir, vamos a tener cuatro casos, uno para rotación. Cada caso tendrá su caso base, cuando N = 1, y los casos de N > 1. A los casos los llamo: a, b, c y d.

Adicionalmente, es necesario saber cuáles van a ser las dimensiones de nuestro SVG. Con otro pequeño predicado recursivo podemos calcular el tamaño del SVG de la curva N, teniendo en cuenta que he decidido que para las rectas serán de 8 unidades.

hilbert_width(1, 8).
hilbert_width(H, N) :-
    #H1 #= H - 1,
    hilbert_width(1, Base),
    hilbert_width(H1, N1),
    #N #= N1*2 + Base.

hilbert_only(H) -->
    { hilbert_width(H, Width) },
    tag(svg, [version("1.1"), width(Width), height(Width), xmlns("http://www.w3.org/2000/svg")], hilbert_a(H, 1, Width, 0, Width, Width, "black")).

hilbert_a(1, F, X0, Y0, X0, Y, Color) -->
    { #X #= X0 - 8 * F, #Y #= Y0 + 8 * F },
    line(X0, Y0, X, Y0, Color),
    line(X, Y0, X, Y, Color),
    line(X, Y, X0, Y, Color).

hilbert_a(H, F, X0, Y0, X0, Y, Color) -->
    { #H1 #= H - 1, #X2 #= #X1 - 8 * F, #Y3 #= #Y2 + 8 * F},
    hilbert_b(H1, F, X0, Y0, X1, Y1, Color),
    line(X1, Y1, X2, Y1, Color),
    hilbert_a(H1, F, X2, Y1, X3, Y2, Color),
    line(X3, Y2, X3, Y3, Color),
    hilbert_a(H1, F, X3, Y3, X4, Y4, Color),
    line(X4, Y4, X1, Y4, Color),
    hilbert_c(H1, F, X1, Y4, X0, Y, Color).

hilbert_b(1, F, X0, Y0, X, Y0, Color) -->
    { #X #= X0 - 8 * F, #Y #= Y0 + 8 * F},
    line(X0, Y0, X0, Y, Color),
    line(X0, Y, X, Y, Color),
    line(X, Y, X, Y0, Color).

hilbert_b(H, F, X0, Y0, X, Y0, Color) -->
    { #H1 #= H - 1, #Y2 #= #Y1 + 8 * F, #X3 #= #X2 - 8 * F},
    hilbert_a(H1, F, X0, Y0, X1, Y1, Color),
    line(X1, Y1, X1, Y2, Color),
    hilbert_b(H1, F, X1, Y2, X2, Y3, Color),
    line(X2, Y3, X3, Y3, Color),
    hilbert_b(H1, F, X3, Y3, X, Y4, Color),
    line(X, Y4, X, Y1, Color),
    hilbert_d(H1, F, X, Y1, X, Y0, Color).

hilbert_c(1, F, X0, Y0, X, Y0, Color) -->
    { #X #= X0 + 8 * F, #Y #= Y0 - 8 * F },
    line(X0, Y0, X0, Y, Color),
    line(X0, Y, X, Y, Color),
    line(X, Y, X, Y0, Color).

hilbert_c(H, F, X0, Y0, X, Y0, Color) -->
    { #H1 #= H - 1, #Y2 #= #Y1 - 8 * F, #X3 #= #X2 + 8 * F},
    hilbert_d(H1, F, X0, Y0, X1, Y1, Color),
    line(X1, Y1, X1, Y2, Color),
    hilbert_c(H1, F, X1, Y2, X2, Y3, Color),
    line(X2, Y3, X3, Y3, Color),
    hilbert_c(H1, F, X3, Y3, X, Y4, Color),
    line(X, Y4, X, Y1, Color),
    hilbert_a(H1, F, X, Y1, X, Y0, Color).

hilbert_d(1, F, X0, Y0, X0, Y, Color) -->
    { #X #= X0 + 8 * F, #Y #= Y0 - 8 * F},
    line(X0, Y0, X, Y0, Color),
    line(X, Y0, X, Y, Color),
    line(X, Y, X0, Y, Color).

hilbert_d(H, F, X0, Y0, X0, Y, Color) -->
    { #H1 #= H - 1, #X2 #= #X1 + 8 * F, #Y3 #= #Y2 - 8 * F},
    hilbert_c(H1, F, X0, Y0, X1, Y1, Color),
    line(X1, Y1, X2, Y1, Color),
    hilbert_d(H1, F, X2, Y1, X3, Y2, Color),
    line(X3, Y2, X3, Y3, Color),
    hilbert_d(H1, F, X3, Y3, X4, Y4, Color),
    line(X4, Y4, X1, Y4, Color),
    hilbert_b(H1, F, X1, Y4, X0, Y, Color).

    
line(X1, Y1, X2, Y2, Color) -->
    closed_tag(line, [x1(X1), x2(X2), y1(Y1), y2(Y2), stroke(Color), 'stroke-width'("1")]).

Con esto podemos llamar a hilbert_only y obtener la curva N de Hilbert.

Curva N = 6

Generar múltiples curvas superpuestas

Algo que queda muy bonito es superponer las curvas de N niveles, una encima de otra. Esto supondría que habría líneas que se transitarían muchas veces. Una opción mejor es ir escalando las curvas y centrándolas. Para eso era la variable F que he usado antes. Juntando todos estos componentes y dibujando cada curva de un color diferente, podemos llegar a esto:

main :-
    phrase_to_file(hilbert_all(["black", "blue", "green", "red", "yellow"]), "hilbert.svg").

hilbert_all(Colors) -->
    {
	length(Colors, H),
	hilbert_width(H, Width),
	#W1 #= Width + 20,
	phrase(format_("-10 -10 ~d ~d", [W1, W1]), ViewBox),
	Colors = [Color|Colors1]
    },
    tag(svg, [version("1.1"), width(Width), height(Width), viewBox(ViewBox), xmlns("http://www.w3.org/2000/svg")],(
	    hilbert_a(H, 1, Width, 0, Width, Width, Color),
	    hilbert_sub(Colors1, 1, Width))
       ).

hilbert_sub([], _, _) --> [].
hilbert_sub(Colors, F, TotalWidth) -->
    {
	length(Colors, N),
	#F1 #= F * 2,
	hilbert_width(N, Width),
	#FWidth #= Width * F1,
	#HalfF #= (TotalWidth - FWidth) / 2,
	phrase(format_("translate(~d, ~d)", [HalfF, HalfF]), Transform),
	Colors = [Color|Colors1]
    },
    tag(g, [transform(Transform)], hilbert_a(N, F1, FWidth, 0, FWidth, FWidth, Color)),
    hilbert_sub(Colors1, F1, TotalWidth).

Que da como resultado esta bonita imagen.