Кривая Минковского

Кривая Минковского — классический геометрический фрактал, предложенный Минковским. Инициатором является отрезок, а генератором является ломаная из восьми звеньев (два равных звена продолжают друг друга) — см. рис., где в качестве генератора использован «биполярный скачок»

Квадратичный остров Коха типа 1 из четырёх кривых Минковского, расположенных в многоугольнике

Квадратичный остров Коха типа 2 из четырёх кривых Минковского, расположенных в многоугольнике

Свойства

• Кривая Минковского нигде не дифференцируема и не спрямляема.
• Кривая Минковского не имеет самопересечений.
• Кривая Минковского имеет Хаусдорфову размерность $\ln 8/\ln 4\ =3/2$ (поскольку она состоит из восьми равных частей, каждая из которых подобна всей кривой с коэффициентом подобия 1/4). В частности,
• Кривая Минковского имеет нулевую меру Лебега.

Построение через систему Линденмайера

переменные: F

константы: + −

старт: F

правило: (F → F−F+F+FF−F−F+F)

угол: 90°

Здесь F означают «рисуем отрезок», + означает «повернуть вправо на угол», а − означает «повернуть влево на угол».

Примеры алгоритма

Python

Пример алгоритма на Python с помощью модуля turtle

from turtle import *
 
 
def start(x: float):
    """This function clears window and make turtle go to start"""
    clear()
    penup()
    x = x if x < 0 else -x
    goto(x, 0)
    pendown()
 
 
def curve_minkowski(length: float, iterations: int):
    """This function draw Minkowski's curve"""
 
    if iterations == 0:
        forward(length * 4)
    else:
        curve_minkowski(length/4, iterations - 1)
        left(90)
        curve_minkowski(length/4, iterations - 1)
        right(90)
        curve_minkowski(length/4, iterations - 1)
        right(90)
        curve_minkowski(length/4, iterations - 1)
        curve_minkowski(length/4, iterations - 1)
        left(90)
        curve_minkowski(length/4, iterations - 1)
        left(90)
        curve_minkowski(length/4, iterations - 1)
        right(90)
        curve_minkowski(length/4, iterations - 1)
 
 
LENGTH = 100       # длина линии
 
ITERATION = 3      # номер итерации
 
start(LENGTH * 2)
 
curve_minkowski(LENGTH, ITERATION)
 
exitonclick()    # функция чтобы программа не завершалась сразу

Пример алгоритма на Python с помощью системы Линденмайера

 
import turtle

turtle.hideturtle()
turtle.tracer(0)
turtle.penup()
turtle.setposition(-150, 0)
turtle.pendown()

axiom, tempAx, logic, iterations = 'F', '', {'F': 'F-F+F+FF-F-F+F'}, 3

for i in range(iterations):
    for j in axiom:
        tempAx += logic[j] if j in logic else j
    axiom, tempAx = tempAx, ''

for k in axiom:
    if k == '+':
        turtle.left(90)
    elif k == '-':
        turtle.right(90)
    else:
        turtle.forward(5)

turtle.update()
turtle.mainloop()

Пример алгоритма на PHP

<?php
    $i = 2;
    
    $image = imagecreatetruecolor(600, 400);
    imagefilledrectangle($image, 0, 0, imagesx($image) - 1, imagesy($image) - 1,
            imagecolorresolve($image, 255, 255, 255));
    $color = imagecolorresolve($image, 0, 0, 0);

    drawMinkowski($image, 0, imagesy($image) / 2, imagesx($image), imagesy($image) / 2, $i, $color);
    
    /**
     * Draws minkowski curve between two points.
     * @return void
     */
    function drawMinkowski($image, $xa, $ya, $xi, $yi, $i, $color) {
        if($i == 0)
            imageline($image, $xa, $ya, $xi, $yi, $color);
        else {
            //     C---D
            //     |   |
            // A---B   E   H---I
            //         |   |
            //         F---G
            
            $xb = $xa + ($xi - $xa) * 1/4;
            $yb = $ya + ($yi - $ya) * 1/4;

            $xe = $xa + ($xi - $xa) * 2/4;
            $ye = $ya + ($yi - $ya) * 2/4;
            
            $xh = $xa + ($xi - $xa) * 3/4;
            $yh = $ya + ($yi - $ya) * 3/4;

            $cos90 = 0;
            $sin90 = -1;
            $xc = $xb + ($xe - $xb) * $cos90 - $sin90 * ($ye - $yb);
            $yc = $yb + ($xe - $xb) * $sin90 + $cos90 * ($ye - $yb);

            $xd = $xc + ($xe - $xb);
            $yd = $yc + ($ye - $yb);
            
            $sin90 = 1;
            $xf = $xe + ($xh - $xe) * $cos90 - $sin90 * ($yh - $ye);
            $yf = $ye + ($xh - $xe) * $sin90 + $cos90 * ($yh - $ye);

            $xg = $xf + ($xh - $xe);
            $yg = $yf + ($yh - $ye);

            drawMinkowski($image, $xa, $ya, $xb, $yb, $i - 1, $color);
            drawMinkowski($image, $xb, $yb, $xc, $yc, $i - 1, $color);
            drawMinkowski($image, $xc, $yc, $xd, $yd, $i - 1, $color);
            drawMinkowski($image, $xd, $yd, $xe, $ye, $i - 1, $color);
            drawMinkowski($image, $xe, $ye, $xf, $yf, $i - 1, $color);
            drawMinkowski($image, $xf, $yf, $xg, $yg, $i - 1, $color);
            drawMinkowski($image, $xg, $yg, $xh, $yh, $i - 1, $color);
            drawMinkowski($image, $xh, $yh, $xi, $yi, $i - 1, $color);
        }
    }

    header('Content-type: image/png');
    imagepng($image);
    imagedestroy($image);
?>

Литература

• Вишневский В. М., Ляхов А. И., Портной С. Л., Шахнович И. В. Широкополосные беспроводные сети передачи информации. — М.: Техносфера. — 2005.- C. 498—569.

Ссылки

• «Minkowski Sausage» — пример интерактивного построения кривой Минковского