Interface Pattern

All Known Subinterfaces:
DirectPointSetPattern, DirectPointSetUniformGridPattern, QuickPointCountPattern, RectangularPattern, UniformGridPattern, WeightedPattern
All Known Implementing Classes:
AbstractPattern, AbstractUniformGridPattern, AbstractWeightedPattern, SimplePattern

public interface Pattern

Pattern: non-empty set of real points in multidimensional space (points with real coordinates).

Usually patterns are relatively little point sets: from tens to millions of points not too far from the origin of coordinates. However, please note that the number of points is not limited by any value. In particular, it can be greater than Long.MAX_VALUE. For example, it may occur for rectangular n-dimensional patterns.

Patterns are the arguments of many image processing filters. For example, a pattern may specify the form and sizes of the aperture for a linear filter.

Integer patterns

The very important subclass among all patterns is integer patterns, consisting of points with integer coordinates. More precisely, a pattern is called integer, if for all pattern's points (x0, x1, ..., xn−1) we have xj==(double)(long)xj for any index j. There is the standard method round(), rounding any pattern to the nearest integer pattern — the result of this method is always integer.

Usually integer patterns are uniform-grid patterns (see the next section), but this condition is not absolute: even a pattern, not implementing UniformGridPattern interface, is called integer pattern, if all its points are really integer. The most popular case of integer patters is so-called ordinary integer patterns — see below in the next section "Uniform-grid patterns".

You can try to investigate, whether some pattern is integer or not, by isSurelyInteger() method.

Integer patterns is the basic pattern type for image processing tasks.

In this package, the following methods always create integer patterns:

Uniform-grid patterns

The important subclass among all patterns is uniform-grid patterns, represented by the subinterface UniformGridPattern. Uniform-grid patterns is a pattern, all points of which are mesh nodes of some uniform grids, i.e. have coordinates

x0 = o0 + i0d0
x1 = o1 + i1d1
. . .
xn−1 = on−1 + in−1dn−1

where oj and dj are some constants (dj>0) and ij are any integer numbers. The parameters oj (named origin) and dj (named steps) are specified while creating the pattern, and they are stored inside the object and can be quickly read by the access methods UniformGridPattern.originOfGrid() and UniformGridPattern.stepsOfGrid().

Draw attention to the last condition! You can easily create also a pattern, all points of which lie in mesh nodes of some uniform grid, but which will not "know" anything about this grid and will not implement UniformGridPattern interface. The simplest way to do this is the call of the constructor

    new SimplePattern(pattern.points()),

where pattern is a uniform-grid pattern. The resulting pattern is geometrically identical to the original uniform-grid one, but it does not implement UniformGridPattern and is not considered to be uniform-grid, because there are no ways to get information about the grid (origin and steps).

It is obvious that a uniform-grid pattern is also an integer pattern (see above), if all numbers oj and dj are integer. The most important particular case: all oj=0 and all dj=1. We shall call this kind of patterns ordinary integer patterns.

In this package, uniform-grid patterns are the patterns, created by one of the following ways, and only they:

and also, in some cases (depending on the arguments), by the following methods:

Direct point-set patterns

One of the most popular, basic kinds of patterns is direct point-set patterns, represented by the subinterface DirectPointSetPattern. The pattern is called direct point-set or, briefly, direct, if it is internally represented as an actual set of points like Set<Point>.

Of course, any pattern is a set of points. The main feature of this subclass is that the point-set is stored directly in a form of some collection — and, so, can be directly accessed at any time via points() or roundedPoints() methods. As a result, direct point-set pattern cannot contain more than Integer.MAX_VALUE points (because Java Set object cannot contain more than Integer.MAX_VALUE elements).

Unlike direct patterns, other forms of pattern, like rectangular or complex (see below), do not actually store the set of their points, though still can build and return it by a request, when you call points() or roundedPoints().

In this package, direct point-set patterns are the patterns, created by one of the following ways, and only they:

Direct point-set pattern may be, at the same time, uniform-grid. In this case it must implement DirectPointSetUniformGridPattern interface. This package provides an implementation of direct pattern, which is not uniform-grid: SimplePattern. Most of other direct point-set patterns, provided by this package, are uniform-grid and implement DirectPointSetUniformGridPattern interface.

Rectangular patterns

The second popular basic kind of patterns is rectangular patterns, represented by the subinterface RectangularPattern. The pattern is called rectangular, if it is uniform-grid (implements UniformGridPattern interface), and it consists of all points inside some hyperparallelepiped, the parameters (bounds) of which were specified while creating the pattern, are stored inside the object and can be quickly read by methods like coordRange(int).

Draw attention to the last condition! Of course, you can create also a direct point-set pattern, consisting of all points inside some hyperparallelepiped. The simplest way to do this is the call of the constructor

    new SimplePattern(pattern.points()),

where pattern is a rectangular pattern. However, the resulting pattern is considered to be direct, but not rectangular.

The main difference between direct point-set and rectangular patterns is the behaviour of methods, retrieving the point set like points(), and some methods, retrieving boundaries of the pattern, like UniformGridPattern.upperSurface(int), UniformGridPattern.maxBound(int), etc. In direct patterns, all methods always work stably, i.e. without exceptions (if the passed arguments are correct), but calculation of pattern boundaries can require some time, proportional to the number of points in the pattern. In rectangular patterns, an attempt to get all points by points() or roundedPoints() method can lead to TooManyPointsInPatternError or to OutOfMemoryError, because the number of points can be extremely large (for example, 10000x10000x10000 3-dimensional parallelepiped consists of 1012 points); but the information about boundaries is available very quickly. See the details in comments to DirectPointSetPattern and RectangularPattern interfaces.

The classes of direct point-set and rectangular patterns do not intersect: a direct point-set pattern cannot be rectangular, and a rectangular pattern cannot be direct.

Direct point-set and rectangular pattern are the base, used in many algorithms and allowing to build more specific pattern types (see below).

In this package, rectangular patterns are the patterns, created by one of the following ways, and only they:

Complex patterns

Besides the basic types of patterns — direct point-set and rectangular — this package allows to create more complex forms of patterns. Such patterns do not actually store information about the point set, but contain some rules allowing to construct this point set. The typical examples are Minkowski sum of several patterns, created by Patterns.newMinkowskiSum(java.util.Collection) method, and the union of several patterns, created by Patterns.newUnion(java.util.Collection) method. An attempt to get actual information about the figure of such a pattern via its methods points(), roundedPoints(), and even usage of the simplest methods pointCount(), largePointCount(), isSurelyOriginPoint() can lead to very long calculations and even to TooManyPointsInPatternError / OutOfMemoryError. However, such patterns can be used indirectly, usually via their decompositions into more simple patterns by minkowskiDecomposition(int) and unionDecomposition(int) methods. For example, it is possible to perform morphological dilation filter over an image (see "Dilation" article in Wikipedia) with a very large pattern, created by Patterns.newMinkowskiSum(java.util.Collection) and consisting of millions or milliards points, via sequential dilations with the Minkowski summands of such a pattern, extracted by minkowskiDecomposition(int) call.

Coordinate restrictions

There are the following guarantees for coordinates of the points of any pattern:

  1. if p=(x0,x1,...,xn−1) is some point of the pattern, then −MAX_COORDINATExjMAX_COORDINATE for all j; here this inequality means absolutely precise mathematical inequality;
  2. if p=(x01,x11,...,xn−11) and q=(x02,x12,...,xn−12) are some two points of the pattern, then |xj1xj2|≤MAX_COORDINATE for all j, where |xj1xj2| means the absolute value of mathematically precise difference (not the result of Java operators Math.abs(xj1xj2)). (This condition can be checked with help of Patterns.isAllowedDifference(double, double) method.)

Each implementation of this interface must fulfil both restriction. The point sets, satisfying these requirements, are called allowed points sets for patterns. Any attempt to create a pattern, the set of points of which is not allowed, leads to TooLargePatternCoordinatesException.

Note: though patterns are sets of real points, their coordinates are restricted by long-type constant MAX_COORDINATE.

Also note: uniform-grid patterns must fulfil, in addition, two similar restrictions for their grid indexes. See more details in the comments to UniformGridPattern interface, the section "Grid index restrictions".

Below are two important theorems, following from these two restrictions.

Theorem I. If you round the coordinates of all points of a pattern, i.e. replace each pattern's point (x0, x1, ..., xn−1) with a new point (round(x0), round(x1), ..., round(xn−1)), where "round(a)" means the result of (double)StrictMath.round(a) call, then the resulting point set will also be allowed. The same statement is true for the point set, consisting of precise integer points, without type cast to double, i.e. for points (StrictMath.round(x0), StrictMath.round(x1), ..., StrictMath.round(xn−1)) — such mathematical point set also fulfils both restrictions 1 and 2.

The proof of this is complex enough. The paper http://algart.net/ru/numeric_algorithms/rounding_theorem.html (in Russian) contains such proof: see the theorem of rounding and the theorem of subtraction in this paper.

It means that you can freely use round() method for any pattern: it always constructs another allowed pattern, both in terms of this interface and in terms in UniformGridPattern, and cannot throw TooLargePatternCoordinatesException.

Theorem II. If all points of a pattern are integer, i.e. for all pattern's points (x0, x1, ..., xn−1) we have xj==(double)(long)xj for any index j, and (X0,X1,...,Xn−1) is some point of this pattern, then you can subtract (using Java “−” operator) the coordinate Xj (j is any index) from the corresponding coordinate of all points of this pattern, i.e. replace each pattern's point (x0, ..., xj−1, xj, xj+1, ..., xn−1) with (x0, ..., xj−1, xjXj, xj+1, ..., xn−1), and the resulting point set will also be allowed. Here and below ab (a and b are real values of double Java type) means the computer difference (not strict mathematical), i.e. the result of execution of Java operator “ab”.

Proof.

First of all, let's remind that the computer difference ab, according IEEE 754 standard and Java language specification, is the nearest double value to the precise mathematical difference ab. Because all pattern's points are integer, the restriction 2 allows to state that any difference xjXj can be represented precisely by double type (see the comments to MAX_COORDINATE constant). So, we have xjXj = xjXj: the computer difference is just a mathematical difference.

Now the proof is simple. If is enough to show that the restrictions will be satisfied for the coordinate index j. The restriction 2 is obvious: (mathematical) subtracting Xj does not change the (mathematical!) differences |xj1xj2|. The new value of this coordinate for each point will be xjXj, where both (x0,x1,...,xn−1) and (X0,X1,...,Xn−1) are some points of the pattern; according the condition 2, this difference lies in range −MAX_COORDINATExjXjMAX_COORDINATE. In other words, the restriction 1 is also satisfied. This completes the proof.

Note: this proof is really correct only for patterns, consisting of integer points only. The reason is that all integer coordinates, fulfilling the restriction 1, and all their differences xjXj are represented precisely by double Java type. If a pattern contains non-integer points, the statement of this theorem is not true. For example, for 1-dimensional pattern, consisting of three points x1=2251799813685248.00 (=MAX_COORDINATE/2), x2=−2251799813685248.00 (=−MAX_COORDINATE/2) and x3=−2251799813685247.75 (=−MAX_COORDINATE/2+0.25), subtracting the point x3 by Java “−” operator leads to the pattern x'1=4503599627370496.00 (=MAX_COORDINATE) (computer subtraction of double values leads to rounding here), x'2=−0.25 and x'3=0.0, which obviously violates the mathematically precise restriction 2: |x'1x'2|>MAX_COORDINATE.

As a result, there is an obvious conclusion. If p is one of the points of some integer pattern (see above), then the method pattern.shift(p.symmetric()) always works successfully and never throw TooLargePatternCoordinatesException.

Note about equals()

The equals() method in the classes, implementing this interface, may return false for two patterns, consisting of the same point sets, for example, if these patterns belong to different pattern types. For example, a rectangular pattern may be considered to be non-equal to a geometrically identical Minkowski sum of several segments, because the thorough comparison of these patterns can require too long time and large memory. (Please consider 10000x10000x10000 3-dimensional parallelepiped, consisting of 1012 points with integer coordinates in range 0..9999. It is geometrically equal to Minkowski sum of 3 orthogonal segments with 10000 integer points in every segment, but we have no resources to check this fact via direct comparison of the point sets.) However, the patterns of the same kind (for example, two rectangular patterns, two Minkowski sums or two unions) are usually compared precisely. In particular, there are the following guarantees:

  • if both patterns are direct point-set (see above), then equals() method always returns true for geometrically identical patterns;
  • if both patterns are rectangular (see above), then, also, equals() method always returns true for geometrically identical patterns;
  • and, of course, there is the reverse guarantee, that if the equals() method returns true, then two patterns consists of the identical point sets.

Multithread compatibility

The classes, implementing this interface, are immutable and thread-safe: there are no ways to modify settings of the created instance.

Author:
Daniel Alievsky
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final long
    The maximal possible absolute coordinate value and maximal absolute difference between the corresponding coordinates for all points in a pattern.
  • Method Summary

    Modifier and Type
    Method
    Description
    allUnionDecompositions(int minimalPointCount)
    Returns a non-empty list of all best or almost best union decompositions with equal or similar "quality", i.e. with the same or almost same summary number of points in all Minkowski decompositions of all returned patterns.
    Returns the carcass of this pattern.
    Returns the minimal and maximal coordinates among all points of this pattern for all dimensions.
    Returns the point, each coordinate of which is equal to the maximal corresponding coordinate among all points of this pattern.
    Returns the point, each coordinate of which is equal to the minimal corresponding coordinate among all points of this pattern.
    coordRange(int coordIndex)
    Returns the minimal and maximal coordinate with the given index (Point.coord(coordIndex)) among all points of this pattern.
    int
    Returns the number of space dimensions of this pattern.
    boolean
    Returns true if and only if the Minkowski decomposition, returned by minkowskiDecomposition(0) call, consists of 2 or more patterns: minkowskiDecomposition(0).size()>1.
    boolean
    Returns true if this pattern is integer: all coordinates of all points of this pattern are integer numbers.
    boolean
    Returns true if this pattern consists of the single point and this point is the origin of coordinates.
    boolean
    Returns true if this pattern consists of the single point, i.e. if pointCount()==1.
    double
    Returns the number of points in this pattern as double value.
    maxBound(int coordIndex)
    Returns the maximal boundary of this pattern along the given axis: a pattern consisting of all points of this pattern, for which there are no other points with greater coordinate #coordIndex and same other coordinates.
    int
    Returns the maximal multiplier k, for which the calculation of the Minkowski multiple k⊗P can be optimized by using the carcass of this pattern P.
    minBound(int coordIndex)
    Returns the minimal boundary of this pattern along the given axis: a pattern consisting of all points of this pattern, for which there are no other points with less coordinate #coordIndex and same other coordinates.
    Calculates and returns the Minkowski sum of this and specified patterns.
    minkowskiDecomposition(int minimalPointCount)
    Returns the Minkowski decomposition: a non-empty list of patterns P0, P1, ..., Pn−1, such that this pattern P (the point set represented by it) is a Minkowski sum of them (of the point sets represented by them): P = P0 ⊕ P1 ⊕...⊕ Pn−1.
    Calculates and returns the erosion of this pattern by specified pattern or null if this erosion is the empty set.
    multiply(double multiplier)
    Returns this pattern, scaled by the specified multiplier along all coordinates.
    long
    Returns the number of points in this pattern.
    Returns a set of all points of this pattern.
    projectionAlongAxis(int coordIndex)
    Returns the projection of this pattern along the given axis.
    Returns this pattern, every point of which is rounded to the nearest integer point.
    Returns the same result as coordArea() method, but all minimal and maximal coordinates are rounded to integer values by StrictMath.round operation.
    roundedCoordRange(int coordIndex)
    Returns the same result as coordRange(int coordIndex) method, but both minimal and maximal coordinates are rounded to integer values by StrictMath.round operation.
    Returns the set of all integer points, obtained from the points of this pattern (results of points() method by rounding with help of Point.toRoundedPoint() method.
    scale(double... multipliers)
    Returns this pattern, scaled by the specified multipliers along all coordinates.
    shift(Point shift)
    Returns this pattern, shifted by the argument.
    Returns the symmetric pattern: equivalent to multiply(-1.0).
    unionDecomposition(int minimalPointCount)
    Returns a union decomposition: a non-empty list of patterns P0, P1, ..., Pn−1, such that this pattern P (the point set represented by it) is the set-theoretical union of them (of the point sets represented by them): P = P0 ∪ P1 ∪...∪ Pn−1.
  • Field Details

  • Method Details

    • dimCount

      int dimCount()
      Returns the number of space dimensions of this pattern. This value is always positive (>=1).

      There is a guarantee, that this method always works very quickly (O(1) operations) and without exceptions.

      Returns:
      the number of space dimensions of this pattern.
    • pointCount

      long pointCount()
      Returns the number of points in this pattern. This value is always positive (>=1). If the number of points is greater than Long.MAX_VALUE, returns Long.MAX_VALUE.

      Warning! This method can work slowly for some forms of large patterns: the required time can be O(N), where N is the number of points (result of this method). In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError.

      There is a guarantee, that if this object implements QuickPointCountPattern interface, then this method works very quickly (O(1) operations) and without exceptions.

      There is a guarantee, that if this object implements DirectPointSetPattern interface, then the result of this method is not greater than Integer.MAX_VALUE.

      Note: if this method returns some value greater than Integer.MAX_VALUE, it means that you cannot use points() and roundedPoints() methods, because Java Set object cannot contain more than Integer.MAX_VALUE elements.

      Returns:
      the number of points in this pattern.
      Throws:
      TooManyPointsInPatternError - for some forms of large patterns, if the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
      See Also:
    • largePointCount

      double largePointCount()
      Returns the number of points in this pattern as double value. In particular, if the result of pointCount() method is not greater than Long.MAX_VALUE, there is a guarantee that this method returns the same result, cast to double type.

      Warning! This method can work slowly for some forms of large patterns: the required time can be O(N), where N is the number of points (result of this method). In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError.

      There is a guarantee, that if this object implements QuickPointCountPattern interface, then this method works very quickly (O(1) operations) and without exceptions.

      Returns:
      the number of points in this pattern as double value.
      Throws:
      TooManyPointsInPatternError - for some forms of large patterns, if the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
      See Also:
    • points

      Set<Point> points()
      Returns a set of all points of this pattern.

      The result of this method is immutable (Collections.unmodifiableSet). Moreover, the result is always the same for different calls of this method for the same instance — there are no ways to change it, in particular, via any custom methods of the implementation class (it is a conclusion from the common requirement, that all implementations of this interface must be immutable).

      The returned set is always non-empty, and the number of its elements is always equal to pointCount().

      Warning! This method can work slowly for some forms of large patterns. In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError. This method surely fails (throws one of these exception), if the total number of points pointCount()>Integer.MAX_VALUE, because Java Set object cannot contain more than Integer.MAX_VALUE elements.

      For example, implementations of the rectangular patterns allow to successfully define a very large 3D parallelepiped n x n x n. Fur such pattern, this method will require a lot of memory for n=1000 and will fail (probably with TooManyPointsInPatternError) for n=2000 (20003>Integer.MAX_VALUE).

      There is a guarantee, that if this object implements DirectPointSetPattern interface, then this method requires not greater than O(N) operations and memory (N=pointCount()) and never throws TooManyPointsInPatternError.

      Note: this method works very quickly (O(1) operations) in SimplePattern class.

      Returns:
      all points of this pattern.
      Throws:
      TooManyPointsInPatternError - if the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
    • roundedPoints

      Set<IPoint> roundedPoints()

      Returns the set of all integer points, obtained from the points of this pattern (results of points() method by rounding with help of Point.toRoundedPoint() method. In other words, the results of this method is the same as the result of the following code:

           Set<IPoint> result = new HashSet<IPoint>(); // or another Set implementation
           for (Point p : points()) {
               result.add(p.toRoundedPoint());
           }
           result = Collections.unmodifiableSet(result);
       

      The result of this method is immutable (Collections.unmodifiableSet). Moreover, the result is always the same for different calls of this method for the same instance — there are no ways to change it, in particular, via any custom methods of the implementation class (it is a conclusion from the common requirement, that all implementations of this interface must be immutable).

      The returned set is always non-empty.

      Note: the number of resulting points can be less than pointCount(), because some real points can be rounded to the same integer points.

      According the basic restriction to pattern coordinates (see the comments to this interface, section "Coordinate restrictions"), you may be sure that you will able to create an integer uniform-grid pattern by passing the result of this method to Patterns.newIntegerPattern(java.util.Collection).

      Warning! This method can work slowly or throw TooManyPointsInPatternError / OutOfMemoryError in the same situations as points() method.

      There is a guarantee, that if this object implements DirectPointSetPattern interface, then this method requires not greater than O(N) operations and memory (N=pointCount()) and never throws TooManyPointsInPatternError. Please compare with round() method, which always works quickly and without exceptions also for the case of RectangularPattern.

      Returns:
      all points of this pattern, rounded to the nearest integer points.
      Throws:
      TooManyPointsInPatternError - if the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
    • coordRange

      Range coordRange(int coordIndex)
      Returns the minimal and maximal coordinate with the given index (Point.coord(coordIndex)) among all points of this pattern. The minimal coordinate will be r.min(), the maximal coordinate will be r.max(), where r is the result of this method.

      There is a guarantee, that if this object implements RectangularPattern interface, then this method works very quickly (O(1) operations) and without exceptions.

      Moreover, all patterns, implemented in this package, have very quick implementations of this method (O(1) operations). Also, the implementations of this method in this package never throw exceptions.

      It is theoretically possible, that in custom implementations of this interface (outside this package) this method will work slowly, up to O(N) operations, N is the number of points in this pattern. However, even in such implementations this method must not lead to TooManyPointsInPatternError / OutOfMemoryError, like points() method.

      Parameters:
      coordIndex - the index of the coordinate (0 for x, 1 for y, 2 for z, etc.).
      Returns:
      the range from minimal to maximal coordinate with this index.
      Throws:
      IndexOutOfBoundsException - if coordIndex<0 or coordIndex>=dimCount().
      See Also:
    • coordArea

      RectangularArea coordArea()
      Returns the minimal and maximal coordinates among all points of this pattern for all dimensions. If a is the result of this method, then a.coordCount()==dimCount() and a.range(k) is equal to coordRange(k) for all k.

      For example, in 2-dimensional case the result is the circumscribed rectangle (with sides, parallel to the axes).

      All, said in the comments to coordRange(int) method about the speed and impossibility of TooManyPointsInPatternError / OutOfMemoryError, is also true for this method.

      Returns:
      the ranges from minimal to maximal coordinate for all space dimensions.
      See Also:
    • coordMin

      Point coordMin()
      Returns the point, each coordinate of which is equal to the minimal corresponding coordinate among all points of this pattern. Equivalent to coordArea().min().

      All, said in the comments to coordRange(int) method about the speed and impossibility of TooManyPointsInPatternError / OutOfMemoryError, is also true for this method.

      Returns:
      minimal coordinates for all space dimensions as a point.
    • coordMax

      Point coordMax()
      Returns the point, each coordinate of which is equal to the maximal corresponding coordinate among all points of this pattern. Equivalent to coordArea().max().

      All, said in the comments to coordRange(int) method about the speed and impossibility of TooManyPointsInPatternError / OutOfMemoryError, is also true for this method.

      Returns:
      maximal coordinates for all space dimensions as a point.
    • roundedCoordRange

      IRange roundedCoordRange(int coordIndex)
      Returns the same result as coordRange(int coordIndex) method, but both minimal and maximal coordinates are rounded to integer values by StrictMath.round operation. Equivalent to coordRange(coordIndex).toRoundedRange().

      According the basic restriction to pattern coordinates (see the comments to this interface, section "Coordinate restrictions"), you may be sure that you will be able to create an integer rectangular pattern by passing the ranges, got by this method, to Patterns.newRectangularIntegerPattern(IRange...).

      All, said in the comments to coordRange(int) method about the speed and impossibility of TooManyPointsInPatternError / OutOfMemoryError, is also true for this method.

      Parameters:
      coordIndex - the index of the coordinate (0 for x, 1 for y, 2 for z, etc.).
      Returns:
      the range from minimal to maximal coordinate with this index, rounded to the long values.
      Throws:
      IndexOutOfBoundsException - if coordIndex<0 or coordIndex>=dimCount().
      See Also:
    • roundedCoordArea

      IRectangularArea roundedCoordArea()
      Returns the same result as coordArea() method, but all minimal and maximal coordinates are rounded to integer values by StrictMath.round operation. The method IRectangularArea.range(int coordIndex) in the returned area returns the same result as roundedCoordRange(int coordIndex) method in this object.

      All, said in the comments to coordRange(int) method about the speed and impossibility of TooManyPointsInPatternError / OutOfMemoryError, is also true for this method.

      Returns:
      the ranges from minimal to maximal coordinate for all space dimensions, rounded to the long values.
    • isSurelySinglePoint

      boolean isSurelySinglePoint()
      Returns true if this pattern consists of the single point, i.e. if pointCount()==1.

      There are no strict guarantees that this method always returns true if the pattern consist of the single point. (In some complex situations, such analysis can be too difficult. In particular, if the pattern is a Minkowski sum, then limited floating-point precision can lead to equality of all points of the result. Simple example: a Minkowski sum of two-point one-dimensional pattern, consisting of points 0.0 and 0.000001, and one-point 251=2251799813685248.0, contains only 1 point 251, because the computer cannot represent precise value 2251799813685248.000001 in double type and rounds it to 2251799813685248.0. In such situations, this method sometimes may incorrectly return false.)

      But there is the reverse guarantee: if this method returns true, the number of points in this pattern is always 1.

      Unlike pointCount() method, there is a guarantee that this method never works very slowly and cannot lead to TooManyPointsInPatternError / OutOfMemoryError. In situations, when the number of points is very large (and, so, pointCount() method is not safe in use), this method must detect this fact in reasonable time and return false.

      There is a guarantee, that if this object implements QuickPointCountPattern interface, then this method works very quickly (O(1) operations) and absolutely correctly (always returns true if and only if pointCount()==1).

      Returns:
      true if it is one-point pattern.
      See Also:
    • isSurelyOriginPoint

      boolean isSurelyOriginPoint()
      Returns true if this pattern consists of the single point and this point is the origin of coordinates.

      There are no strict guarantees that this method always returns true if the pattern consist of the single point, equal to the origin of coordinates. (In some complex situations, such analysis can be too difficult. In such situations, this method may incorrectly return false.) But there is the reverse guarantee: if this method returns true, the number of points in this pattern is always 1 and its only point is the origin of coordinates, in terms of Point.isOrigin() method.

      Unlike pointCount() method, there is a guarantee that this method never works very slowly and cannot lead to TooManyPointsInPatternError / OutOfMemoryError. In situations, when the number of points is very large (and, so, pointCount() method is not safe in use), this method must detect this fact in reasonable time and return false.

      There is a guarantee, that if this object implements QuickPointCountPattern interface, then this method works very quickly (O(1) operations) and absolutely correctly.

      Returns:
      true if it is one-point pattern containing the origin of coordinates as the single point.
      See Also:
    • isSurelyInteger

      boolean isSurelyInteger()
      Returns true if this pattern is integer: all coordinates of all points of this pattern are integer numbers. In other words, it means that for each real (double) coordinate x of each point of this pattern the Java expression x==(long)x is true.

      More precisely, if this method returns true, then there are the following guarantees:

      1. for each point, returned by points() method, as well as by coordMin()/coordMax(), Point.isInteger() method returns true;
      2. each pattern, returned in the results of minkowskiDecomposition(int), unionDecomposition(int) and allUnionDecompositions(int) methods, is also surely integer, i.e. this method also returns true for it.

      However, there are no strict guarantees that this method always returns true if the pattern is really integer. In other words, if this method returns false, there is no guarantee, that this pattern really contains some non-integer points — but it is probable.

      Unlike points() method, there is a guarantee that this method never works very slowly and cannot lead to TooManyPointsInPatternError / OutOfMemoryError. In situations, when the number of points is very large and there is a risk to fail with TooManyPointsInPatternError / OutOfMemoryError, this method must detect this fact in reasonable time and return false.

      See the comments to this interface, section "Integer patterns", for more details.

      Returns:
      true if this pattern and all patterns of its decomposition (Minkowski or union) assuredly contain only integer points.
    • round

      Returns this pattern, every point of which is rounded to the nearest integer point. The result is always ordinary integer pattern (see the comments to this interface, section "Uniform-grid patterns").

      More precisely, the resulting pattern:

      1. consists of all points, obtained from all points of this pattern by rounding by the call point.toRoundedPoint().toPoint();
      2. has zero origin UniformGridPattern.originOfGrid()=(0,0,...,0) and unit steps UniformGridPattern.stepsOfGrid()={1,1,..,1}.

      Note: the number of points in the result can be less than pointCount(), because some real points can be rounded to the same integer points.

      Warning! If this object is not DirectPointSetPattern and is not RectangularPattern, this method can work slowly for some large patterns: the required time can be O(N), where N is the number of points. In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError. The situation is like in points() and roundedPoints() method.

      There is a guarantee, that if this object implements DirectPointSetPattern interface, then this method requires not greater than O(N) operations and memory (N=pointCount()) and never throws TooManyPointsInPatternError.

      There is a guarantee, that if this object implements RectangularPattern interface, then this method works quickly (O(1) operations) and without exceptions. It is an important difference from points() and roundedPoints() method.

      The theorem I, described in the comments to this interface, section "Coordinate restrictions", provides a guarantee that this method never throws TooLargePatternCoordinatesException.

      Returns:
      the integer pattern, geometrically nearest to this one.
      Throws:
      TooManyPointsInPatternError - if this pattern is not DirectPointSetPattern and not RectangularPattern and if, at the same time, the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
    • shift

      Pattern shift(Point shift)
      Returns this pattern, shifted by the argument.

      More precisely, the resulting pattern consists of the points, obtained from all points of this pattern by the call point.add(shift).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      There is a guarantee, that this method does not try to allocate much more memory, that it is required for storing this pattern itself, and that it never throws TooManyPointsInPatternError. For comparison, an attempt to do the same operation via getting all points (points() method), correcting them and forming a new pattern via Patterns.newPattern(java.util.Collection) will lead to TooManyPointsInPatternError / OutOfMemoryError for some forms of large patterns.

      Warning: this method can fail with TooLargePatternCoordinatesException, if some of new points violate restrictions, described in the comments to this interface, section "Coordinate restrictions" (for example, due to very large shift).

      However, TooLargePatternCoordinatesException is impossible in many important cases, when this pattern is an integer pattern and each coordinate Xj=shift.coord(j) of the argument is equal to −xj for some some point (x0, x1, ..., xn−1) of this pattern. In particular, you can use this method for integer patterns without a risk of TooLargePatternCoordinatesException in the following situations:

      See more details in the comments to this interface, section "Coordinate restrictions", the theorem II.

      Parameters:
      shift - the shift.
      Returns:
      the shifted pattern.
      Throws:
      NullPointerException - if the argument is null.
      IllegalArgumentException - if point.coordCount()!=dimCount().
      TooLargePatternCoordinatesException - if the set of shifted points does not fulfil the restrictions, described in the comments to this interface, section "Coordinate restrictions".
    • symmetric

      Pattern symmetric()
      Returns the symmetric pattern: equivalent to multiply(-1.0).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      There is a guarantee, that this method does not try to allocate much more memory, that it is required for storing this pattern itself, and that it never throws TooManyPointsInPatternError. For comparison, an attempt to do the same operation via getting all points (points() method), correcting them and forming a new pattern via Patterns.newPattern(java.util.Collection) will lead to TooManyPointsInPatternError / OutOfMemoryError for some forms of large patterns.

      Returns:
      the symmetric pattern.
    • multiply

      Pattern multiply(double multiplier)
      Returns this pattern, scaled by the specified multiplier along all coordinates.

      More precisely, the resulting pattern consists of the points, obtained from all points of this pattern by the call point.multiply(multipliers).

      This method is equivalent to scale(double...multipliers), where all dimCount() arguments of that method are equal to multiplier.

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      There is a guarantee, that this method does not try to allocate much more memory, that it is required for storing this pattern itself, and that it never throws TooManyPointsInPatternError. For comparison, an attempt to do the same operation via getting all points (points() method), correcting them and forming a new pattern via Patterns.newPattern(java.util.Collection) will lead to TooManyPointsInPatternError / OutOfMemoryError for some forms of large patterns.

      Warning: this method can fail with TooLargePatternCoordinatesException, if some of new points violate restrictions, described in the comments to this interface, section "Coordinate restrictions" (for example, due to a very large multiplier). However, such failure is obviously impossible, if the multiplier is in range -1.0<=multiplier<=1.0.

      Parameters:
      multiplier - the scale along all coordinates.
      Returns:
      the scaled pattern.
      Throws:
      TooLargePatternCoordinatesException - if the set of scaled points does not fulfil the restrictions, described in the comments to this interface, section "Coordinate restrictions".
      See Also:
    • scale

      Pattern scale(double... multipliers)
      Returns this pattern, scaled by the specified multipliers along all coordinates.

      More precisely, the resulting pattern consists of the points, obtained from all points of this pattern by the call point.scale(multipliers).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      There is a guarantee, that this method does not try to allocate much more memory, that it is required for storing this pattern itself, and that it never throws TooManyPointsInPatternError. For comparison, an attempt to do the same operation via getting all points (points() method), correcting them and forming a new pattern via Patterns.newPattern(java.util.Collection) will lead to TooManyPointsInPatternError / OutOfMemoryError for some forms of large patterns.

      Warning: this method can fail with TooLargePatternCoordinatesException, if some of new points violate restrictions, described in the comments to this interface, section "Coordinate restrictions" (for example, due to very large multipliers). However, such failure is obviously impossible, if all multipliers are in range -1.0<=multipliers[k]<=1.0.

      Parameters:
      multipliers - the scales along coordinates.
      Returns:
      the scaled pattern.
      Throws:
      NullPointerException - if the argument is null.
      IllegalArgumentException - if multipliers.length!=dimCount().
      TooLargePatternCoordinatesException - if the set of scaled points does not fulfil the restrictions, described in the comments to this interface, section "Coordinate restrictions".
      See Also:
    • projectionAlongAxis

      Pattern projectionAlongAxis(int coordIndex)
      Returns the projection of this pattern along the given axis. The number of dimensions in the resulting pattern (dimCount()) is less by 1, than in this one.

      More precisely, the resulting pattern consists of the points, obtained from all points of this pattern by the call point.projectionAlongAxis(coordIndex).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      There is a guarantee, that this method does not try to allocate much more memory, that it is required for storing this pattern itself, and that it never throws TooManyPointsInPatternError. For comparison, an attempt to do the same operation via getting all points (points() method), correcting them and forming a new pattern via Patterns.newPattern(java.util.Collection) will lead to TooManyPointsInPatternError / OutOfMemoryError for some forms of large patterns.

      Parameters:
      coordIndex - the index of the coordinate (0 for x-axis , 1 for y-axis, 2 for za-xis, etc.).
      Returns:
      the projection of this pattern (its dimCount() is equal to thisInstance.dimCount()-1).
      Throws:
      IndexOutOfBoundsException - if coordIndex<0 or coordIndex>=dimCount().
      IllegalStateException - if this pattern is 1-dimensional (dimCount()==1).
    • minBound

      Pattern minBound(int coordIndex)
      Returns the minimal boundary of this pattern along the given axis: a pattern consisting of all points of this pattern, for which there are no other points with less coordinate #coordIndex and same other coordinates. The number of dimensions in the resulting pattern (dimCount()) is the same as in this one.

      In other words, this method removes some points from this pattern according the following rule: if this pattern contains several points p0, p1, ..., pm−1 with identical projection to the given axis (pi.projectionAlongAxis(coordIndex).equals(pj.projectionAlongAxis(coordIndex)) for all ij), then the resulting pattern contains only one from these points, for which the given coordinate coord(coordIndex) has the minimal value.

      This method is especially useful for uniform-grid patterns. For example, in rectangular patterns this method returns one of the facets of the hyperparallelepiped. In most cases (including all rectangular patterns) this method returns the same result as UniformGridPattern.lowerSurface(int); but if the figure, described by this pattern, contains some "holes", the result of this method contains fewer points than UniformGridPattern.lowerSurface(int).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      Warning! If this object is not DirectPointSetPattern and is not RectangularPattern, this method can work slowly for some large patterns: the required time can be O(N), where N is the number of points. In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError. The situation is like in points() and roundedPoints() method.

      There is a guarantee, that if this object implements DirectPointSetPattern interface, then this method requires not greater than O(N) memory (N=pointCount()) and never throws TooManyPointsInPatternError.

      There is a guarantee, that if this object implements RectangularPattern interface, then this method works quickly (O(1) operations) and without exceptions.

      Parameters:
      coordIndex - the index of the coordinate (0 for x-axis , 1 for y-axis, 2 for za-xis, etc.).
      Returns:
      the minimal boundary of this pattern for the given axis.
      Throws:
      IndexOutOfBoundsException - if coordIndex<0 or coordIndex>=dimCount().
      TooManyPointsInPatternError - if this pattern is not DirectPointSetPattern and not RectangularPattern and if, at the same time, the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
      See Also:
    • maxBound

      Pattern maxBound(int coordIndex)
      Returns the maximal boundary of this pattern along the given axis: a pattern consisting of all points of this pattern, for which there are no other points with greater coordinate #coordIndex and same other coordinates. The number of dimensions in the resulting pattern (dimCount()) is the same as in this one.

      In other words, this method removes some points from this pattern according the following rule: if this pattern contains several points p0, p1, ..., pm−1 with identical projection to the given axis (pi.projectionAlongAxis(coordIndex).equals(pj.projectionAlongAxis(coordIndex)) for all ij), then the resulting pattern contains only one from these points, for which the given coordinate coord(coordIndex) has the maximal value.

      This method is especially useful for uniform-grid patterns. For example, in rectangular patterns this method returns one of the facets of the hyperparallelepiped. In most cases (including all rectangular patterns) this method returns the same result as UniformGridPattern.upperSurface(int); but if the figure, described by this pattern, contains some "holes", the result of this method contains fewer points than UniformGridPattern.upperSurface(int).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern

      The returned pattern always implements RectangularPattern if this pattern implements RectangularPattern.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      Warning! If this object is not DirectPointSetPattern and is not RectangularPattern, this method can work slowly for some large patterns: the required time can be O(N), where N is the number of points. In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError. The situation is like in points() and roundedPoints() method.

      There is a guarantee, that if this object implements DirectPointSetPattern interface, then this method requires not greater than O(N) memory (N=pointCount()) and never throws TooManyPointsInPatternError.

      There is a guarantee, that if this object implements RectangularPattern interface, then this method works quickly (O(1) operations) and without exceptions.

      Parameters:
      coordIndex - the index of the coordinate (0 for x-axis , 1 for y-axis, 2 for za-xis, etc.).
      Returns:
      the maximal boundary of this pattern for the given axis.
      Throws:
      IndexOutOfBoundsException - if coordIndex<0 or coordIndex>=dimCount().
      TooManyPointsInPatternError - if this pattern is not DirectPointSetPattern and not RectangularPattern and if, at the same time, the number of points is greater than Integer.MAX_VALUE or, in some rare situations, is near this limit (OutOfMemoryError can be also thrown instead of this exception).
      See Also:
    • carcass

      Pattern carcass()
      Returns the carcass of this pattern. We define the carcass of the pattern P as such point set C, that, for some integer n>=1:
      1. 2⊗P = P ⊕ C;
        4⊗P = (2⊗P) ⊕ 2C;
        8⊗P = (4⊗P) ⊕ 4C;
        ...
        2n⊗P = (2n−1⊗P) ⊕ 2n−1C;
      2. for any m=1,2,...,n and for any positive integer k≤2m−1, we have
        (2m−1+k)⊗P = (2m−1⊗P) ⊕ kC.

      Here A⊕B means the Minkowski sum of patterns A and B, k⊗P means P⊕P⊕...⊕P (k summands), and kP means the pointwise geometrical multiplication of the pattern P by the multiplier k, i.e. P.multiply(k).

      This method tries to find the minimal carcass, consisting of as little as possible number of points, and the maximal value n, for which the formulas above are correct for the found carcass. (The value 2n is called the maximal carcass multiplier and is returned by maxCarcassMultiplier() method.) For example, for rectangular patterns this method returns the set of vertices of the hyperparallelepiped (in one-dimensional case, the pair of segment ends), and the corresponding n=+∞. But this method does not guarantee that the returned result is always the minimal possible carcass and that the found n is really maximal for this carcass.

      This method allows to optimize calculation of the point set of a Minkowski multiple k⊗P. It is really used in the pattern implementations, returned by Patterns.newMinkowskiMultiplePattern(Pattern, int) method: the result of that method is not always an actual Minkowski sum of N equal patterns, but can be (in the best case) an equal Minkowski sum of ~log2N patterns P ⊕ C ⊕ 2C ⊕ ... ⊕ 2mC ⊕ (N−2mC), 2m<N≤2m+1, or (in not the best case, when N is greater than the maximal carcass multiplier 2n) can be another, not so little Minkowski sum.

      In the worst case (no optimization is possible), this method just returns this object (C=P), and maxCarcassMultiplier() returns 2 (i.e. n=1).

      The returned pattern has the same number of dimensions (dimCount()) as this one.

      The returned pattern always implements UniformGridPattern if this pattern implements UniformGridPattern.

      This method can require some time and memory for execution, but never throws TooManyPointsInPatternError.

      Returns:
      the carcass of this pattern.
    • maxCarcassMultiplier

      int maxCarcassMultiplier()
      Returns the maximal multiplier k, for which the calculation of the Minkowski multiple k⊗P can be optimized by using the carcass of this pattern P. Please see carcass() method for more information.

      Note: the returned value is always ≥2. If the correct value is greater than Integer.MAX_VALUE (for example, for rectangular patterns), this method returns Integer.MAX_VALUE; in all other cases the returning value is a power of two.

      This method can require some time and memory for execution, but never throws TooManyPointsInPatternError. Usually an implementation caches the results of carcass() and this methods, so this method works very quickly after the first call of carcass().

      Returns:
      the maximal multiplier (≥2), for which the calculation of the Minkowski multiple can be optimized by using the carcass.
    • minkowskiAdd

      Pattern minkowskiAdd(Pattern added)
      Calculates and returns the Minkowski sum of this and specified patterns. Briefly, the returned pattern consists of all points a+b, where a is any point of this pattern, b is any point of the argument "added" and "+" means a vector sum of two points (the result of "a.add(b)" call). Please see details in Wikipedia.

      Warning! This method can work slowly for some forms of large patterns. In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError.

      Warning: this method can fail with TooLargePatternCoordinatesException, if some of new points violate restrictions, described in the comments to this interface, section "Coordinate restrictions".

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern.

      The returned pattern always implements RectangularPattern if this pattern and subtracted argument implement RectangularPattern and both patterns have identical steps (i.e. thisPattern.stepsOfGridEqual(subtracted) returns true). In this case, this method works very quickly and without TooManyPointsInPatternError / OutOfMemoryError exceptions.

      Please draw attention: there is another way to build a Minkowski sum, namely the method Patterns.newMinkowskiSum(java.util.Collection). That method does not perform actual calculations and returns a special implementation of this interface (see comments to this interface, section "Complex patterns"). Unlike that method, this one tries to actually calculate the Minkowski sum, saving (when possible) the type of the original pattern: see above two guarantees about DirectPointSetPattern and RectangularPattern types. If it is impossible to represent the Minkowski sum by Java class of this pattern, it is probable that the result will be constructed as DirectPointSetUniformGridPattern or as SimplePattern.

      Parameters:
      added - another pattern.
      Returns:
      the Minkowski sum of this and another patterns.
      Throws:
      NullPointerException - if the argument is null.
      IllegalArgumentException - if the numbers of space dimensions of both patterns are different.
      TooManyPointsInPatternError - for some forms of large patterns, if the number of points in this, added or result pattern is greater than Integer.MAX_VALUE or, maybe, is near this limit
      TooLargePatternCoordinatesException - if the resulting set of points does not fulfil the restrictions, described in the comments to this interface, section "Coordinate restrictions".
      See Also:
    • minkowskiSubtract

      Pattern minkowskiSubtract(Pattern subtracted)
      Calculates and returns the erosion of this pattern by specified pattern or null if this erosion is the empty set. Briefly, the returned pattern consists of all such points p, that for any points b of the "subtracted" pattern the vector sum of two points p+b (the result of "p.add(b)" call) belongs to this pattern. Please see more details in Wikipedia and Google about the "Erosion" and "Minkowski subtraction" terms.

      Warning! This method can work slowly for some forms of large patterns. In these cases, this method can also throw TooManyPointsInPatternError or OutOfMemoryError.

      Warning: this method can fail with TooLargePatternCoordinatesException, if some of new points violate restrictions, described in the comments to this interface, section "Coordinate restrictions". But it is obvious, that this exception is impossible if the passed pattern "subtracted" contains the origin of coordinates (in this case, the result is a subset of this pattern).

      The returned pattern always implements DirectPointSetPattern if this pattern implements DirectPointSetPattern.

      The returned pattern always implements RectangularPattern if this pattern and subtracted argument implement RectangularPattern and both patterns have identical steps (i.e. thisPattern.stepsOfGridEqual(subtracted) returns true). In this case, this method works very quickly and without TooManyPointsInPatternError / OutOfMemoryError exceptions.

      Parameters:
      subtracted - another pattern.
      Returns:
      the erosion of this pattern by the specified pattern or null if this erosion is the empty set.
      Throws:
      NullPointerException - if the argument is null.
      IllegalArgumentException - if the numbers of space dimensions of both patterns are different.
      TooManyPointsInPatternError - for some forms of large patterns, if the number of points in this, subtracted or result pattern is greater than Integer.MAX_VALUE or, maybe, is near this limit
      TooLargePatternCoordinatesException - if the resulting set of points does not fulfil the restrictions, described in the comments to this interface, section "Coordinate restrictions".
      See Also:
    • minkowskiDecomposition

      List<Pattern> minkowskiDecomposition(int minimalPointCount)
      Returns the Minkowski decomposition: a non-empty list of patterns P0, P1, ..., Pn−1, such that this pattern P (the point set represented by it) is a Minkowski sum of them (of the point sets represented by them): P = P0 ⊕ P1 ⊕...⊕ Pn−1. In other words, each point p∈P of this pattern is equal to a vector sum of some n points p0, p1, ..., pn−1, where pi∈Pi. Please see Wikipedia about the "Minkowski sum" term.

      This method tries to find the best decomposition, that means the list of patterns with minimal summary number of points. For good pattern, the returned patterns list can consist of O(log2N) points (sum of pointCount() values for all returned patterns), where N is the number of points (pointCount()) in this pattern. For example, a linear one-dimensional segment {x: 0<=x<2m} is a Minkowski sum of m point pairs {0, 2i}, i=0,1,...,m-1.

      There is no guarantee that this method returns a good decomposition. If this method cannot find required decomposition, it returns the 1-element list containing this instance as the only element.

      If the number of points in this pattern is less than the argument, i.e. pointCount()<minimalPointCount, then this method probably does not decompose this pattern and returns the 1-element list containing this instance as its element. But it is not guaranteed: if the method "knows" some decomposition, but estimation of the number of points can require a lot of resources, this method may ignore minimalPointCount argument.

      However, there is a guarantee that if the number of points is 1 or 2, i.e. pointCount()≤2, then this method always returns the 1-element list containing this instance as its element.

      There is a guarantee that the elements of the resulting list cannot be further decomposed: this method, called for them with the same or larger minimalPointCount argument, always returns a list consisting of one element.

      The number of space dimensions in all returned patterns (dimCount() is the same as in this one.

      The result of this method is immutable (Collections.unmodifiableList).

      Parameters:
      minimalPointCount - this method usually does not decompose patterns that contain less than minimalPointCount points.
      Returns:
      the decomposition of this pattern to Minkowski sum; always contains ≥1 elements.
      Throws:
      IllegalArgumentException - if the argument is negative.
    • hasMinkowskiDecomposition

      boolean hasMinkowskiDecomposition()
      Returns true if and only if the Minkowski decomposition, returned by minkowskiDecomposition(0) call, consists of 2 or more patterns: minkowskiDecomposition(0).size()>1.

      In some situations this method works essentially faster then the actual minkowskiDecomposition(0) call.

      Note that if this method returns true, then pointCount() and largePointCount() methods can work very slowly and even may fail with OutOfMemoryError or TooManyPointsInPatternError.

      Returns:
      true if the Minkowski decomposition contains 2 or more elements.
    • unionDecomposition

      List<Pattern> unionDecomposition(int minimalPointCount)
      Returns a union decomposition: a non-empty list of patterns P0, P1, ..., Pn−1, such that this pattern P (the point set represented by it) is the set-theoretical union of them (of the point sets represented by them): P = P0 ∪ P1 ∪...∪ Pn−1.

      This method tries to find such decomposition, that all patterns Pi have good Minkowski decompositions and the summary number of points in all Minkowski decompositions Pi.minkowskiDecomposition(minimalPointCount) of all patterns, returned by this method, is as small as possible — usually much less than the number of points in this instance. If this pattern already has a good Minkowski decompositions, this method should return the 1-element list containing this instance as the only element.

      If the number of points in this pattern is less than the argument, i.e. pointCount()<minimalPointCount, then this method probably does not decompose this pattern and returns the 1-element list containing this instance as its element. Moreover, this method tries to build such decomposition, that every element Pi in the resulting list contains ≥minimalPointCount elements.

      There is a guarantee that the elements of the resulting list cannot be further decomposed: this method, called for them with the same or larger minimalPointCount argument, always returns a list consisting of one element.

      The number of space dimensions in all returned patterns (dimCount() is the same as in this one.

      The result of this method is immutable (Collections.unmodifiableList).

      Parameters:
      minimalPointCount - this method usually does not decompose patterns that contain less than minimalPointCount points.
      Returns:
      a decomposition of this pattern into the union of patterns; always contains ≥1 elements.
      Throws:
      IllegalArgumentException - if the argument is negative.
    • allUnionDecompositions

      List<List<Pattern>> allUnionDecompositions(int minimalPointCount)
      Returns a non-empty list of all best or almost best union decompositions with equal or similar "quality", i.e. with the same or almost same summary number of points in all Minkowski decompositions of all returned patterns.

      This method is a useful addition to unionDecomposition(int) method for a case, when there are several union decompositions with similar "quality". In this case an algorithm, using union decompositions, is able to choose the best from several variants according additional algorithm-specific criteria.

      The number of space dimensions in all returned patterns (dimCount() is the same as in this one.

      The result of this method and the elements of the result are immutable (Collections.unmodifiableList).

      Parameters:
      minimalPointCount - this method usually does not decompose patterns that contain less than minimalPointCount points.
      Returns:
      several good variants of decomposition of this pattern to the union of patterns; the result always contains ≥1 elements, and all its elements also contain ≥1 elements.
      Throws:
      IllegalArgumentException - if the argument is negative.