Package net.algart.matrices.scanning

Class Boundary2DScanner

java.lang.Object
net.algart.matrices.scanning.Boundary2DScanner
Direct Known Subclasses:
Boundary2DWrapper
public abstract class Boundary2DScanner extends Object

2-dimensional object boundaries scanner: the class allowing to trace boundaries of objects, "drawn" at some 2-dimensional bit matrix.

More precisely, let's consider some 2-dimensional AlgART bit matrix Matrix<? extends BitArray>. Below we shall designate this matrix as M.

Let's define a pixel with integer coordinates (x, y) as a set of points of the plane with such coordinates (x', y') that x−0.5≤x'≤x+0.5, y−0.5≤y'≤y+0.5. In other words, pixel is the square with the center (x, y) and the side 1.0.

Every unit element of the matrix M with coordinates (x, y) corresponds to a pixel (x, y) at the plane. Let's designate IM the figure (point set) consisting of all points of all pixels (squares with the side 1.0), corresponding to unit (1) elements of our matrix M. We can consider IM as an image (figure), "drawn" at the matrix M. Every unit element in M represents a little square 1x1 (a pixel) in the image (figure) IM, and the center of the pixel has integer coordinates in ranges 0..M.dimX()−1, 0..M.dimY()−1.

Then, let's consider a connected object at the matrix M, defined in the same terms as in ConnectedObjectScanner class, and corresponding connected figure in the image IM. As well as in that class, a connected object can have straight-and-diagonal connectivity (8-connected object) or straight connectivity (4-connected object). The first case corresponds to a usual connected area in the image IM, the second case — to a connected area in the figure, coming out from IM by removing all points with half-integer coordinates.

We define the boundary of some connected object as the geometrical boundary of the corresponding connected figure in the image IM. More precisely, the boundary of the connected object is a connected component of the full set of the boundary points (not pixels, but infinitesimal points of the plane) of the corresponding connected figure. So, the connected object can have several boundaries, if there are some "holes" in it. Any boundary is a chain of horizontal or vertical segments with the length 1.0, that separate pixels from each others. The ends of each segment have half-integer coordinates, and the 2nd end of the last segment coincides with the 1st end of the first segment.

We define the main boundary of the connected object as its boundary containing whole this object inside it.

We define the completion of the connected object as the sets of all points lying at or inside its main boundary. In other words, the completion is the object, where all internal "holes" ("pores") are filled. If the connected object has no "holes", its completion is identical to it.

Each segment with length 1.0 in any object boundary is a boundary of some pixel, belonging to the image IM. These pixels can lie 1) inside the boundary, and then it is true for all segments of the boundary, or 2) outside the boundary, and then it is true for all segments of the boundary.

In the first case we shall call the boundary as external, and in the second case we shall call it as internal. A connected object always have only one external boundary, namely, its main boundary. But a connected object can have several internal boundaries: these are boundaries of all its "holes".

This class represents a boundary scanner: an iterator allowing to trace all segments of one boundary — in the clockwise order for external boundaries, in the anticlockwise order for internal boundaries (if the x axis is directed rightwards and the y axis is directed downwards). The basic method of this iterator is next(). In addition, this class allows to sequentially visit all boundaries or all main boundaries of all connected objects; it is performed by the method nextBoundary().

The boundary scanner always has the current position. The position consists of:

  • x()-coordinate of the current pixel;
  • y()-coordinate of the current pixel;
  • the current pixel side(): index of one of 4 sides of the square 1x1, represented by Boundary2DScanner.Side enumeration class.

There is the only exception, when the scanner has no any position — directly after creating new instance. The first call of nextBoundary or goTo method sets some position.

In other words, the current position specifies some segment with length 1.0. This segment can be an element of some object boundary, but also can be a random pixel side in the image.

There are two basic methods of this class, changing the current position. The first method is nextBoundary(): it moves the current position to the nearest next object boundary, according to some rules depending on a concrete kind of scanner. After calling this method you may be sure that the current position specifies a segment of some object boundary. The second method is next(): it supposes that the current position specifies a segment of a boundary and, if it's true, moves the current position to the next segment of this boundary. So, you can find the next object boundary by nextBoundary() method and then scan it by sequential calls of next() method. Instead of manual loop of next() calls, you can use scanBoundary(ArrayContext) method.

We suppose that all possible positions are sorted in the following "natural" order: the position x1, y1, side1 is "less" than the position x2, y2, side2,

We also suppose that the "undefined" position, when the scanner is newly created and nextBoundary or goTo methods were not called yet, is "less" than all other positions. This order is used by nextBoundary() method.

There are the following ways to create an instance of this class:

The difference between instances, created by first 3 methods, is in the behavior of nextBoundary() and next(): see comments to these instantiation methods. The Boundary2DWrapper class and its inheritors just call some parent boundary scanner and, maybe, do some additional work (for example, measure the objects).

The instance of this class always works with some concrete matrix and some concrete connectivity type, specified while creating the instance, and you cannot switch an instance of this class to another bit matrix. But this class is lightweight: there is no problem to create new instances for different matrices.

You must not use this instance after any modifications in the scanned matrix, performed by an external code. If you modify the matrix, you must create new instance of this class after this.

Below is a typical example of using this class:

 Boundary2DScanner scanner = Boundary2DScanner.getAllBoundariesScanner(m, um1, um2, connectivityType);
 Boundary2DSimpleMeasurer measurer = Boundary2DSimpleMeasurer.getInstance(scanner,
     EnumSet.of(Boundary2DSimpleMeasurer.ObjectParameter.AREA));
 while (measurer.nextBoundary()) {
     measurer.checkInterruption(ac);
     measurer.updateProgress(ac);
     measurer.scanBoundary(ac);
     long area = measurer.area();
     // some operations with the found area
 }

Note: this class works much faster (in several times) if the scanned matrix is created by SimpleMemoryModel, especially if its horizontal dimension dimX() is divisible by 64 (dimX()%64==0). So, if the matrix is not created by SimpleMemoryModel and is not too large, we recommend to create its clone by SimpleMemoryModel, expanded by x to the nearest integer divisible by 64, and use this class for the clone.

Note: this class can process only 2-dimensional matrices. An attempt to create an instance of this class for a matrix with other number of dimensions leads to IllegalArgumentException.

This class does not use multithreading optimization, unlike Arrays.copy(ArrayContext, UpdatableArray, Array) and similar methods. In other words, all methods of this class are executed in the current thread.

This class is not thread-safe, but is thread-compatible and can be synchronized manually, if multithread access is necessary. Warning! Even if you use in several different threads different instances of this class, created via one of the following methods:

then you either must pass different buffer matrices in different threads, or manually synchronize all called methods. In other case, the content of buffer matrices will be unspecified and behavior of the scanning algorithm will be undefined.

Author:
Daniel Alievsky