Package net.algart.arrays

Class Matrices.Region

java.lang.Object
net.algart.arrays.Matrices.Region
Direct Known Subclasses:
Matrices.ConvexHyperpolyhedron, Matrices.Hyperparallelepiped, Matrices.Polygon2D
Enclosing class:
Matrices
public abstract static class Matrices.Region extends Object

Region in n-dimensional space. More precisely, this class defines a random set of points with integer coordinates in n-dimensional space. Though some kinds of regions are defined in terms of real coordinates, this class is useful for processing only integer points belonging to the region. This class is designed for copying/filling regions in AlgART matrices by

methods, where non-integer coordinates are needless.

This class is abstract and describes the region (set of points) by the only one simple abstract method contains(long...coordinates), which returns true if and only if the point with the specified coordinates belongs to the region. It is enough to implement this method to define a new region. In addition, this class always requires to specify coordinate ranges: such ranges that coordinates of all region points guaranteedly belong to them.

However, the region, constructed by this way, provides low performance of Matrices.copyRegion / Matrices.fillRegion methods, because the only way to process it is checking all points separately by contains(long...) method. Therefore, this class provides the additional method sectionAtLastCoordinate(long sectionCoordinateValue), which builds an intersection of this region with some hyperplane and returns this intersection as one or several regions with less number of dimensions. This method is not abstract (it is implemeneted via contains(long...) method by default), but an inheritor can offer much faster implementation for most cases — and all inheritors from this package really do it.

An idea of this method is the following. It allows to represent the n-dimensional region (a set of integer points) as a union of its (n−1)-dimensional sections: results of calls of sectionAtLastCoordinate for all possible values of its argument sectionCoordinateValue. Then every (n−1)-dimensional section can be similarly represented as a union of its (n−2)-dimensional sections, etc. But for 2-dimensional case most region types (in particular, all inhertiros of this class from this package) can return the required intersection (with a horizontal line) as one or several continuous segments: regions of special type (1-dimensional Hyperparallelepiped), which can be processes very quickly.

If an inheritor correctly implements sectionAtLastCoordinate and if this method does not use contains(long...) method and the parent (default) implementation Region.sectionAtLastCoordinate, then the inheritor is allowed not to implement contains(long...) method. Instead, it is enough to override isContainsSupported() method and return false by it. In this case, contains(long...) method should throw UnsupportedOperationException.

This class can represent an empty region (containing no points). The number of dimensions of the range is always positive (1, 2, ...).

This package offers the following implementations of the regions:

  1. Matrices.Hyperparallelepiped: the simplest possible region (a segment in 1-dimensional case, a rectangle in 2-dimensional case, a parallelepiped in 3-dimensional case);
  2. Matrices.ConvexHyperpolyhedron: an intersection of several n-dimensional half-spaces (in other words, a convex hyperpolyhedron);
  3. Matrices.Simplex: the simplest kind of n-dimensional hyperpolyhedron — a hyperpolyhedron with n+1 vertices (a segment in 1-dimensional case, a triangle in 2-dimensional case, a tetrahedron in 3-dimensional case);
  4. Matrices.Polygon2D: a random 2-dimensional polygon, maybe non-convex and even self-intersecting.

Note that all region types are always restricted by the hyperparallelepiped, defined by the coordinate ranges, so a region cannot be infinite.

Also note: this class and its inheritors from this package do not implement own equals and hashCode methods. So, this class does not provide a mechanism for comparing different regions.

Inheritors of this abstract class are usually immutable and always thread-safe: all methods of this class may be freely used while simultaneous accessing the same instance from several threads. All inheritors of this class from this package are immutable.

  • Constructor Details

    • Region

      protected Region(IRange[] coordRanges)
      Creates new instance of this class.

      The passed coordRanges array is cloned by this constructor: no references to it are maintained by the created object.

      Parameters:
      coordRanges - the ranges that guaranteedly contain coordinates of all points of this region (they will be returned by coordRanges() method).
      Throws:
      NullPointerException - if the coordRanges array some of its elements is null.
      IllegalArgumentException - if the passed array is empty (coordRanges.length==0).

  • Method Details

    • getSegment

      public static Matrices.Hyperparallelepiped getSegment(IRange xRange)
      Creates 1-dimensional segment, described by the given range. Equivalent to getHyperparallelepiped(xRange).
      Parameters:
      xRange - the range of the only coordinate of all points of the segment.
      Returns:
      the segment containing all points from the specified range (including minimal and maximal values).
      Throws:
      NullPointerException - if the argument is null.

    • getRectangle2D

      public static Matrices.Hyperparallelepiped getRectangle2D(IRange xRange, IRange yRange)
      Creates 2-dimensional rectangle with sides, parallel to coordinate axes, described by the given ranges of coordinates. Equivalent to getHyperparallelepiped(xRange, yRange).

      Note: an equivalent region can be constructed by getPolygon2D(double[][] vertices) method. But the region, constructed by this method, is processed little faster.

      Parameters:
      xRange - the x-projection of the rectangle.
      yRange - the y-projection of the rectangle.
      Returns:
      the rectangle xRange × yRange.
      Throws:
      NullPointerException - if one of the arguments is null.

    • getParallelepiped3D

      public static Matrices.Hyperparallelepiped getParallelepiped3D(IRange xRange, IRange yRange, IRange zRange)
      Creates 3-dimensional parallelepiped with edges, parallel to coordinate axes, described by the given ranges of coordinates. Equivalent to getHyperparallelepiped(xRange, yRange, zRange).
      Parameters:
      xRange - the x-projection of the rectangle.
      yRange - the y-projection of the rectangle.
      zRange - the z-projection of the rectangle.
      Returns:
      the parallelepiped xRange × yRange × zRange.
      Throws:
      NullPointerException - if one of the arguments is null.

    • getHyperparallelepiped

      public static Matrices.Hyperparallelepiped getHyperparallelepiped(IRange... coordRanges)
      Creates n-dimensional hyperparallelepiped with edges, parallel to coordinate axes, described by the given ranges of coordinates. More precisely, the returned region contains all such points (x0, x1, ..., xn−1), that
      coordRanges[0].min() ≤ x0 ≤ coordRanges[0].max(),
      coordRanges[1].min() ≤ x1 ≤ coordRanges[1].max(),
      ...,
      coordRanges[n-1].min() ≤ xn−1 ≤ coordRanges[n-1].max().

      The number n of dimensions of the created region is equal to coordRanges.length.

      The passed coordRanges array is cloned by this method: no references to it are maintained by the created object.

      Parameters:
      coordRanges - the ranges of coordinates of the hyperparallelepiped.
      Returns:
      the hyperparallelepiped coordRanges[0] × coordRanges[1] × ...
      Throws:
      NullPointerException - if the coordRanges array some of its elements is null.
      IllegalArgumentException - if the passed array is empty (coordRanges.length==0).

    • getTriangle2D

      public static Matrices.Simplex getTriangle2D(double x1, double y1, double x2, double y2, double x3, double y3)
      Creates 2-dimensional triangle with the specified coordinates of vertices. Equivalent to getSimplex(new double[][] {{x1,y1},{x2,y2},{x3,y3}}).

      The specified vertices must not lie in the same straight line.

      Note: an equivalent region can be constructed by getPolygon2D(double[][] vertices) method. But the region, constructed by this method, is processed little faster. On the other hand, getPolygon2D method works correcly even if the vertices lie in the same straight line.

      Parameters:
      x1 - the x-coordinate of the 1st vertex.
      y1 - the y-coordinate of the 1st vertex.
      x2 - the x-coordinate of the 2nd vertex.
      y2 - the y-coordinate of the 2nd vertex.
      x3 - the x-coordinate of the 3rd vertex.
      y3 - the y-coordinate of the 3rd vertex.
      Returns:
      the triangle with the specified vertices.
      Throws:
      DegeneratedSimplexException - if all vertices lies in the same straight line (as it is detected by analysing the coordinates via calculations with standard Java double numbers).

    • getTetrahedron3D

      public static Matrices.Simplex getTetrahedron3D(double x1, double y1, double z1, double x2, double y2, double z2, double x3, double y3, double z3, double x4, double y4, double z4)
      Creates 3-dimensional tetrahedron with the specified coordinates of vertices. Equivalent to getSimplex(new double[][] {{x1,y1,z1},{x2,y2,z2},{x3,y3,z3},{x4,y4,z4}}).

      The specified vertices must not lie in the same plane.

      Parameters:
      x1 - the x-coordinate of the 1st vertex.
      y1 - the y-coordinate of the 1st vertex.
      z1 - the z-coordinate of the 1st vertex.
      x2 - the x-coordinate of the 2nd vertex.
      y2 - the y-coordinate of the 2nd vertex.
      z2 - the z-coordinate of the 2nd vertex.
      x3 - the x-coordinate of the 3rd vertex.
      y3 - the y-coordinate of the 3rd vertex.
      z3 - the z-coordinate of the 3rd vertex.
      x4 - the x-coordinate of the 4th vertex.
      y4 - the y-coordinate of the 4th vertex.
      z4 - the z-coordinate of the 4th vertex.
      Returns:
      the tetrahedron with the specified vertices.
      Throws:
      DegeneratedSimplexException - if all vertices lies in the same plane (as it is detected by analysing the coordinates via calculations with standard Java double numbers).

    • getSimplex

      public static Matrices.Simplex getSimplex(double[][] vertices)
      Creates n-dimensional simplex with the specified coordinates of vertices. More precisely, this method creates a simplex — the simplest n-dimensional hyperpolyhedron with n+1 vertices, where the vertex #k (k=0,1,...,n) has the coordinates vertices[k][0], vertices[k][1], ..., vertices[k][n-1].

      The number n of dimensions of the created region is equal to vertices[k].length; this length must be same for all k. The number of vertices vertices.length must be equal to n+1.

      The points, lying precisely in the (hyper)facets of the simplex (in particular, the vertices), belong to the resulting region.

      The created region is defined in terms of real coordinates, but only integer points belonging to this region are really processed by methods of this package.

      The passed vertices array is deeply cloned by this method: no references to it or its elements are maintained by the created object.

      The specified vertices must not lie in the same (n−1)-dimensional hyperplane.

      Note: this method allocates two Java double[] arrays containing n+1 and n*(n+1) elements. We do not recommend create simplexes with large number of dimensions: this method can work very slowly when n is greater than 6–7.

      Parameters:
      vertices - coordinates of all vertices.
      Returns:
      the simplex with the specified vertices.
      Throws:
      NullPointerException - if the vertices array or some of its elements is null.
      IllegalArgumentException - if the vertices array or some of its elements is empty (has zero length), or if the length of some vertices[k] array is not equal to vertices[0].length+1.
      DegeneratedSimplexException - if all vertices lies in the same (n−1)-dimensional hyperplane (as it is detected by analysing the coordinates via calculations with standard Java double numbers).

    • getConvexHyperpolyhedron

      public static Matrices.ConvexHyperpolyhedron getConvexHyperpolyhedron(double[] a, double[] b, IRange... coordRanges)
      Creates n-dimensional convex hyperpolyhedron, which is an intersection of m n-dimensional half-spaces, specified by inequations aix ≤ bi (i=0,1,...,m−1), and the hyperparallelepiped, built by getHyperparallelepiped(IRange...coordRanges) method with the same coordRanges argument. Here aix means the scalar product of the line #i of the matrix A, passed by the first argument, and the vector of coordinates x=(x0,x1,...,xn−1). The elements of the matrix A must be listed, row by row, in the a array: A={aij}, aij=a[i*n+j], i is the index of the row (0..m-1), j is the index of the column (0..n-1), m=b.length. The elements of the vector b=(b0,b1,...,bm−1) must be listed in b argument. The length a.length of the a array must be equal to the product nm, where n=coordRanges.length, m=b.length. The number of inequations m can be any non-negative integer 0,1,2,...

      The number n of dimensions of the created region is equal to coordRanges.length.

      The points, lying precisely in the (hyper)facets of the hyperpolyhedron (in particular, the vertices), belong to the resulting region.

      The created region is defined in terms of real coordinates, but only integer points belonging to this region are really processed by methods of this package.

      The passed Java arrays are cloned by this method: no references to them are maintained by the created object.

      Parameters:
      a - the matrix of coefficients of the left side of inequations, defining the half-spaces.
      b - the values in the right side of inequations, defining the half-spaces.
      coordRanges - the ranges of coordinates of the containing hyperparallelepiped.
      Returns:
      the intersection of the specified half-spaces and hyperparallelepiped.
      Throws:
      NullPointerException - if one of the arguments is null or if some element of coordRanges array is null.
      IllegalArgumentException - if coordRanges.length==0, or if a.length!=coordRanges.length*b.length.

    • getPolygon2D

      public static Matrices.Polygon2D getPolygon2D(double[][] vertices)
      Creates 2-dimensional polygon with the specified coordinates of vertices. More precisely, this method creates a polygon with m=vertices.length vertices, where the vertex #k (k=0,1,...,m−1) has the coordinates xk=vertices[k][0], yk=vertices[k][1]. All arrays vertices[k] must consist of 2 elements.

      The created polygon can be non-convex and even self-intersecting. The vertices can be specified both in clockwise or in anticlockwise order. The points, lying precisely in the sides of the polygon (in particular, the vertices), belong to the resulting region.

      The created region is defined in terms of real coordinates, but only integer points belonging to this region are really processed by methods of this package.

      The passed vertices array is deeply cloned by this method: no references to it or its elements are maintained by the created object.

      Note: this method allocates two Java double[] arrays containing m elements.

      Parameters:
      vertices - coordinates of all vertices.
      Returns:
      the 2-dimensional polygon with the specified vertices.
      Throws:
      NullPointerException - if the vertices array or some of its elements is null.
      IllegalArgumentException - if the vertices array or some of its elements is empty (has zero length), or if the length of some vertices[k] array is not 2.

    • n

      public final int n()
      Returns the number of dimensions of this region. The returned value is always positive (1, 2, ...).
      Returns:
      the number of dimensions of this region.

    • coordRanges

      public final IRange[] coordRanges()
      Returns the coordinate ranges, passed to the constructor. The length of the returned array is equal to n().

      For Matrices.Hyperparallelepiped and Matrices.ConvexHyperpolyhedron classes, these ranges are the same as the corresponding argument of the instantiation methods (getHyperparallelepiped(IRange...) and getConvexHyperpolyhedron(double[], double[], IRange...)).

      For Matrices.Simplex and Matrices.Polygon2D classes, these ranges are calculated automatically as the minimal integer ranges, containing all vertices, passed to the instantiation methods (getSimplex(double[][]) and getPolygon2D(double[][])).

      The returned array is a clone of the internal array stored in this object.

      Returns:
      the ranges that guaranteedly contain coordinates of all points of this region.

    • coordRange

      public final IRange coordRange(int coordIndex)
      Returns the coordinate range #coordIndex. Equivalent to coordRanges()[coordIndex], but works faster.
      Parameters:
      coordIndex - the index of coordinate.
      Returns:
      the ranges that guaranteedly contain the coordinate #coordIndex of all points of this region.
      Throws:
      IndexOutOfBoundsException - if coordIndex<0 or coordIndex>=n().

    • isRectangular

      public boolean isRectangular()
      Returns true if this region is rectangular, that is if it contains the same set of integer points (points with integer coordinates) as some hyperparallelepiped. This method always returns false if this region is not rectangular, but there is no guarantee that it returns true when it is rectangular.

      This default implementation returns false. In Matrices.Hyperparallelepiped class this method returns true. In all other inheritors of this class, implemented in this package, it returns false.

      Returns:
      true if this region is rectangular.

    • contains

      public abstract boolean contains(long... coordinates)
      Returns true if and only if the point with the specified integer coordinates belongs to this region.

      The coordinates must contain at least n() elements. It can contain more than n() elements; then the extra elements will be ignored.

      Warning! Some inheritors of this class does not provide correct implementation of this method. In this case, isContainsSupported() method returns false and this method throws UnsupportedOperationException. So, you must always check the result of isContainsSupported() method before calling this one.

      However, this method must be correctly implemented, if this region is a 1-dimensional (n()==1) and isRectangular() method returns false.

      Note: even if the inheritor does not provide correct implementation of this method, it must always provide correct implementation of sectionAtLastCoordinate(long) method.

      Parameters:
      coordinates - the coordinates of the point: the first element is x, the second is y, ...
      Returns:
      true if and only if the point with the specified coordinates belongs to this region.
      Throws:
      NullPointerException - if the argument is null.
      IndexOutOfBoundsException - if the length of the passed array is less than n().
      UnsupportedOperationException - if the inheritor does not implement this operation.

    • isContainsSupported

      public boolean isContainsSupported()
      Indicates whether the method contains(long...) in this class works correctly. You should use contains(long...) method only if this method returns true; in other case, contains(long...) throws UnsupportedOperationException.

      This default implementation returns true. So, if you prefer not to implement contains(long...) method, you must override this method and return false. This method must return true if n()==1 && !isRectangular().

      Returns:
      true if contains(long...) method works correctly; otherwise contains(long...) method throws UnsupportedOperationException.

    • sectionAtLastCoordinate

      public Matrices.Region[] sectionAtLastCoordinate(long sectionCoordinateValue)
      Finds the intersection of this region with the hyperplane, described by the equation xn−1=sectionCoordinateValue, and returns this intersection as an array of (n−1)-dimensional regions. (Here xn−1 is the last coordinate of the points: y-coordinate in 2-dimensional case, z-coordinate in 3-dimensional case, etc.) If the intersection is empty, this method returns an empty array ("new Region[0]"). This method never returns null.

      This method must not be used if this region is 1-dimensional (n()==1). In this case, it throws IllegalStateException.

      This default implementation is based on contains(long...) method, which is supposed to be correctly implemented.

      Note: it is possible (in some rare exotic cases), that the regions, returned by this method, intersects with each other: some points will belong to 2 and more elements of the result. In particular, it is possible for Matrices.Polygon2D, if some sides of the polygon lie exactly at the horizontal y=sectionCoordinateValue.

      Implementations of this method in this packages, besides the implementation in Matrices.Polygon2D class, never return more than 1 region in the result.

      You must override this method if you prefer not to implement contains(long...) method (isContainsSupported() returns false). In this case, your implementation must not call contains(long...) method or super.sectionAtLastCoordinate(long).

      Parameters:
      sectionCoordinateValue - the value of the last coordinate.
      Returns:
      the intersection of this region and the (n−1)-dimensional hyperplane, corresponding to the specified value of the last coordinate (0, 1 or more regions, every region is (n−1)-dimensional).
      Throws:
      IllegalStateException - if this region is 1-dimensional (n()==1).

    • checkSectionAtLastCoordinate

      protected final boolean checkSectionAtLastCoordinate(long sectionCoordinateValue)
      Returns true if and only the specified coordinate value lies inside the corresponding coordinate range. In other words, returns the result of the following check: coordRange(n()-1).contains(coordinateValue). Besides this, this method checks the number of dimensions n() and throws IllegalStateException if n()==1.

      This method is usually called at the beginning of sectionAtLastCoordinate(long) method. If it returns false, that method returns an empty array.

      Parameters:
      sectionCoordinateValue - the value of the last coordinate.
      Returns:
      true if and only the specified coordinate value lies inside the corresponding coordinate range.
      Throws:
      IllegalStateException - if this region is 1-dimensional (n()==1).