Examples of net.algart.math.patterns.Pattern

net.algart.math.patterns.Pattern
kipedia.org/wiki/Dilation_%28morphology%29">"Dilation" article in Wikipedia) with a very large pattern, created by {@link 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 {@link #minkowskiDecomposition(int)} call.
Coordinate restrictions

There are the following guarantees for coordinates of the points of any pattern:
1. if p=(x₀,x₁,...,x_n−1) is some point of the pattern, then − {@link #MAX_COORDINATE}≤x_j≤ {@link #MAX_COORDINATE}for all j; here this inequality means absolutely precise mathematical inequality;
2. if p=(x₀¹,x₁¹,...,x_n−1¹) and q=(x₀²,x₁²,...,x_n−1²) are some two points of the pattern, then |x_j¹−x_j²|≤ {@link #MAX_COORDINATE} for all j, where|x_j¹−x_j²| means the absolute value of mathematically precise difference (not the result of Java operators Math.abs(x_j¹−x_j²)). (This condition can be checked with help of {@link 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 {@link TooLargePatternCoordinatesException}.

Note: though patterns are sets of real points, their coordinates are restricted by long-type constant {@link #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 {@link 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 (x₀, x₁, ..., x_n−1) with a new point (round(x₀), round(x₁), ..., round(x_n−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(x₀), StrictMath.round(x₁), ..., StrictMath.round(x_n−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 {@link #round()} method for any pattern:it always constructs another allowed pattern, both in terms of this interface and in terms in {@link UniformGridPattern}, and cannot throw {@link TooLargePatternCoordinatesException}.

Theorem II. If all points of a pattern are integer, i.e. for all pattern's points (x₀, x₁, ..., x_n−1) we have x_j==(double)(long)x_j for any index j, and (X₀,X₁,...,X_n−1) is some point of this pattern, then you can subtract (using Java “−” operator) the coordinate X_j (j is any index) from the corresponding coordinate of all points of this pattern, i.e. replace each pattern's point (x₀, ..., x_j−1, x_j, x_j+1, ..., x_n−1) with (x₀, ..., x_j−1, x_j⊖X_j, x_j+1, ..., x_n−1), and the resulting point set will also be allowed. Here and below a⊖b (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 “a−b”.

Proof.

First of all, let's remind that the computer difference a⊖b, according IEEE 754 standard and Java language specification, is the nearest double value to the precise mathematical difference a−b. Because all pattern's points are integer, the restriction 2 allows to state that any difference x_j−X_j can be represented precisely by double type (see the comments to {@link #MAX_COORDINATE} constant).So, we have x_j⊖X_j = x_j−X_j: 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 X_j does not change the (mathematical!) differences |x_j¹−x_j²|. The new value of this coordinate for each point will be x_j−X_j, where both (x₀,x₁,...,x_n−1) and (X₀,X₁,...,X_n−1) are some points of the pattern; according the condition 2, this difference lies in range − {@link #MAX_COORDINATE}≤x_j−X_j≤ {@link #MAX_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 x_j−X_j 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 x₁=2251799813685248.00 (= {@link #MAX_COORDINATE}/2), x₂=−2251799813685248.00 (=− {@link #MAX_COORDINATE}/2) and x₃=−2251799813685247.75 (=− {@link #MAX_COORDINATE}/2+0.25), subtracting the point x₃ by Java “−” operator leads to the pattern x'₁=4503599627370496.00 (= {@link #MAX_COORDINATE}) (computer subtraction of double values leads to rounding here), x'₂=−0.25 and x'₃=0.0, which obviously violates the mathematically precise restriction 2: |x'₁−x'₂|> {@link #MAX_COORDINATE}.

As a result, there is an obvious conclusion. If p is one of the {@link #points() points} ofsome integer pattern (see above), then the method pattern. {@link #shift(Point) shift}(p. {@link Point#symmetric() symmetric()}) always works successfully and never throw {@link 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 {@link Patterns#newMinkowskiSum(Pattern) 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 10¹² 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 {@link Patterns#newMinkowskiSum(Pattern) Minkowski sums} ortwo {@link Patterns#newUnion(Pattern) 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.

AlgART Laboratory 2007–2014
@author Daniel Alievsky @version 1.2 @since JDK 1.5

        }
        if (p.isSurelyInteger()) {
            System.out.println("It is integer");
        }
        if (p.pointCount() < 1000) {
            Pattern samePoints = Patterns.newPattern(p.points());
            System.out.println("Pattern with same points: " + samePoints);
            if (samePoints instanceof UniformGridPattern && ((UniformGridPattern)samePoints).isActuallyRectangular()) {
                System.out.println("It is also rectangular");
            }
        }

View Full Code Here

            center[k] = Double.parseDouble(args[2 + k]);
        int minimalPointCountForDecomposition = Integer.parseInt(args[2 + center.length]);
        int numberOfIterations = args.length > 3 + center.length ? Integer.parseInt(args[3 + center.length]) : 1;
        System.out.println("Sphere with center " + Point.valueOf(center) + " and radius " + r);
        long t1 = System.nanoTime();
        Pattern p = Patterns.newSphereIntegerPattern(Point.valueOf(center), r);
        long t2 = System.nanoTime();
        System.out.printf(Locale.US, "Pattern created in %.3f ms: %s%n", (t2 - t1) * 1e-6, p);
        Set<Point> points = p.points();
        System.out.println(points.size() + " points");
        if (points.size() < 1000)
            System.out.println(new TreeSet<Point>(points));
        for (int iterationIndex = 1; iterationIndex <= numberOfIterations; iterationIndex++) {
            System.out.println();
            System.out.println("Iteration #" + iterationIndex);
            if (p instanceof UniformGridPattern && ((UniformGridPattern)p).isActuallyRectangular()) {
                System.out.println("It is rectangular");
            }
            if (p.isSurelySinglePoint()) {
                System.out.println("It is 1-point");
            }
            if (p.isSurelyOriginPoint()) {
                System.out.println("It is origin of coordinates");
            }
            if (p.isSurelyInteger()) {
                System.out.println("It is integer");
            }
            System.out.println("Minimal coordinates: " + p.coordMin());
            System.out.println("Maximal coordinates: " + p.coordMax());
            for (int k = 0; k < p.dimCount(); k++) {
                System.out.println("Range of coordinate #" + k + ": " + p.coordRange(k));
            }
            points = p.round().lowerSurface(iterationIndex % dimCount).points();
            System.out.println(points.size() + " left points along axis #" + iterationIndex % dimCount + ":");
            if (points.size() < 1000)
                System.out.println(new TreeSet<Point>(points));
            points = p.round().upperSurface(iterationIndex % dimCount).points();
            System.out.println(points.size() + " right points along axis #" + iterationIndex % dimCount + ":");
            if (points.size() < 1000)
                System.out.println(new TreeSet<Point>(points));
            points = p.round().surface().points();
            System.out.println(points.size() + " boundary:");
            if (points.size() < 1000)
                System.out.println(new TreeSet<Point>(points));
            t1 = System.nanoTime();
            List<Pattern> minkowskiDecomposition = p.minkowskiDecomposition(minimalPointCountForDecomposition);
            t2 = System.nanoTime();
            System.out.printf(Locale.US, "Minkowski decomposition to %d patterns (%.3f ms, %.3f ns / point):%n",
                minkowskiDecomposition.size(), (t2 - t1) * 1e-6, (t2 - t1) / (double)p.pointCount());
            for (Pattern q : minkowskiDecomposition) {
                System.out.println("    " + q);
            }
            System.out.println();


            t1 = System.nanoTime();
            List<List<Pattern>> allUnionDecompositions = p.allUnionDecompositions(minimalPointCountForDecomposition);
            t2 = System.nanoTime();
            for (int k = 0, n = allUnionDecompositions.size(); k < n; k++) {
                List<Pattern> unionDecomposition = allUnionDecompositions.get(k);
                System.out.printf(Locale.US, "Union decompositions #%d to %d patterns (%.3f ms, %.3f ns / point):%n",
                    k + 1, unionDecomposition.size(), (t2 - t1) * 1e-6, (t2 - t1) / (double) p.pointCount());
                for (Pattern q : unionDecomposition) {
                    System.out.println("    " + q
                        + (!q.hasMinkowskiDecomposition() ? " " + new TreeSet<IPoint>(q.roundedPoints()) : ""));
                }
                t1 = System.nanoTime();
                long totalPatternCount = 0, totalPointCount = 0;
                for (Pattern q : allUnionDecompositions.get(0)) {
                    List<Pattern> mink = q.minkowskiDecomposition(minimalPointCountForDecomposition);
                    totalPatternCount += mink.size();
                    for (Pattern s : mink)
                        totalPointCount += s.pointCount();
                }
                t2 = System.nanoTime();
                System.out.printf(Locale.US, "Minkowski decomposition of this union elements to %d patterns, "
                    + "%d total points (%.3f ms, %.3f ns / point)%n%n",
                    totalPatternCount, totalPointCount, (t2 - t1) * 1e-6, (t2 - t1) / (double)p.pointCount());
            }
        }
    }

View Full Code Here

 * @version 1.2
 * @since JDK 1.5
 */
public class LargePatternTest {
    public static void main(String[] args) {
        Pattern p1 = Patterns.newRectangularIntegerPattern(IPoint.valueOf(0, 0), IPoint.valueOf(20, 20));
        Set<IPoint> points = new HashSet<IPoint>();
        for (int k = 0; k < 1000; k++) {
            points.add(IPoint.valueOf(k, k));
            points.add(IPoint.valueOf(2000000000 + k, k));
            points.add(IPoint.valueOf(k, 2000000000 + k));
        }
        Pattern p2 = Patterns.newIntegerPattern(points);
        Pattern pSum = Patterns.newMinkowskiSum(p1, p2);
        System.out.println("Large sum: " + pSum + ", contains " + pSum.pointCount() + " points");
    }

View Full Code Here

            //     }
            // and if the checks "i < 0" lead to the same stable result (almost always true or, little better,
            // almost always false), then CPU can optimize this branching.
//            System.out.println("QUICK");
            final IPoint min = pattern.coordMin().toRoundedPoint();
            final Pattern shiftedPattern = pattern.shift(min.symmetric().toPoint()); // "normalized" coordinates >=0
            final Matrix<?> shiftedSrc = Matrices.asShifted(src, min.coordinates());
            Matrix<? extends UpdatablePArray> clone = Arrays.SMM.newMatrix(UpdatablePArray.class, src);
            Matrices.copy(arrayContext == null ? null : arrayContext.part(0.0, 0.05),
                clone, shiftedSrc);
            Matrix<? extends PArray> lazy = asProcessed(requiredType, clone, additionalMatrices, shiftedPattern);
            new Arrays.Copier(arrayContext == null ? null : arrayContext.part(0.05, 1.0),
                dest.array(), lazy.array(), 0, 1).process();
            // "1" allows to split into minimal number of ranges
            return;
        }
        boolean direct = sa instanceof DirectAccessible && ((DirectAccessible) sa).hasJavaArray();
        if (direct || !ENABLE_STREAMING) {
//            System.out.println("SIMPLE");
            Matrix<? extends PArray> lazy = asProcessed(requiredType, src, additionalMatrices, pattern);
            new Arrays.Copier(arrayContext, dest.array(), lazy.array(), 0, 1).process();
            // "1" allows to split into minimal number of ranges
            return;
        }
        assert bufSize < size;


        final IPoint min = pattern.coordMin().toRoundedPoint();
        final Pattern shiftedPattern = pattern.shift(min.symmetric().toPoint()); // "normalized" coordinates >=0
        final Matrix<? extends PArray> shiftedSrc = Matrices.asShifted(src, min.coordinates()).cast(PArray.class);


        final long[] dimensions = src.dimensions();
        final long lSize = Arrays.longMul(dimensions, 0, dimensions.length - 1);
        final long lastDim = dimensions[dimensions.length - 1];

View Full Code Here

TOP

Related Classes of net.algart.math.patterns.Pattern

net.algart.math.patterns.demo.LargePatternTest

net.algart.math.patterns.demo.RectangularPatternsDemo

net.algart.math.patterns.demo.SpherePatternsDemo

net.algart.matrices.StreamingApertureProcessor

All source code are property of their respective owners. Java is a trademark of Sun Microsystems, Inc and owned by ORACLE Inc. Contact coftware#gmail.com.

Examples of net.algart.math.patterns.Pattern

Coordinate restrictions

Note about equals()

Multithread compatibility

Related Classes of net.algart.math.patterns.Pattern

Note about `equals()`