Матрица статей        Список статей        Всячина        Контакты       

Кривая Гильберта


Кривая Гильберта

program Gilb;

uses Crt, Graph;

const
	u =10;
	p = 5;
	
var
  i: Integer;
  gd, gm : Integer;

procedure a(i: Integer); forward;

procedure b(i: Integer); forward;

procedure c(i: Integer); forward;

procedure d(i: Integer); forward;

procedure a(i: Integer);

begin
	if i > 0 then
	begin
		d(i - 1);
		LineRel( + u, 0);
		a(i - 1);
		LineRel(0, u);
		a(i - 1);
		LineRel(-u, 0);
		c(i - 1)
	end
end;

procedure b(i: integer);

begin
	if i > 0 then
	begin
		c(i - 1);
		LineRel(-u, 0);
		b(i - 1);
		LineRel(0, -u);
		b(i - 1);
		LineRel(u, 0);
		d(i - 1)
	end
end;

procedure c(i: integer);

begin
	if i > 0 then
	begin
		b(i - 1);
		LineRel(0, -u);
		c(i - 1);
		LineRel(-u, 0);
		c(i - 1);
		LineRel(0, u);
		a(i - 1)
	end
end;

procedure d(i: integer);

begin
	if i > 0 then
	begin
		a(i - 1);
		LineRel(0, u);
		d(i - 1);
		LineRel(u, 0);
		d(i - 1);
		LineRel(0, -u);
		b(i - 1)
	end
end;

begin
	gd := Detect;
	InitGraph(gd,gm,'c:\bp\bgi');
	MoveTo(100, 100);
	a(p);
	ReadKey;
	CloseGraph
end.

Дальше идёт фрактальный кусочек моей хабрастатьи Рисуем картинки с помощью кривой Гильберта .

Листая книгу «Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая» М. Шредера, можно наткнуться на следующую иллюстрацию:

Кривая Гильберта

Выглядит это очень симпатично, и понятно, что такое можно сделать с произвольным изображением. О том, как это было нарисовано, в книге не рассказывается, но не сложно догадаться самому.

Для начала нужно взять алгоритм построения кривой Гильберта. Но не с помощью каких-нибудь L-систем, а честный рекурсивный алгоритм. А дальше модифицируем его следующим образом. Если яркость квадратика больше заданного порога и в четырёх его подквадратиках кривую рисовать не нужно, то считаем, что и в самом квадратике рисовать кривую не нужно. Хотя наверное проще понять из кода, приведённого ниже.

Point2D[] drawHilbertCurve(Point2D p, double size, int d) {
    Point2D q = new Point2D.Double(
            p.getX() + size * sqrt(2) * cos(PI * (d + 0.5) / 2),
            p.getY() + size * sqrt(2) * sin(PI * (d + 0.5) / 2));
    if (size <= 2) {
        if (blockIsWhite(p, q)) {
            return null;
        } else {
            Point2D cc = new Point2D.Double(
                    p.getX() + size * sqrt(2) * cos(PI * (d + 0.5) / 2) / 2,
                    p.getY() + size * sqrt(2) * sin(PI * (d + 0.5) / 2) / 2);
            return new Point2D[]{cc, cc};
        }
    } else {
        Point2D cl = new Point2D.Double(
                p.getX() + size * cos(PI * (d + 1) / 2) / 2,
                p.getY() + size * sin(PI * (d + 1) / 2) / 2);
        Point2D cc = new Point2D.Double(
                p.getX() + size * sqrt(2) * cos(PI * (d + 0.5) / 2) / 2,
                p.getY() + size * sqrt(2) * sin(PI * (d + 0.5) / 2) / 2);
        Point2D br = new Point2D.Double(
                p.getX() + size * cos(PI * d / 2),
                p.getY() + size * sin(PI * d / 2));
        Point2D[] p1 = drawHilbertCurve(cl, size / 2, d - 1);
        Point2D[] p2 = drawHilbertCurve(cl, size / 2, d);
        Point2D[] p3 = drawHilbertCurve(cc, size / 2, d);
        Point2D[] p4 = drawHilbertCurve(br, size / 2, d + 1);
        if (p1 == null && p2 == null && p3 == null && p4 == null 
            && blockIsWhite(p, q)) {
            return null;
        } else {
            if (p1 == null) {
                p1 = new Point2D[2];
                p1[0] = p1[1] = new Point2D.Double(
                        cl.getX() + size * sqrt(2) * cos(PI * (d - 0.5) / 2) / 4,
                        cl.getY() + size * sqrt(2) * sin(PI * (d - 0.5) / 2) / 4);
            }
            if (p2 == null) {
                p2 = new Point2D[2];
                p2[0] = p2[1] = new Point2D.Double(
                        cl.getX() + size * sqrt(2) * cos(PI * (d + 0.5) / 2) / 4,
                        cl.getY() + size * sqrt(2) * sin(PI * (d + 0.5) / 2) / 4);
            }
            if (p3 == null) {
                p3 = new Point2D[2];
                p3[0] = p3[1] = new Point2D.Double(
                        cc.getX() + size * sqrt(2) * cos(PI * (d + 0.5) / 2) / 4,
                        cc.getY() + size * sqrt(2) * sin(PI * (d + 0.5) / 2) / 4);
            }
            if (p4 == null) {
                p4 = new Point2D[2];
                p4[0] = p4[1] = new Point2D.Double(
                        br.getX() + size * sqrt(2) * cos(PI * (d + 1.5) / 2) / 4,
                        br.getY() + size * sqrt(2) * sin(PI * (d + 1.5) / 2) / 4);
            }

            drawLine(p1[0], p2[0]);
            drawLine(p2[1], p3[0]);
            drawLine(p3[1], p4[1]);
        }
        return new Point2D[]{p1[1], p4[0]};
    }
}

boolean blockIsWhite(Point2D p, Point2D q) {
    int l = (int) min(p.getX(), q.getX());
    int r = (int) max(p.getX(), q.getX());
    int t = (int) min(p.getY(), q.getY());
    int b = (int) max(p.getY(), q.getY());

    double c = 0;
    for (int i = l; i < r; ++i) {
        for (int j = t; j < b; ++j) {
            c += (srcImage.getRGB(i, j) & 0x0000FF) / 255.0;
        }
    }
    return c / ((b - t) * (r - l)) > threshold * (1 - log(2) / log(b - t));
}

Перед тем, как изображение скармливалось программке, оно переводилось в оттенки серого и опытным путём подстраивалась яркость и контрастность. Например, вот что получилось, когда программку натравили на тукса и на котёнка по имени Гав:

Кривая Гильберта Кривая Гильберта

Смотрите также:

Ссылки: