Реализации алгоритмов/Губка Менгера: различия между версиями
Содержимое удалено Содержимое добавлено
м Рекурсивный метод |
|||
Строка 3:
== Построение итеративным методом на [[w:en:Geometric Description Language|GDL]] для [[w:ArchiCAD|ArchiCAD]] ==
Алгоритм итеративного метода основан на операции твердотельного вычитания (subtraction). В языке GDL такая операция реализуется с помощью групп (group).
# Строится "группа-уменьшаемое". Она состоит из одного единичного куба (стороной 1 с центром в начале координат).
# Строится "группа-вычитаемое". Она включает "стержни", которые будут вычитаться из куба. Размер и количество зависит от итерации.
# Проводится операцию твердотельного вычитания.
Данный метод весьма требователен к ресурсам:
{| class="standard"
|-
!Итерация||0||1||2||3||4||5||6||7||8||9||10
|-
|Кубов||1||20||400||8K||160K||3.2M||64M||1.28G||25.6G||512G||10.24T
|-
|Граней||6||120||2.4K||48K||960K||19.2M||384M||7.68G||153.6G||3.072T||61.44T
|-
|Треугольников||12||240||4.8K||96K||1.92K||38.4M||768M||15.36G||307.2G||6.144T||122.88T
|-
|Рёбер||12||240||4.8K||96K||1.92K||38.4M||768M||15.36G||307.2G||6.144T||122.88T
|-
|Вершин||8||160||3.2K||64K||1.28M||25.6M||512M||10.24G||204.8G||4.096T||81.92T
|}
Код оптимизирован под наглядность, а не производительность. В среде ArchiCAD 19 и 20 корректно исполняются 4 итерации. В среде ArchiCAD 13 (64 бит) корректно исполняются только 2 итерации.
<source lang="gdl">
Строка 70 ⟶ 89 :
PLACEGROUP Menger
CUTEND
</source>
== Построение рекурсивным методом на [[w:en:Geometric Description Language|GDL]] для [[w:ArchiCAD|ArchiCAD]] ==
Код оптимизирован под наглядность, поэтому требователен к ресурсам. В среде ArchiCAD 13, 19 и 20 корректно исполняются 4 итерации.
Оптимально для работы 3 итерации.
Для визуализации можно использовать текстуру [[w:Ковёр Серпиского|ковра Серпинского]]
Поскольку язык GDL не предполагает процедур, для рекурсии используем переходы по меткам.
# Сразу переходим на i-ю метку
# i-я метка устанавливает параметры для метки (i-1) и переходит на метку рекурсивного алгоритма
# Метка рекурсивного алгоритма устанавливает позицию (x, y, z) и переходит на метку i-1
# ...
# Метка 0 строит единичный куб
Рекурсивный алгоритм описывает 3D-матрицу, по которой строится каждая итерация губки Менгера:
<math>\begin{pmatrix} 1 & 1 & 1\\1 & 0 & 1\\1 & 1 & 1\end{pmatrix}</math>
<math>\begin{pmatrix} 1 & 0 & 1\\0 & 0 & 0\\1 & 0 & 1\end{pmatrix}</math>
<math>\begin{pmatrix} 1 & 1 & 1\\1 & 0 & 1\\1 & 1 & 1\end{pmatrix}</math>
<source lang="gdl">
!!!3D Script
GOSUB i
END
4:
n = 3
d = 27
GOSUB 100
RETURN
3:
n = 2
d = 9
GOSUB 100
n = 3
d = 27
RETURN
2:
n = 1
d = 3
GOSUB 100
n = 2
d = 9
RETURN
1:
n = 0
d = 1
GOSUB 100
n = 1
d = 3
RETURN
0:
BLOCK 1,1,1
RETURN
100:
GOSUB n !111
AddX d !1: 2,1,1
GOSUB n !211
AddX d !2: 3,1,1
GOSUB n !311
DEL 2 !0: 1,1,1
AddY d !1: 1,2,1
GOSUB n !121
AddX 2*d !2: 3,2,1
GOSUB n !321
DEL 1 !1: 1,2,1
AddY d !2: 1,3,1
GOSUB n !131
AddX d !3: 2,3,1
GOSUB n !231
AddX d !4: 3,3,1
GOSUB n !331
DEL 4 !0: 1,1,1
AddZ d !1: 1,1,2
GOSUB n !112
AddX 2*d !2: 3,1,2
GOSUB n !312
DEL 1 !1: 1,1,2
AddY 2*d !2: 1,3,2
GOSUB n !132
AddX 2*d !3: 3,3,2
GOSUB n !332
DEL 2 !1: 1,1,2
AddZ d !2: 1,1,3
GOSUB n !113
AddX d !3: 2,1,3
GOSUB n !213
AddX d !4: 3,1,3
GOSUB n !313
DEL 2 !2: 1,1,3
AddY d !3: 1,2,3
GOSUB n !123
AddX 2*d !4: 3,2,3
GOSUB n !323
DEL 1 !3: 1,2,3
AddY d !4: 1,3,3
GOSUB n !133
AddX d !5: 2,3,3
GOSUB n !233
AddX d !6: 3,3,3
GOSUB n !333
DEL 6 !0
RETURN
</source>
| |||