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

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2008 Feb 05.

s.27