Proceed to Safety

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-2024.

Mu-ency main pageindexrecent changesDEMZ

Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

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