This implementation of the Marching Box Algorithm makes use of some clever programming for code readability, however it may not be inherently easy to read for beginners, but it is a good example of how to implement an algorithm such as this one, in a clean way.

It may not be the fastest implementation but this code has served me well in the past and it turns out to be quite easy to maintain as well.

The primary application is to traverse for example bitmaps, you could implement a bucket fill or follow a contour easily, however more patterns may be required depending on your requirements.

I’ve used this, among with a peucker implementation, to create rough vector representations of bitmaps in the past. You may have to add exclusions or rules if you don’t want to check the extra 4 directions in diagonal, this depends on the type of images or data you’ll be working with.

EnableExplicit

Enumeration
	#MARCHING_BOX_PATTERN_A
	#MARCHING_BOX_PATTERN_B
	#MARCHING_BOX_PATTERN_C
	#MARCHING_BOX_PATTERN_D
EndEnumeration

Enumeration
	#MARCHING_BOX_ADD
	#MARCHING_BOX_SUB
EndEnumeration

Structure MARCHING_BOX_PATTERN
	field.i[4] 								; holds the pattern variables.
	*variable.Integer 						; variable we'll manipulate if the pattern matches.
	operator.i 								; flat to either increment or decrement on actual *variable
EndStructure

Structure MARCHING_BOX
	List pattern.MARCHING_BOX_PATTERN()
EndStructure

Declare.i marchingbox_create( *tx.Integer, *ty.Integer, *foreground.Integer, *background.Integer )
Declare.i marchingbox_destroy( *this.MARCHING_BOX )
Declare.i marchingbox_pattern_add( *this.MARCHING_BOX, *a.Integer, *b.Integer, *c.Integer, *d.Integer, *variable.Integer, operator.i )
Declare.i marchingbox_pattern_matches( *this.MARCHING_BOX_PATTERN, a.i, b.i, c.i, d.i )

Procedure.i marchingbox_create( *tx.Integer, *ty.Integer, *foreground.Integer, *background.Integer )
	
	Define.MARCHING_BOX *this = AllocateMemory( SizeOf(MARCHING_BOX) )
	If *this
		InitializeStructure( *this, MARCHING_BOX )
		
		marchingbox_pattern_add( *this, *foreground, *foreground, *foreground, *foreground, *tx, #MARCHING_BOX_ADD )
		marchingbox_pattern_add( *this, *foreground, *background, *foreground, *foreground, *tx, #MARCHING_BOX_ADD )
		marchingbox_pattern_add( *this, *foreground, *background, *foreground, *background, *ty, #MARCHING_BOX_ADD )
		marchingbox_pattern_add( *this, *foreground, *foreground, *foreground, *background, *ty, #MARCHING_BOX_ADD )
		
		marchingbox_pattern_add( *this, *background, *background, *foreground, *foreground, *tx, #MARCHING_BOX_ADD )
		marchingbox_pattern_add( *this, *background, *foreground, *foreground, *foreground, *ty, #MARCHING_BOX_SUB )
		marchingbox_pattern_add( *this, *background, *foreground, *background, *foreground, *ty, #MARCHING_BOX_SUB )
		marchingbox_pattern_add( *this, *foreground, *foreground, *background, *foreground, *tx, #MARCHING_BOX_SUB )
		
		marchingbox_pattern_add( *this, *foreground, *foreground, *background, *background, *tx, #MARCHING_BOX_SUB )
		marchingbox_pattern_add( *this, *background, *foreground, *background, *background, *ty, #MARCHING_BOX_SUB )			
		marchingbox_pattern_add( *this, *foreground, *background, *background, *background, *tx, #MARCHING_BOX_SUB )
		marchingbox_pattern_add( *this, *background, *background, *foreground, *background, *ty, #MARCHING_BOX_ADD )
		
		marchingbox_pattern_add( *this, *background, *background, *background, *foreground, *tx, #MARCHING_BOX_ADD )
		marchingbox_pattern_add( *this, *background, *foreground, *foreground, *background, *ty, #MARCHING_BOX_SUB )
		marchingbox_pattern_add( *this, *foreground, *background, *background, *foreground, *tx, #MARCHING_BOX_SUB )
		marchingbox_pattern_add( *this, *background, *background, *background, *background, #Null, #Null )
		
		ProcedureReturn *this
	EndIf

EndProcedure

Procedure.i marchingbox_destroy( *this.MARCHING_BOX )

	If *this
		ClearStructure( *this, MARCHING_BOX )
		ProcedureReturn FreeMemory(*this)
	EndIf

EndProcedure

Procedure.i marchingbox_pattern_add( *this.MARCHING_BOX, *a.Integer, *b.Integer, *c.Integer, *d.Integer, *variable.Integer, operator.i )
	
	If *this
		If AddElement( *this\pattern() )
			
			*this\pattern()\field[ #MARCHING_BOX_PATTERN_A ] 	= *a\i
			*this\pattern()\field[ #MARCHING_BOX_PATTERN_B ] 	= *b\i
			*this\pattern()\field[ #MARCHING_BOX_PATTERN_C ] 	= *c\i
			*this\pattern()\field[ #MARCHING_BOX_PATTERN_D ] 	= *d\i
			*this\pattern()\variable 													= *variable
			*this\pattern()\operator 													= operator
			
		EndIf
	EndIf
	
EndProcedure

Procedure.i marchingbox_pattern_matches( *this.MARCHING_BOX_PATTERN, a.i, b.i, c.i, d.i )
	
	If *this
		If *this\variable <> #Null
			If *this\field[ #MARCHING_BOX_PATTERN_A ] = a
				If *this\field[ #MARCHING_BOX_PATTERN_B ] = b
					If *this\field[ #MARCHING_BOX_PATTERN_C ] = c
						If *this\field[ #MARCHING_BOX_PATTERN_D ] = d
							
							Select *this\operator
								Case #MARCHING_BOX_ADD
									*this\variable\i + 1
								Case #MARCHING_BOX_SUB
									*this\variable\i - 1
								Default
									ProcedureReturn #False
							EndSelect
							
							ProcedureReturn #True
							
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf
	
EndProcedure

 
Probable optimizations include denesting and less error checking on the match procedure for the release version, however that’s also implementation dependent.

This original implementation was aimed toward image manipulation, hence you’ll notice some variable names aren’t generic, but relevant to the subject. You may change this as you please.

At any rate, enjoy!

Cheers,
Gus