Details

An earlier Demonstration discussed component identification using "marching squares" and boundary delineation with the Moore boundary tracing algorithm. As the name indicates, marching squares progressively accumulates a single component and the Moore boundary tracer uses a kind of "spinning wheel" to trace out the boundary of a component. The boundary was traced inspecting the eight-noded neighbor (NW, N, NE, E, SE, S, SW, W) of every successive point.

However, if there are holes and the components are nested, and if one is only interested in the boundaries, a shorter method to obtain all the boundaries traced using the four-noded neighbors (N, E, S, W) is possible. The four-noded neighbors do not bias the boundary inward or outward when there are holes.

In this Demonstration, a large set of random points is chosen in a grid and some holes are artificially created. The prospective boundary points are classified using the fact that the number of common members of their eight neighbors is less than eight. Then the four-noded boundaries are traced one after another and the resulting boundary is taken out of the set of boundary points. After that, we also exclude "loners", which are those with none of their eight neighbors in the remaining set of boundary points. These loners typically arise when the holes are close to the outer boundary. This process is continued until all the boundary points are taken out.