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, (c) 1987-2013.     Mu-ency index
Robert Munafo's home pages on HostMDS   © 1996-2013 Robert P. Munafo.   about   contact   Google+   mrob27   @mrob_27

This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. Details here s.11