Доброго времени суток.
Необходимо реализовать рекурсивную и нерекурсивную реализацию построения кривой Серпинского.
Рекурсивное построение не составило большого труда, а вот найти конечный алгоритм для нерекурсивной реализации (понятный для имплементации) не получилось (Только в книге Род Стивене - "Delphi Готовые алгоритмы").
Может ли кто-нибудь скинуть материалы где можно почитать про нерекурсивную имплементацию построения кривых Серпинского?
Реализация Рекурсивного алгоритма:
static private void Sierpinski(int depth, float dx, float dy, Graphics gr = null){
float x = dx;
float y = dy;
drawA(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, dx, dy);
drawB(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -dx, dy);
drawC(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -dx, -dy);
drawD(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, dx, -dy);
}
static private void drawA(Graphics gr, int depth, ref float x, ref float y, float dx, float dy)
{
if (depth > 0)
{
--depth;
drawA(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, dx, dy);
drawB(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, 2 * dx, 0);
drawD(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, dx, -dy);
drawA(gr, depth, ref x, ref y, dx, dy);
}
}
static private void drawB(Graphics gr, int depth, ref float x, ref float y, float dx, float dy)
{
if (depth > 0)
{
--depth;
drawB(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -dx, dy);
drawC(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, 0, 2 * dy);
drawA(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, dx, dy);
drawB(gr, depth, ref x, ref y, dx, dy);
}
}
static private void drawC(Graphics gr, int depth, ref float x, ref float y, float dx, float dy)
{
if (depth > 0)
{
--depth;
drawC(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -dx, -dy);
drawD(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -2 * dx, 0);
drawB(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -dx, dy);
drawC(gr, depth, ref x, ref y, dx, dy);
}
}
static private void drawD(Graphics gr, int depth, ref float x, ref float y, float dx, float dy)
{
if (depth > 0)
{
--depth;
drawD(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, dx, -dy);
drawA(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, 0, -2 * dy);
drawC(gr, depth, ref x, ref y, dx, dy);
drawLine(gr, ref x, ref y, -dx, -dy);
drawD(gr, depth, ref x, ref y, dx, dy);
}
}
Реализация функции drawLine()
static private void drawLine(Graphics gr, ref float x, ref float y, float dx, float dy)
{
if (gr != null)
gr.DrawLine(Pens.Black, x, y, x + dx, y + dy);
x += dx;
y += dy;
}
Ответ
Воспользуемся стандартным подходом: перепишем функцию в виде набора заданий и управляющего цикла, который выполняет задания по одному. Вместо рекурсивного вызова функций будем добавлять новые задания в стек этих самых заданий. Этим самым мы как бы заменяем стек вызовов стеком заданий.
Для нашего случая, заведём структуру данных, описывающую одно задание. Одним заданием у нас будет вызов drawA, drawB, drawC, drawD или drawLine. Получаем следующую структуру:
struct DrawTask
{
public DrawTask(char type, int depth, float dx = 0, float dy = 0)
{
Type = type;
Depth = depth;
Linedx = dx;
Linedy = dy;
}
public char Type; // A, B, C, D или L
public int Depth;
public float Linedx; // эти параметры нужны лишь для задания типа L
public float Linedy;
}
Теперь нам нужна очередь заданий и её интерпретатор:
static void Sierpinski_NR(int depth, float dx, float dy, Graphics gr = null)
{
Stack taskStack = new Stack();
float x = dx;
float y = dy;
// загружаем задания в стек в обратном порядке
taskStack.Push(new DrawTask('L', depth, dx, -dy));
taskStack.Push(new DrawTask('D', depth));
taskStack.Push(new DrawTask('L', depth, -dx, -dy));
taskStack.Push(new DrawTask('C', depth));
taskStack.Push(new DrawTask('L', depth, -dx, dy));
taskStack.Push(new DrawTask('B', depth));
taskStack.Push(new DrawTask('L', depth, dx, dy));
taskStack.Push(new DrawTask('A', depth));
// пока есть задание, достаём его и выполняем
// в результате выполнения в стеке могут оказаться подзадания
while (taskStack.Count > 0)
{
var currentTask = taskStack.Pop();
switch (currentTask.Type)
{
case 'A':
drawA_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
break;
case 'B':
drawB_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
break;
case 'C':
drawC_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
break;
case 'D':
drawD_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
break;
case 'L':
drawLine(gr, ref x, ref y, currentTask.Linedx, currentTask.Linedy);
break;
}
}
}
Процедуру A имплементируем таким же образом. Она сама не делает ничего, просто добавляет в стек подзадания:
static void drawA_NR(Graphics gr, int depth, ref float x, ref float y, float dx, float dy,
Stack taskStack)
{
if (depth > 0)
{
--depth;
// помещаем в стек в обратном порядке
taskStack.Push(new DrawTask('A', depth));
taskStack.Push(new DrawTask('L', depth, dx, -dy));
taskStack.Push(new DrawTask('D', depth));
taskStack.Push(new DrawTask('L', depth, 2 * dx, 0));
taskStack.Push(new DrawTask('B', depth));
taskStack.Push(new DrawTask('L', depth, dx, dy));
taskStack.Push(new DrawTask('A', depth));
}
}
Остальные процедуры реализуются аналогично:
static void drawB_NR(Graphics gr, int depth, ref float x, ref float y, float dx, float dy,
Stack taskStack)
{
if (depth > 0)
{
--depth;
taskStack.Push(new DrawTask('B', depth));
taskStack.Push(new DrawTask('L', depth, dx, dy));
taskStack.Push(new DrawTask('A', depth));
taskStack.Push(new DrawTask('L', depth, 0, 2 * dy));
taskStack.Push(new DrawTask('C', depth));
taskStack.Push(new DrawTask('L', depth, -dx, dy));
taskStack.Push(new DrawTask('B', depth));
}
}
static void drawC_NR(Graphics gr, int depth, ref float x, ref float y, float dx, float dy,
Stack taskStack)
{
if (depth > 0)
{
--depth;
taskStack.Push(new DrawTask('C', depth));
taskStack.Push(new DrawTask('L', depth, -dx, dy));
taskStack.Push(new DrawTask('B', depth));
taskStack.Push(new DrawTask('L', depth, -2 * dx, 0));
taskStack.Push(new DrawTask('D', depth));
taskStack.Push(new DrawTask('L', depth, -dx, -dy));
taskStack.Push(new DrawTask('C', depth));
}
}
static void drawD_NR(Graphics gr, int depth, ref float x, ref float y, float dx, float dy,
Stack taskStack)
{
if (depth > 0)
{
--depth;
taskStack.Push(new DrawTask('D', depth));
taskStack.Push(new DrawTask('L', depth, -dx, -dy));
taskStack.Push(new DrawTask('C', depth));
taskStack.Push(new DrawTask('L', depth, 0, -2 * dy));
taskStack.Push(new DrawTask('A', depth));
taskStack.Push(new DrawTask('L', depth, dx, -dy));
taskStack.Push(new DrawTask('D', depth));
}
}
