Реализации алгоритмов/Треугольник Серпинского

Треугольник Серпинского

Треугольник Серпинского — фрактал, один из двумерных аналогов множества Кантора, предложенный польским математиком Вацлавом Серпинским в 1915 году.

Построение рекурсивным методом на GDL для ArchiCAD

Поскольку язык GDL не предполагает процедур, для рекурсии используем переходы по меткам.

1. Сразу переходим на i-ю метку
2. i-я метка устанавливает параметры для метки (i-1) и переходит на метку рекурсивного алгоритма
3. Метка рекурсивного алгоритма устанавливает позицию (x, y) и переходит на метку i-1
4. ...
5. Метка 0 строит треугольник

Рекурсивный алгоритм описывает 3D-матрицу, по которой строится каждая итерация треугольника Серпинского.

В среде ArchiCAD вызываем интерфейс разработки библиотечных объектов (Ctrl+Shift+O). На вкладке «Параметры» задаём целую переменную i – число итераций.

Переходим в 3D-скрипт.

!!!3D Script

xA = 0			!COS(90)
yA = 1			!SIN(90)
xB = COS(210)	!-0.86602540378
yB = -0.5		!SIN(210)
xC = COS(330)	!0.86602540378
yC = -0.5		!SIN(330)

GOSUB i

END

4:
	n = 3
	dX1 = 8*xC
	dX2 = 16*xC
	dY = 12
	GOSUB 100
RETURN

3:
	n = 2
	dX1 = 4*xC
	dX2 = 8*xC
	dY = 6
	GOSUB 100
	n = 3
	dX1 = 8*xC
	dX2 = 16*xC
	dY = 12
RETURN

2:
	n = 1
	dX1 = 2*xC
	dX2 = 4*xC
	dY = 3
	GOSUB 100
	n = 2
	dX1 = 4*xC
	dX2 = 8*xC
	dY = 6
RETURN

1:
	n = 0
	dX1 = xC
	dX2 = 2*xC
	dY = 1.5
	GOSUB 100
	n = 1
	dX1 = 2*xC
	dX2 = 4*xC
	dY = 3
RETURN

0:
	PLANE 3, xA, yA, 0, xB, yB, 0, xC, yC, 0
RETURN

100:
	GOSUB n
	AddX dX2
	GOSUB n
	DEL 1
	AddX dX1
	AddY dY
	GOSUB n
	DEL 2
RETURN

Построение методом хаоса на VBA для CAD-систем

Построение треугольника Серпинского методом хаоса

Sub Sieve()
Dim pointObj As AcadPoint
Dim location(0 To 2) As Double	'Координаты искомых точек xi, yi, zi; zn = 0

Dim i As Long		'Счётчик итераций
Dim R As Double		'Случайность
Dim A(0 To 1) As Double 'Координаты вершин
Dim B(0 To 1) As Double
Dim C(0 To 1) As Double

'Треугольник может быть произвольным
A(0) = 0		'Cos(pi / 2)
A(1) = 1		'Sin(pi / 2)
B(0) = -0.866		'Cos(7 * pi / 6)
B(1) = -0.5		'Sin(7 * pi / 6)
C(0) = 0.866		'Cos(11 * pi / 6)
C(1) = -0.5		'Sin(11 * pi / 6)

For i = 1 To 100000	
 R = Rnd(1)
 If R < 0.33 Then
  location(0) = (location(0) + A(0)) / 2
  location(1) = (location(1) + A(1)) / 2
 ElseIf R < 0.67 Then
  location(0) = (location(0) + B(0)) / 2
  location(1) = (location(1) + B(1)) / 2
 Else
  location(0) = (location(0) + C(0)) / 2
  location(1) = (location(1) + C(1)) / 2
End If
Set pointObj = ThisDrawing.ModelSpace.AddPoint(location)
Next i
End Sub

Построение на JavaScript

Картинка генерируемая кодом на JavaScript

var k=Math.sqrt(3)/2; var S=16; var H=512; var W=Math.floor(H/k);
document.body.innerHTML=('<canvas id="C" width="'+W+'" height="'+H+'"></canvas>');
var canvas = document.getElementById('C');
var ctx = canvas.getContext('2d');
ctx.fillRect(0, 0, W, H);
for(var x = 0;x<=Math.floor(W/2);x++) {
  for(var y = 0;y<H;y++) {
    var A = y;          var a = A%S;
    var B = y/2+x*k;    var b = B%S;
    var C = y/2-x*k;    var c = C%S;
    if(a>b&&C>0&&B>0) {
      if ((B/S)&(C/S)) ctx.fillStyle='#ff0';
      else ctx.fillStyle='#000';
    } else if(a<b&&C>0&&B>0) {
      ctx.fillStyle='#0f8';
    } else ctx.fillStyle='#fff';
    ctx.fillRect(Math.floor(W/2)-x, y, 1, 1);
    if (x!=0) ctx.fillRect(Math.floor(W/2)+x, y, 1, 1);
  }
}

См. также

• Размер и размерность
• Ковёр Серпинского
• Губка Менгера