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