Boundary Scanning
Robert P. Munafo, 1993 Feb 3.
Boundary Scanning is an Adjacency Optimization whereby a grid is traversed
using a recursive or queue-oriented method similar to maze-solving
algorithms. Starting generally at one pixel on an edge or corner of the
grid, neighboring pixels are evaluated if they are adjacent to a pixel that
has been evaluated and if they are either on the edge of the grid or if
they have at least two neighbors which have been evaluated and are of
differing values.
Boundary scanning works well for Mandelbrot and Julia images, and will
sometimes miss features, but only if the maximum Dwell is too low.
The algorithm is fairly complex, because of many different types of tests
that must be made.
Program MANDELBROT-BS-1
~~~~~~~~~~~~~~~~~~~~~~~
COMMENT "The Boundary Scanning algorithm, applied to the Mandelbrot
Set."
DEFINE-TYPE grid_element
next_x: INTEGER;
next_y: INTEGER;
dwell: INTEGER;
active: BOOLEAN;
END DEFINE
DECLARE grid: ARRAY[1 TO grid_width, 1 TO grid_height] OF grid_element
SUBROUTINE ADD_POINT
PARAM x: INTEGER
PARAM y: INTEGER
BEGIN
IF ((0 < x <= GRID_WIDTH) AND (0 < y <= GRID_HEIGHT) ) THEN
IF (grid[x,y].dwell EQUALS -1) THEN
LET grid[x,y].active = TRUE
LET grid[x,y].next_x = first_x
LET grid[x,y].next_y = first_y
LET first_x = x
LET first_y = y
END IF
END IF
END SUBROUTINE
SUBROUTINE ADD_4
PARAM x: INTEGER
PARAM y: INTEGER
PARAM dx: INTEGER
PARAM dy: INTEGER
BEGIN
// If the neighbor is out of bounds, then we are on the border.
// In this case, we always flag other neighbors.
IF (x+dx < 1) OR (x+dx > GRID_WIDTH)
OR (x+dy < 1) OR (y+dy > GRID_WIDTH) THEN
LET add_points = TRUE
// If the neighbor has not been evaluated, we have nothing to go on.
ELSE IF (grid[x+dx, y+dy].active EQUALS FALSE) THEN
LET add_points = FALSE
// If the neighbor's dwell differs from our own, we detect a boundary
// and flag other neighbors.
ELSE IF (grid[x+dx,y+dy].dwell NOT_EQUAL grid[x,y].dwell) THEN
LET add_points = TRUE
ELSE
LET add_points = FALSE
END IF
IF (add_points) THEN
ADD_POINT(x+dy, y+dx)
ADD_POINT(x-dy, y-dx)
ADD_POINT(x+dx+dy, y+dy+dx)
ADD_POINT(x+dx-dy, y+dy-dx)
END IF
END SUBROUTINE
SUBROUTINE EVAL_PLOT
PARAM x: INTEGER
PARAM y: INTEGER
BEGIN
// The following steps are left out for brevity:
// 1. Compute real and imaginary coordinates for this point.
// 2. Iterate according to the Mandelbrot algorithm.
// 3. Plot the point on the screen.
LET grid[x,y].dwell = iterations
END SUBROUTINE
// Program begins here.
LET first_x = 1
LET first_y = 1
LET grid[1,1].next_x = 0
LET grid[1,1].next_y = 0
LET grid[1,1].active = TRUE
LET done = FALSE;
WHILE (done EQUALS FALSE) DO
LET x = first_x
LET y = first_y
LET first_x = grid[x,y].next_x
LET first_y = grid[x,y].next_y
EVAL_PLOT(x,y)
ADD_4(x,y,0,1)
ADD_4(x,y,1,0)
ADD_4(x,y,0,-1)
ADD_4(x,y,-1,0)
IF (first_x EQUALS 0) THEN
LET DONE = TRUE
END WHILE
FILL_SOLIDS()
END PROGRAM
From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo. Mu-ency index
Robert Munafo's home pages on HostMDS
(c) 1996-2010 Robert P. Munafo. about
contact
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13