http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java b/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java deleted file mode 100644 index 2a63bbb..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java +++ /dev/null @@ -1,134 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.genetics; - -import java.util.ArrayList; -import java.util.List; - -import org.apache.commons.math3.exception.DimensionMismatchException; -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.OutOfRangeException; -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.random.RandomGenerator; - -/** - * Perform Uniform Crossover [UX] on the specified chromosomes. A fixed mixing - * ratio is used to combine genes from the first and second parents, e.g. using a - * ratio of 0.5 would result in approximately 50% of genes coming from each - * parent. This is typically a poor method of crossover, but empirical evidence - * suggests that it is more exploratory and results in a larger part of the - * problem space being searched. - * <p> - * This crossover policy evaluates each gene of the parent chromosomes by chosing a - * uniform random number {@code p} in the range [0, 1]. If {@code p} < {@code ratio}, - * the parent genes are swapped. This means with a ratio of 0.7, 30% of the genes from the - * first parent and 70% from the second parent will be selected for the first offspring (and - * vice versa for the second offspring). - * <p> - * This policy works only on {@link AbstractListChromosome}, and therefore it - * is parameterized by T. Moreover, the chromosomes must have same lengths. - * - * @see <a href="http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29";>Crossover techniques (Wikipedia)</a> - * @see <a href="http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php";>Crossover (Obitko.com)</a> - * @see <a href="http://www.tomaszgwiazda.com/uniformX.htm";>Uniform crossover</a> - * @param <T> generic type of the {@link AbstractListChromosome}s for crossover - * @since 3.1 - */ -public class UniformCrossover<T> implements CrossoverPolicy { - - /** The mixing ratio. */ - private final double ratio; - - /** - * Creates a new {@link UniformCrossover} policy using the given mixing ratio. - * - * @param ratio the mixing ratio - * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range - */ - public UniformCrossover(final double ratio) throws OutOfRangeException { - if (ratio < 0.0d || ratio > 1.0d) { - throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d); - } - this.ratio = ratio; - } - - /** - * Returns the mixing ratio used by this {@link CrossoverPolicy}. - * - * @return the mixing ratio - */ - public double getRatio() { - return ratio; - } - - /** - * {@inheritDoc} - * - * @throws MathIllegalArgumentException iff one of the chromosomes is - * not an instance of {@link AbstractListChromosome} - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - @SuppressWarnings("unchecked") - public ChromosomePair crossover(final Chromosome first, final Chromosome second) - throws DimensionMismatchException, MathIllegalArgumentException { - - if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { - throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME); - } - return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second); - } - - /** - * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover. - * - * @param first the first chromosome - * @param second the second chromosome - * @return the pair of new chromosomes that resulted from the crossover - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - private ChromosomePair mate(final AbstractListChromosome<T> first, - final AbstractListChromosome<T> second) throws DimensionMismatchException { - final int length = first.getLength(); - if (length != second.getLength()) { - throw new DimensionMismatchException(second.getLength(), length); - } - - // array representations of the parents - final List<T> parent1Rep = first.getRepresentation(); - final List<T> parent2Rep = second.getRepresentation(); - // and of the children - final List<T> child1Rep = new ArrayList<T>(length); - final List<T> child2Rep = new ArrayList<T>(length); - - final RandomGenerator random = GeneticAlgorithm.getRandomGenerator(); - - for (int index = 0; index < length; index++) { - - if (random.nextDouble() < ratio) { - // swap the bits -> take other parent - child1Rep.add(parent2Rep.get(index)); - child2Rep.add(parent1Rep.get(index)); - } else { - child1Rep.add(parent1Rep.get(index)); - child2Rep.add(parent2Rep.get(index)); - } - } - - return new ChromosomePair(first.newFixedLengthChromosome(child1Rep), - second.newFixedLengthChromosome(child2Rep)); - } -}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/package-info.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/package-info.java b/src/main/java/org/apache/commons/math3/genetics/package-info.java deleted file mode 100644 index 5c145e8..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/package-info.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/** - * This package provides Genetic Algorithms components and implementations. - */ -package org.apache.commons.math3.genetics; http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/Point.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/Point.java b/src/main/java/org/apache/commons/math3/geometry/Point.java deleted file mode 100644 index 1504d2e..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/Point.java +++ /dev/null @@ -1,46 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry; - -import java.io.Serializable; - -/** This interface represents a generic geometrical point. - * @param <S> Type of the space. - * @see Space - * @see Vector - * @since 3.3 - */ -public interface Point<S extends Space> extends Serializable { - - /** Get the space to which the point belongs. - * @return containing space - */ - Space getSpace(); - - /** - * Returns true if any coordinate of this point is NaN; false otherwise - * @return true if any coordinate of this point is NaN; false otherwise - */ - boolean isNaN(); - - /** Compute the distance between the instance and another point. - * @param p second point - * @return the distance between the instance and p - */ - double distance(Point<S> p); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/Space.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/Space.java b/src/main/java/org/apache/commons/math3/geometry/Space.java deleted file mode 100644 index 7f72439..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/Space.java +++ /dev/null @@ -1,42 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry; - -import java.io.Serializable; - -import org.apache.commons.math3.exception.MathUnsupportedOperationException; - -/** This interface represents a generic space, with affine and vectorial counterparts. - * @see Vector - * @since 3.0 - */ -public interface Space extends Serializable { - - /** Get the dimension of the space. - * @return dimension of the space - */ - int getDimension(); - - /** Get the n-1 dimension subspace of this space. - * @return n-1 dimension sub-space of this space - * @see #getDimension() - * @exception MathUnsupportedOperationException for dimension-1 spaces - * which do not have sub-spaces - */ - Space getSubSpace() throws MathUnsupportedOperationException; - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/Vector.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/Vector.java b/src/main/java/org/apache/commons/math3/geometry/Vector.java deleted file mode 100644 index f22f7a1..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/Vector.java +++ /dev/null @@ -1,155 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry; - -import java.text.NumberFormat; - -import org.apache.commons.math3.exception.MathArithmeticException; - -/** This interface represents a generic vector in a vectorial space or a point in an affine space. - * @param <S> Type of the space. - * @see Space - * @see Point - * @since 3.0 - */ -public interface Vector<S extends Space> extends Point<S> { - - /** Get the null vector of the vectorial space or origin point of the affine space. - * @return null vector of the vectorial space or origin point of the affine space - */ - Vector<S> getZero(); - - /** Get the L<sub>1</sub> norm for the vector. - * @return L<sub>1</sub> norm for the vector - */ - double getNorm1(); - - /** Get the L<sub>2</sub> norm for the vector. - * @return Euclidean norm for the vector - */ - double getNorm(); - - /** Get the square of the norm for the vector. - * @return square of the Euclidean norm for the vector - */ - double getNormSq(); - - /** Get the L<sub>∞</sub> norm for the vector. - * @return L<sub>∞</sub> norm for the vector - */ - double getNormInf(); - - /** Add a vector to the instance. - * @param v vector to add - * @return a new vector - */ - Vector<S> add(Vector<S> v); - - /** Add a scaled vector to the instance. - * @param factor scale factor to apply to v before adding it - * @param v vector to add - * @return a new vector - */ - Vector<S> add(double factor, Vector<S> v); - - /** Subtract a vector from the instance. - * @param v vector to subtract - * @return a new vector - */ - Vector<S> subtract(Vector<S> v); - - /** Subtract a scaled vector from the instance. - * @param factor scale factor to apply to v before subtracting it - * @param v vector to subtract - * @return a new vector - */ - Vector<S> subtract(double factor, Vector<S> v); - - /** Get the opposite of the instance. - * @return a new vector which is opposite to the instance - */ - Vector<S> negate(); - - /** Get a normalized vector aligned with the instance. - * @return a new normalized vector - * @exception MathArithmeticException if the norm is zero - */ - Vector<S> normalize() throws MathArithmeticException; - - /** Multiply the instance by a scalar. - * @param a scalar - * @return a new vector - */ - Vector<S> scalarMultiply(double a); - - /** - * Returns true if any coordinate of this vector is infinite and none are NaN; - * false otherwise - * @return true if any coordinate of this vector is infinite and none are NaN; - * false otherwise - */ - boolean isInfinite(); - - /** Compute the distance between the instance and another vector according to the L<sub>1</sub> norm. - * <p>Calling this method is equivalent to calling: - * <code>q.subtract(p).getNorm1()</code> except that no intermediate - * vector is built</p> - * @param v second vector - * @return the distance between the instance and p according to the L<sub>1</sub> norm - */ - double distance1(Vector<S> v); - - /** Compute the distance between the instance and another vector according to the L<sub>2</sub> norm. - * <p>Calling this method is equivalent to calling: - * <code>q.subtract(p).getNorm()</code> except that no intermediate - * vector is built</p> - * @param v second vector - * @return the distance between the instance and p according to the L<sub>2</sub> norm - */ - double distance(Vector<S> v); - - /** Compute the distance between the instance and another vector according to the L<sub>∞</sub> norm. - * <p>Calling this method is equivalent to calling: - * <code>q.subtract(p).getNormInf()</code> except that no intermediate - * vector is built</p> - * @param v second vector - * @return the distance between the instance and p according to the L<sub>∞</sub> norm - */ - double distanceInf(Vector<S> v); - - /** Compute the square of the distance between the instance and another vector. - * <p>Calling this method is equivalent to calling: - * <code>q.subtract(p).getNormSq()</code> except that no intermediate - * vector is built</p> - * @param v second vector - * @return the square of the distance between the instance and p - */ - double distanceSq(Vector<S> v); - - /** Compute the dot-product of the instance and another vector. - * @param v second vector - * @return the dot product this.v - */ - double dotProduct(Vector<S> v); - - /** Get a string representation of this vector. - * @param format the custom format for components - * @return a string representation of this vector - */ - String toString(final NumberFormat format); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/VectorFormat.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/VectorFormat.java b/src/main/java/org/apache/commons/math3/geometry/VectorFormat.java deleted file mode 100644 index b58d765..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/VectorFormat.java +++ /dev/null @@ -1,290 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.geometry; - -import java.text.FieldPosition; -import java.text.NumberFormat; -import java.text.ParsePosition; -import java.util.Locale; - -import org.apache.commons.math3.util.CompositeFormat; -import org.apache.commons.math3.exception.MathParseException; - -/** - * Formats a vector in components list format "{x; y; ...}". - * <p>The prefix and suffix "{" and "}" and the separator "; " can be replaced by - * any user-defined strings. The number format for components can be configured.</p> - * <p>White space is ignored at parse time, even if it is in the prefix, suffix - * or separator specifications. So even if the default separator does include a space - * character that is used at format time, both input string "{1;1;1}" and - * " { 1 ; 1 ; 1 } " will be parsed without error and the same vector will be - * returned. In the second case, however, the parse position after parsing will be - * just after the closing curly brace, i.e. just before the trailing space.</p> - * <p><b>Note:</b> using "," as a separator may interfere with the grouping separator - * of the default {@link NumberFormat} for the current locale. Thus it is advised - * to use a {@link NumberFormat} instance with disabled grouping in such a case.</p> - * - * @param <S> Type of the space. - * @since 3.0 - */ -public abstract class VectorFormat<S extends Space> { - - /** The default prefix: "{". */ - public static final String DEFAULT_PREFIX = "{"; - - /** The default suffix: "}". */ - public static final String DEFAULT_SUFFIX = "}"; - - /** The default separator: ", ". */ - public static final String DEFAULT_SEPARATOR = "; "; - - /** Prefix. */ - private final String prefix; - - /** Suffix. */ - private final String suffix; - - /** Separator. */ - private final String separator; - - /** Trimmed prefix. */ - private final String trimmedPrefix; - - /** Trimmed suffix. */ - private final String trimmedSuffix; - - /** Trimmed separator. */ - private final String trimmedSeparator; - - /** The format used for components. */ - private final NumberFormat format; - - /** - * Create an instance with default settings. - * <p>The instance uses the default prefix, suffix and separator: - * "{", "}", and "; " and the default number format for components.</p> - */ - protected VectorFormat() { - this(DEFAULT_PREFIX, DEFAULT_SUFFIX, DEFAULT_SEPARATOR, - CompositeFormat.getDefaultNumberFormat()); - } - - /** - * Create an instance with a custom number format for components. - * @param format the custom format for components. - */ - protected VectorFormat(final NumberFormat format) { - this(DEFAULT_PREFIX, DEFAULT_SUFFIX, DEFAULT_SEPARATOR, format); - } - - /** - * Create an instance with custom prefix, suffix and separator. - * @param prefix prefix to use instead of the default "{" - * @param suffix suffix to use instead of the default "}" - * @param separator separator to use instead of the default "; " - */ - protected VectorFormat(final String prefix, final String suffix, - final String separator) { - this(prefix, suffix, separator, CompositeFormat.getDefaultNumberFormat()); - } - - /** - * Create an instance with custom prefix, suffix, separator and format - * for components. - * @param prefix prefix to use instead of the default "{" - * @param suffix suffix to use instead of the default "}" - * @param separator separator to use instead of the default "; " - * @param format the custom format for components. - */ - protected VectorFormat(final String prefix, final String suffix, - final String separator, final NumberFormat format) { - this.prefix = prefix; - this.suffix = suffix; - this.separator = separator; - trimmedPrefix = prefix.trim(); - trimmedSuffix = suffix.trim(); - trimmedSeparator = separator.trim(); - this.format = format; - } - - /** - * Get the set of locales for which point/vector formats are available. - * <p>This is the same set as the {@link NumberFormat} set.</p> - * @return available point/vector format locales. - */ - public static Locale[] getAvailableLocales() { - return NumberFormat.getAvailableLocales(); - } - - /** - * Get the format prefix. - * @return format prefix. - */ - public String getPrefix() { - return prefix; - } - - /** - * Get the format suffix. - * @return format suffix. - */ - public String getSuffix() { - return suffix; - } - - /** - * Get the format separator between components. - * @return format separator. - */ - public String getSeparator() { - return separator; - } - - /** - * Get the components format. - * @return components format. - */ - public NumberFormat getFormat() { - return format; - } - - /** - * Formats a {@link Vector} object to produce a string. - * @param vector the object to format. - * @return a formatted string. - */ - public String format(Vector<S> vector) { - return format(vector, new StringBuffer(), new FieldPosition(0)).toString(); - } - - /** - * Formats a {@link Vector} object to produce a string. - * @param vector the object to format. - * @param toAppendTo where the text is to be appended - * @param pos On input: an alignment field, if desired. On output: the - * offsets of the alignment field - * @return the value passed in as toAppendTo. - */ - public abstract StringBuffer format(Vector<S> vector, - StringBuffer toAppendTo, FieldPosition pos); - - /** - * Formats the coordinates of a {@link Vector} to produce a string. - * @param toAppendTo where the text is to be appended - * @param pos On input: an alignment field, if desired. On output: the - * offsets of the alignment field - * @param coordinates coordinates of the object to format. - * @return the value passed in as toAppendTo. - */ - protected StringBuffer format(StringBuffer toAppendTo, FieldPosition pos, - double ... coordinates) { - - pos.setBeginIndex(0); - pos.setEndIndex(0); - - // format prefix - toAppendTo.append(prefix); - - // format components - for (int i = 0; i < coordinates.length; ++i) { - if (i > 0) { - toAppendTo.append(separator); - } - CompositeFormat.formatDouble(coordinates[i], format, toAppendTo, pos); - } - - // format suffix - toAppendTo.append(suffix); - - return toAppendTo; - - } - - /** - * Parses a string to produce a {@link Vector} object. - * @param source the string to parse - * @return the parsed {@link Vector} object. - * @throws MathParseException if the beginning of the specified string - * cannot be parsed. - */ - public abstract Vector<S> parse(String source) throws MathParseException; - - /** - * Parses a string to produce a {@link Vector} object. - * @param source the string to parse - * @param pos input/output parsing parameter. - * @return the parsed {@link Vector} object. - */ - public abstract Vector<S> parse(String source, ParsePosition pos); - - /** - * Parses a string to produce an array of coordinates. - * @param dimension dimension of the space - * @param source the string to parse - * @param pos input/output parsing parameter. - * @return coordinates array. - */ - protected double[] parseCoordinates(int dimension, String source, ParsePosition pos) { - - int initialIndex = pos.getIndex(); - double[] coordinates = new double[dimension]; - - // parse prefix - CompositeFormat.parseAndIgnoreWhitespace(source, pos); - if (!CompositeFormat.parseFixedstring(source, trimmedPrefix, pos)) { - return null; - } - - for (int i = 0; i < dimension; ++i) { - - // skip whitespace - CompositeFormat.parseAndIgnoreWhitespace(source, pos); - - // parse separator - if (i > 0 && !CompositeFormat.parseFixedstring(source, trimmedSeparator, pos)) { - return null; - } - - // skip whitespace - CompositeFormat.parseAndIgnoreWhitespace(source, pos); - - // parse coordinate - Number c = CompositeFormat.parseNumber(source, format, pos); - if (c == null) { - // invalid coordinate - // set index back to initial, error index should already be set - pos.setIndex(initialIndex); - return null; - } - - // store coordinate - coordinates[i] = c.doubleValue(); - - } - - // parse suffix - CompositeFormat.parseAndIgnoreWhitespace(source, pos); - if (!CompositeFormat.parseFixedstring(source, trimmedSuffix, pos)) { - return null; - } - - return coordinates; - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java b/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java deleted file mode 100644 index 9b2588a..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/enclosing/Encloser.java +++ /dev/null @@ -1,36 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.enclosing; - -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** Interface for algorithms computing enclosing balls. - * @param <S> Space type. - * @param <P> Point type. - * @see EnclosingBall - * @since 3.3 - */ -public interface Encloser<S extends Space, P extends Point<S>> { - - /** Find a ball enclosing a list of points. - * @param points points to enclose - * @return enclosing ball - */ - EnclosingBall<S, P> enclose(Iterable<P> points); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java b/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java deleted file mode 100644 index eedbd46..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/enclosing/EnclosingBall.java +++ /dev/null @@ -1,103 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.enclosing; - -import java.io.Serializable; - -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** This class represents a ball enclosing some points. - * @param <S> Space type. - * @param <P> Point type. - * @see Space - * @see Point - * @see Encloser - * @since 3.3 - */ -public class EnclosingBall<S extends Space, P extends Point<S>> implements Serializable { - - /** Serializable UID. */ - private static final long serialVersionUID = 20140126L; - - /** Center of the ball. */ - private final P center; - - /** Radius of the ball. */ - private final double radius; - - /** Support points used to define the ball. */ - private final P[] support; - - /** Simple constructor. - * @param center center of the ball - * @param radius radius of the ball - * @param support support points used to define the ball - */ - public EnclosingBall(final P center, final double radius, final P ... support) { - this.center = center; - this.radius = radius; - this.support = support.clone(); - } - - /** Get the center of the ball. - * @return center of the ball - */ - public P getCenter() { - return center; - } - - /** Get the radius of the ball. - * @return radius of the ball (can be negative if the ball is empty) - */ - public double getRadius() { - return radius; - } - - /** Get the support points used to define the ball. - * @return support points used to define the ball - */ - public P[] getSupport() { - return support.clone(); - } - - /** Get the number of support points used to define the ball. - * @return number of support points used to define the ball - */ - public int getSupportSize() { - return support.length; - } - - /** Check if a point is within the ball or at boundary. - * @param point point to test - * @return true if the point is within the ball or at boundary - */ - public boolean contains(final P point) { - return point.distance(center) <= radius; - } - - /** Check if a point is within an enlarged ball or at boundary. - * @param point point to test - * @param margin margin to consider - * @return true if the point is within the ball enlarged - * by the margin or at boundary - */ - public boolean contains(final P point, final double margin) { - return point.distance(center) <= radius + margin; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java b/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java deleted file mode 100644 index 3a0f875..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/enclosing/SupportBallGenerator.java +++ /dev/null @@ -1,42 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.enclosing; - -import java.util.List; - -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** Interface for generating balls based on support points. - * <p> - * This generator is used in the {@link WelzlEncloser Emo Welzl} algorithm - * and its derivatives. - * </p> - * @param <S> Space type. - * @param <P> Point type. - * @see EnclosingBall - * @since 3.3 - */ -public interface SupportBallGenerator<S extends Space, P extends Point<S>> { - - /** Create a ball whose boundary lies on prescribed support points. - * @param support support points (may be empty) - * @return ball whose boundary lies on the prescribed support points - */ - EnclosingBall<S, P> ballOnSupport(List<P> support); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java b/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java deleted file mode 100644 index 987e7d9..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/enclosing/WelzlEncloser.java +++ /dev/null @@ -1,181 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.enclosing; - -import java.util.ArrayList; -import java.util.List; - -import org.apache.commons.math3.exception.MathInternalError; -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Space; - -/** Class implementing Emo Welzl algorithm to find the smallest enclosing ball in linear time. - * <p> - * The class implements the algorithm described in paper <a - * href="http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf";>Smallest - * Enclosing Disks (Balls and Ellipsoids)</a> by Emo Welzl, Lecture Notes in Computer Science - * 555 (1991) 359-370. The pivoting improvement published in the paper <a - * href="http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf";>Fast and - * Robust Smallest Enclosing Balls</a>, by Bernd Gärtner and further modified in - * paper <a - * href=http://www.idt.mdh.se/kurser/ct3340/ht12/MINICONFERENCE/FinalPapers/ircse12_submission_30.pdf";> - * Efficient Computation of Smallest Enclosing Balls in Three Dimensions</a> by Linus Källberg - * to avoid performing local copies of data have been included. - * </p> - * @param <S> Space type. - * @param <P> Point type. - * @since 3.3 - */ -public class WelzlEncloser<S extends Space, P extends Point<S>> implements Encloser<S, P> { - - /** Tolerance below which points are consider to be identical. */ - private final double tolerance; - - /** Generator for balls on support. */ - private final SupportBallGenerator<S, P> generator; - - /** Simple constructor. - * @param tolerance below which points are consider to be identical - * @param generator generator for balls on support - */ - public WelzlEncloser(final double tolerance, final SupportBallGenerator<S, P> generator) { - this.tolerance = tolerance; - this.generator = generator; - } - - /** {@inheritDoc} */ - public EnclosingBall<S, P> enclose(final Iterable<P> points) { - - if (points == null || !points.iterator().hasNext()) { - // return an empty ball - return generator.ballOnSupport(new ArrayList<P>()); - } - - // Emo Welzl algorithm with Bernd Gärtner and Linus Källberg improvements - return pivotingBall(points); - - } - - /** Compute enclosing ball using Gärtner's pivoting heuristic. - * @param points points to be enclosed - * @return enclosing ball - */ - private EnclosingBall<S, P> pivotingBall(final Iterable<P> points) { - - final P first = points.iterator().next(); - final List<P> extreme = new ArrayList<P>(first.getSpace().getDimension() + 1); - final List<P> support = new ArrayList<P>(first.getSpace().getDimension() + 1); - - // start with only first point selected as a candidate support - extreme.add(first); - EnclosingBall<S, P> ball = moveToFrontBall(extreme, extreme.size(), support); - - while (true) { - - // select the point farthest to current ball - final P farthest = selectFarthest(points, ball); - - if (ball.contains(farthest, tolerance)) { - // we have found a ball containing all points - return ball; - } - - // recurse search, restricted to the small subset containing support and farthest point - support.clear(); - support.add(farthest); - EnclosingBall<S, P> savedBall = ball; - ball = moveToFrontBall(extreme, extreme.size(), support); - if (ball.getRadius() < savedBall.getRadius()) { - // this should never happen - throw new MathInternalError(); - } - - // it was an interesting point, move it to the front - // according to Gärtner's heuristic - extreme.add(0, farthest); - - // prune the least interesting points - extreme.subList(ball.getSupportSize(), extreme.size()).clear(); - - - } - } - - /** Compute enclosing ball using Welzl's move to front heuristic. - * @param extreme subset of extreme points - * @param nbExtreme number of extreme points to consider - * @param support points that must belong to the ball support - * @return enclosing ball, for the extreme subset only - */ - private EnclosingBall<S, P> moveToFrontBall(final List<P> extreme, final int nbExtreme, - final List<P> support) { - - // create a new ball on the prescribed support - EnclosingBall<S, P> ball = generator.ballOnSupport(support); - - if (ball.getSupportSize() <= ball.getCenter().getSpace().getDimension()) { - - for (int i = 0; i < nbExtreme; ++i) { - final P pi = extreme.get(i); - if (!ball.contains(pi, tolerance)) { - - // we have found an outside point, - // enlarge the ball by adding it to the support - support.add(pi); - ball = moveToFrontBall(extreme, i, support); - support.remove(support.size() - 1); - - // it was an interesting point, move it to the front - // according to Welzl's heuristic - for (int j = i; j > 0; --j) { - extreme.set(j, extreme.get(j - 1)); - } - extreme.set(0, pi); - - } - } - - } - - return ball; - - } - - /** Select the point farthest to the current ball. - * @param points points to be enclosed - * @param ball current ball - * @return farthest point - */ - public P selectFarthest(final Iterable<P> points, final EnclosingBall<S, P> ball) { - - final P center = ball.getCenter(); - P farthest = null; - double dMax = -1.0; - - for (final P point : points) { - final double d = point.distance(center); - if (d > dMax) { - farthest = point; - dMax = d; - } - } - - return farthest; - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java b/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java deleted file mode 100644 index 20462a1..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/enclosing/package-info.java +++ /dev/null @@ -1,24 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/** - * - * <p> - * This package provides interfaces and classes related to the smallest enclosing ball problem. - * </p> - * - */ -package org.apache.commons.math3.geometry.enclosing; http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Euclidean1D.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Euclidean1D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Euclidean1D.java deleted file mode 100644 index 14d130d..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Euclidean1D.java +++ /dev/null @@ -1,100 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.geometry.euclidean.oned; - -import java.io.Serializable; - -import org.apache.commons.math3.exception.MathUnsupportedOperationException; -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.geometry.Space; - -/** - * This class implements a one-dimensional space. - * @since 3.0 - */ -public class Euclidean1D implements Serializable, Space { - - /** Serializable version identifier. */ - private static final long serialVersionUID = -1178039568877797126L; - - /** Private constructor for the singleton. - */ - private Euclidean1D() { - } - - /** Get the unique instance. - * @return the unique instance - */ - public static Euclidean1D getInstance() { - return LazyHolder.INSTANCE; - } - - /** {@inheritDoc} */ - public int getDimension() { - return 1; - } - - /** {@inheritDoc} - * <p> - * As the 1-dimension Euclidean space does not have proper sub-spaces, - * this method always throws a {@link NoSubSpaceException} - * </p> - * @return nothing - * @throws NoSubSpaceException in all cases - */ - public Space getSubSpace() throws NoSubSpaceException { - throw new NoSubSpaceException(); - } - - // CHECKSTYLE: stop HideUtilityClassConstructor - /** Holder for the instance. - * <p>We use here the Initialization On Demand Holder Idiom.</p> - */ - private static class LazyHolder { - /** Cached field instance. */ - private static final Euclidean1D INSTANCE = new Euclidean1D(); - } - // CHECKSTYLE: resume HideUtilityClassConstructor - - /** Handle deserialization of the singleton. - * @return the singleton instance - */ - private Object readResolve() { - // return the singleton instance - return LazyHolder.INSTANCE; - } - - /** Specialized exception for inexistent sub-space. - * <p> - * This exception is thrown when attempting to get the sub-space of a one-dimensional space - * </p> - */ - public static class NoSubSpaceException extends MathUnsupportedOperationException { - - /** Serializable UID. */ - private static final long serialVersionUID = 20140225L; - - /** Simple constructor. - */ - public NoSubSpaceException() { - super(LocalizedFormats.NOT_SUPPORTED_IN_DIMENSION_N, 1); - } - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Interval.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Interval.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Interval.java deleted file mode 100644 index 18ebac7..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/Interval.java +++ /dev/null @@ -1,129 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.euclidean.oned; - -import org.apache.commons.math3.geometry.partitioning.Region.Location; - - -/** This class represents a 1D interval. - * @see IntervalsSet - * @since 3.0 - */ -public class Interval { - - /** The lower bound of the interval. */ - private final double lower; - - /** The upper bound of the interval. */ - private final double upper; - - /** Simple constructor. - * @param lower lower bound of the interval - * @param upper upper bound of the interval - */ - public Interval(final double lower, final double upper) { - this.lower = lower; - this.upper = upper; - } - - /** Get the lower bound of the interval. - * @return lower bound of the interval - * @since 3.1 - */ - public double getInf() { - return lower; - } - - /** Get the lower bound of the interval. - * @return lower bound of the interval - * @deprecated as of 3.1, replaced by {@link #getInf()} - */ - @Deprecated - public double getLower() { - return getInf(); - } - - /** Get the upper bound of the interval. - * @return upper bound of the interval - * @since 3.1 - */ - public double getSup() { - return upper; - } - - /** Get the upper bound of the interval. - * @return upper bound of the interval - * @deprecated as of 3.1, replaced by {@link #getSup()} - */ - @Deprecated - public double getUpper() { - return getSup(); - } - - /** Get the size of the interval. - * @return size of the interval - * @since 3.1 - */ - public double getSize() { - return upper - lower; - } - - /** Get the length of the interval. - * @return length of the interval - * @deprecated as of 3.1, replaced by {@link #getSize()} - */ - @Deprecated - public double getLength() { - return getSize(); - } - - /** Get the barycenter of the interval. - * @return barycenter of the interval - * @since 3.1 - */ - public double getBarycenter() { - return 0.5 * (lower + upper); - } - - /** Get the midpoint of the interval. - * @return midpoint of the interval - * @deprecated as of 3.1, replaced by {@link #getBarycenter()} - */ - @Deprecated - public double getMidPoint() { - return getBarycenter(); - } - - /** Check a point with respect to the interval. - * @param point point to check - * @param tolerance tolerance below which points are considered to - * belong to the boundary - * @return a code representing the point status: either {@link - * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY} - * @since 3.1 - */ - public Location checkPoint(final double point, final double tolerance) { - if (point < lower - tolerance || point > upper + tolerance) { - return Location.OUTSIDE; - } else if (point > lower + tolerance && point < upper - tolerance) { - return Location.INSIDE; - } else { - return Location.BOUNDARY; - } - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/IntervalsSet.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/IntervalsSet.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/IntervalsSet.java deleted file mode 100644 index 383ea9f..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/IntervalsSet.java +++ /dev/null @@ -1,686 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.euclidean.oned; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.Iterator; -import java.util.List; -import java.util.NoSuchElementException; - -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.partitioning.AbstractRegion; -import org.apache.commons.math3.geometry.partitioning.BSPTree; -import org.apache.commons.math3.geometry.partitioning.BoundaryProjection; -import org.apache.commons.math3.geometry.partitioning.SubHyperplane; -import org.apache.commons.math3.util.Precision; - -/** This class represents a 1D region: a set of intervals. - * @since 3.0 - */ -public class IntervalsSet extends AbstractRegion<Euclidean1D, Euclidean1D> implements Iterable<double[]> { - - /** Default value for tolerance. */ - private static final double DEFAULT_TOLERANCE = 1.0e-10; - - /** Build an intervals set representing the whole real line. - * @param tolerance tolerance below which points are considered identical. - * @since 3.3 - */ - public IntervalsSet(final double tolerance) { - super(tolerance); - } - - /** Build an intervals set corresponding to a single interval. - * @param lower lower bound of the interval, must be lesser or equal - * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY}) - * @param upper upper bound of the interval, must be greater or equal - * to {@code lower} (may be {@code Double.POSITIVE_INFINITY}) - * @param tolerance tolerance below which points are considered identical. - * @since 3.3 - */ - public IntervalsSet(final double lower, final double upper, final double tolerance) { - super(buildTree(lower, upper, tolerance), tolerance); - } - - /** Build an intervals set from an inside/outside BSP tree. - * <p>The leaf nodes of the BSP tree <em>must</em> have a - * {@code Boolean} attribute representing the inside status of - * the corresponding cell (true for inside cells, false for outside - * cells). In order to avoid building too many small objects, it is - * recommended to use the predefined constants - * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p> - * @param tree inside/outside BSP tree representing the intervals set - * @param tolerance tolerance below which points are considered identical. - * @since 3.3 - */ - public IntervalsSet(final BSPTree<Euclidean1D> tree, final double tolerance) { - super(tree, tolerance); - } - - /** Build an intervals set from a Boundary REPresentation (B-rep). - * <p>The boundary is provided as a collection of {@link - * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the - * interior part of the region on its minus side and the exterior on - * its plus side.</p> - * <p>The boundary elements can be in any order, and can form - * several non-connected sets (like for example polygons with holes - * or a set of disjoints polyhedrons considered as a whole). In - * fact, the elements do not even need to be connected together - * (their topological connections are not used here). However, if the - * boundary does not really separate an inside open from an outside - * open (open having here its topological meaning), then subsequent - * calls to the {@link - * org.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.geometry.Point) - * checkPoint} method will not be meaningful anymore.</p> - * <p>If the boundary is empty, the region will represent the whole - * space.</p> - * @param boundary collection of boundary elements - * @param tolerance tolerance below which points are considered identical. - * @since 3.3 - */ - public IntervalsSet(final Collection<SubHyperplane<Euclidean1D>> boundary, - final double tolerance) { - super(boundary, tolerance); - } - - /** Build an intervals set representing the whole real line. - * @deprecated as of 3.1 replaced with {@link #IntervalsSet(double)} - */ - @Deprecated - public IntervalsSet() { - this(DEFAULT_TOLERANCE); - } - - /** Build an intervals set corresponding to a single interval. - * @param lower lower bound of the interval, must be lesser or equal - * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY}) - * @param upper upper bound of the interval, must be greater or equal - * to {@code lower} (may be {@code Double.POSITIVE_INFINITY}) - * @deprecated as of 3.3 replaced with {@link #IntervalsSet(double, double, double)} - */ - @Deprecated - public IntervalsSet(final double lower, final double upper) { - this(lower, upper, DEFAULT_TOLERANCE); - } - - /** Build an intervals set from an inside/outside BSP tree. - * <p>The leaf nodes of the BSP tree <em>must</em> have a - * {@code Boolean} attribute representing the inside status of - * the corresponding cell (true for inside cells, false for outside - * cells). In order to avoid building too many small objects, it is - * recommended to use the predefined constants - * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p> - * @param tree inside/outside BSP tree representing the intervals set - * @deprecated as of 3.3, replaced with {@link #IntervalsSet(BSPTree, double)} - */ - @Deprecated - public IntervalsSet(final BSPTree<Euclidean1D> tree) { - this(tree, DEFAULT_TOLERANCE); - } - - /** Build an intervals set from a Boundary REPresentation (B-rep). - * <p>The boundary is provided as a collection of {@link - * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the - * interior part of the region on its minus side and the exterior on - * its plus side.</p> - * <p>The boundary elements can be in any order, and can form - * several non-connected sets (like for example polygons with holes - * or a set of disjoints polyhedrons considered as a whole). In - * fact, the elements do not even need to be connected together - * (their topological connections are not used here). However, if the - * boundary does not really separate an inside open from an outside - * open (open having here its topological meaning), then subsequent - * calls to the {@link - * org.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.geometry.Point) - * checkPoint} method will not be meaningful anymore.</p> - * <p>If the boundary is empty, the region will represent the whole - * space.</p> - * @param boundary collection of boundary elements - * @deprecated as of 3.3, replaced with {@link #IntervalsSet(Collection, double)} - */ - @Deprecated - public IntervalsSet(final Collection<SubHyperplane<Euclidean1D>> boundary) { - this(boundary, DEFAULT_TOLERANCE); - } - - /** Build an inside/outside tree representing a single interval. - * @param lower lower bound of the interval, must be lesser or equal - * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY}) - * @param upper upper bound of the interval, must be greater or equal - * to {@code lower} (may be {@code Double.POSITIVE_INFINITY}) - * @param tolerance tolerance below which points are considered identical. - * @return the built tree - */ - private static BSPTree<Euclidean1D> buildTree(final double lower, final double upper, - final double tolerance) { - if (Double.isInfinite(lower) && (lower < 0)) { - if (Double.isInfinite(upper) && (upper > 0)) { - // the tree must cover the whole real line - return new BSPTree<Euclidean1D>(Boolean.TRUE); - } - // the tree must be open on the negative infinity side - final SubHyperplane<Euclidean1D> upperCut = - new OrientedPoint(new Vector1D(upper), true, tolerance).wholeHyperplane(); - return new BSPTree<Euclidean1D>(upperCut, - new BSPTree<Euclidean1D>(Boolean.FALSE), - new BSPTree<Euclidean1D>(Boolean.TRUE), - null); - } - final SubHyperplane<Euclidean1D> lowerCut = - new OrientedPoint(new Vector1D(lower), false, tolerance).wholeHyperplane(); - if (Double.isInfinite(upper) && (upper > 0)) { - // the tree must be open on the positive infinity side - return new BSPTree<Euclidean1D>(lowerCut, - new BSPTree<Euclidean1D>(Boolean.FALSE), - new BSPTree<Euclidean1D>(Boolean.TRUE), - null); - } - - // the tree must be bounded on the two sides - final SubHyperplane<Euclidean1D> upperCut = - new OrientedPoint(new Vector1D(upper), true, tolerance).wholeHyperplane(); - return new BSPTree<Euclidean1D>(lowerCut, - new BSPTree<Euclidean1D>(Boolean.FALSE), - new BSPTree<Euclidean1D>(upperCut, - new BSPTree<Euclidean1D>(Boolean.FALSE), - new BSPTree<Euclidean1D>(Boolean.TRUE), - null), - null); - - } - - /** {@inheritDoc} */ - @Override - public IntervalsSet buildNew(final BSPTree<Euclidean1D> tree) { - return new IntervalsSet(tree, getTolerance()); - } - - /** {@inheritDoc} */ - @Override - protected void computeGeometricalProperties() { - if (getTree(false).getCut() == null) { - setBarycenter((Point<Euclidean1D>) Vector1D.NaN); - setSize(((Boolean) getTree(false).getAttribute()) ? Double.POSITIVE_INFINITY : 0); - } else { - double size = 0.0; - double sum = 0.0; - for (final Interval interval : asList()) { - size += interval.getSize(); - sum += interval.getSize() * interval.getBarycenter(); - } - setSize(size); - if (Double.isInfinite(size)) { - setBarycenter((Point<Euclidean1D>) Vector1D.NaN); - } else if (size >= Precision.SAFE_MIN) { - setBarycenter((Point<Euclidean1D>) new Vector1D(sum / size)); - } else { - setBarycenter((Point<Euclidean1D>) ((OrientedPoint) getTree(false).getCut().getHyperplane()).getLocation()); - } - } - } - - /** Get the lowest value belonging to the instance. - * @return lowest value belonging to the instance - * ({@code Double.NEGATIVE_INFINITY} if the instance doesn't - * have any low bound, {@code Double.POSITIVE_INFINITY} if the - * instance is empty) - */ - public double getInf() { - BSPTree<Euclidean1D> node = getTree(false); - double inf = Double.POSITIVE_INFINITY; - while (node.getCut() != null) { - final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane(); - inf = op.getLocation().getX(); - node = op.isDirect() ? node.getMinus() : node.getPlus(); - } - return ((Boolean) node.getAttribute()) ? Double.NEGATIVE_INFINITY : inf; - } - - /** Get the highest value belonging to the instance. - * @return highest value belonging to the instance - * ({@code Double.POSITIVE_INFINITY} if the instance doesn't - * have any high bound, {@code Double.NEGATIVE_INFINITY} if the - * instance is empty) - */ - public double getSup() { - BSPTree<Euclidean1D> node = getTree(false); - double sup = Double.NEGATIVE_INFINITY; - while (node.getCut() != null) { - final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane(); - sup = op.getLocation().getX(); - node = op.isDirect() ? node.getPlus() : node.getMinus(); - } - return ((Boolean) node.getAttribute()) ? Double.POSITIVE_INFINITY : sup; - } - - /** {@inheritDoc} - * @since 3.3 - */ - @Override - public BoundaryProjection<Euclidean1D> projectToBoundary(final Point<Euclidean1D> point) { - - // get position of test point - final double x = ((Vector1D) point).getX(); - - double previous = Double.NEGATIVE_INFINITY; - for (final double[] a : this) { - if (x < a[0]) { - // the test point lies between the previous and the current intervals - // offset will be positive - final double previousOffset = x - previous; - final double currentOffset = a[0] - x; - if (previousOffset < currentOffset) { - return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(previous), previousOffset); - } else { - return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(a[0]), currentOffset); - } - } else if (x <= a[1]) { - // the test point lies within the current interval - // offset will be negative - final double offset0 = a[0] - x; - final double offset1 = x - a[1]; - if (offset0 < offset1) { - return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(a[1]), offset1); - } else { - return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(a[0]), offset0); - } - } - previous = a[1]; - } - - // the test point if past the last sub-interval - return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(previous), x - previous); - - } - - /** Build a finite point. - * @param x abscissa of the point - * @return a new point for finite abscissa, null otherwise - */ - private Vector1D finiteOrNullPoint(final double x) { - return Double.isInfinite(x) ? null : new Vector1D(x); - } - - /** Build an ordered list of intervals representing the instance. - * <p>This method builds this intervals set as an ordered list of - * {@link Interval Interval} elements. If the intervals set has no - * lower limit, the first interval will have its low bound equal to - * {@code Double.NEGATIVE_INFINITY}. If the intervals set has - * no upper limit, the last interval will have its upper bound equal - * to {@code Double.POSITIVE_INFINITY}. An empty tree will - * build an empty list while a tree representing the whole real line - * will build a one element list with both bounds being - * infinite.</p> - * @return a new ordered list containing {@link Interval Interval} - * elements - */ - public List<Interval> asList() { - final List<Interval> list = new ArrayList<Interval>(); - for (final double[] a : this) { - list.add(new Interval(a[0], a[1])); - } - return list; - } - - /** Get the first leaf node of a tree. - * @param root tree root - * @return first leaf node - */ - private BSPTree<Euclidean1D> getFirstLeaf(final BSPTree<Euclidean1D> root) { - - if (root.getCut() == null) { - return root; - } - - // find the smallest internal node - BSPTree<Euclidean1D> smallest = null; - for (BSPTree<Euclidean1D> n = root; n != null; n = previousInternalNode(n)) { - smallest = n; - } - - return leafBefore(smallest); - - } - - /** Get the node corresponding to the first interval boundary. - * @return smallest internal node, - * or null if there are no internal nodes (i.e. the set is either empty or covers the real line) - */ - private BSPTree<Euclidean1D> getFirstIntervalBoundary() { - - // start search at the tree root - BSPTree<Euclidean1D> node = getTree(false); - if (node.getCut() == null) { - return null; - } - - // walk tree until we find the smallest internal node - node = getFirstLeaf(node).getParent(); - - // walk tree until we find an interval boundary - while (node != null && !(isIntervalStart(node) || isIntervalEnd(node))) { - node = nextInternalNode(node); - } - - return node; - - } - - /** Check if an internal node corresponds to the start abscissa of an interval. - * @param node internal node to check - * @return true if the node corresponds to the start abscissa of an interval - */ - private boolean isIntervalStart(final BSPTree<Euclidean1D> node) { - - if ((Boolean) leafBefore(node).getAttribute()) { - // it has an inside cell before it, it may end an interval but not start it - return false; - } - - if (!(Boolean) leafAfter(node).getAttribute()) { - // it has an outside cell after it, it is a dummy cut away from real intervals - return false; - } - - // the cell has an outside before and an inside after it - // it is the start of an interval - return true; - - } - - /** Check if an internal node corresponds to the end abscissa of an interval. - * @param node internal node to check - * @return true if the node corresponds to the end abscissa of an interval - */ - private boolean isIntervalEnd(final BSPTree<Euclidean1D> node) { - - if (!(Boolean) leafBefore(node).getAttribute()) { - // it has an outside cell before it, it may start an interval but not end it - return false; - } - - if ((Boolean) leafAfter(node).getAttribute()) { - // it has an inside cell after it, it is a dummy cut in the middle of an interval - return false; - } - - // the cell has an inside before and an outside after it - // it is the end of an interval - return true; - - } - - /** Get the next internal node. - * @param node current internal node - * @return next internal node in ascending order, or null - * if this is the last internal node - */ - private BSPTree<Euclidean1D> nextInternalNode(BSPTree<Euclidean1D> node) { - - if (childAfter(node).getCut() != null) { - // the next node is in the sub-tree - return leafAfter(node).getParent(); - } - - // there is nothing left deeper in the tree, we backtrack - while (isAfterParent(node)) { - node = node.getParent(); - } - return node.getParent(); - - } - - /** Get the previous internal node. - * @param node current internal node - * @return previous internal node in ascending order, or null - * if this is the first internal node - */ - private BSPTree<Euclidean1D> previousInternalNode(BSPTree<Euclidean1D> node) { - - if (childBefore(node).getCut() != null) { - // the next node is in the sub-tree - return leafBefore(node).getParent(); - } - - // there is nothing left deeper in the tree, we backtrack - while (isBeforeParent(node)) { - node = node.getParent(); - } - return node.getParent(); - - } - - /** Find the leaf node just before an internal node. - * @param node internal node at which the sub-tree starts - * @return leaf node just before the internal node - */ - private BSPTree<Euclidean1D> leafBefore(BSPTree<Euclidean1D> node) { - - node = childBefore(node); - while (node.getCut() != null) { - node = childAfter(node); - } - - return node; - - } - - /** Find the leaf node just after an internal node. - * @param node internal node at which the sub-tree starts - * @return leaf node just after the internal node - */ - private BSPTree<Euclidean1D> leafAfter(BSPTree<Euclidean1D> node) { - - node = childAfter(node); - while (node.getCut() != null) { - node = childBefore(node); - } - - return node; - - } - - /** Check if a node is the child before its parent in ascending order. - * @param node child node considered - * @return true is the node has a parent end is before it in ascending order - */ - private boolean isBeforeParent(final BSPTree<Euclidean1D> node) { - final BSPTree<Euclidean1D> parent = node.getParent(); - if (parent == null) { - return false; - } else { - return node == childBefore(parent); - } - } - - /** Check if a node is the child after its parent in ascending order. - * @param node child node considered - * @return true is the node has a parent end is after it in ascending order - */ - private boolean isAfterParent(final BSPTree<Euclidean1D> node) { - final BSPTree<Euclidean1D> parent = node.getParent(); - if (parent == null) { - return false; - } else { - return node == childAfter(parent); - } - } - - /** Find the child node just before an internal node. - * @param node internal node at which the sub-tree starts - * @return child node just before the internal node - */ - private BSPTree<Euclidean1D> childBefore(BSPTree<Euclidean1D> node) { - if (isDirect(node)) { - // smaller abscissas are on minus side, larger abscissas are on plus side - return node.getMinus(); - } else { - // smaller abscissas are on plus side, larger abscissas are on minus side - return node.getPlus(); - } - } - - /** Find the child node just after an internal node. - * @param node internal node at which the sub-tree starts - * @return child node just after the internal node - */ - private BSPTree<Euclidean1D> childAfter(BSPTree<Euclidean1D> node) { - if (isDirect(node)) { - // smaller abscissas are on minus side, larger abscissas are on plus side - return node.getPlus(); - } else { - // smaller abscissas are on plus side, larger abscissas are on minus side - return node.getMinus(); - } - } - - /** Check if an internal node has a direct oriented point. - * @param node internal node to check - * @return true if the oriented point is direct - */ - private boolean isDirect(final BSPTree<Euclidean1D> node) { - return ((OrientedPoint) node.getCut().getHyperplane()).isDirect(); - } - - /** Get the abscissa of an internal node. - * @param node internal node to check - * @return abscissa - */ - private double getAngle(final BSPTree<Euclidean1D> node) { - return ((OrientedPoint) node.getCut().getHyperplane()).getLocation().getX(); - } - - /** {@inheritDoc} - * <p> - * The iterator returns the limit values of sub-intervals in ascending order. - * </p> - * <p> - * The iterator does <em>not</em> support the optional {@code remove} operation. - * </p> - * @since 3.3 - */ - public Iterator<double[]> iterator() { - return new SubIntervalsIterator(); - } - - /** Local iterator for sub-intervals. */ - private class SubIntervalsIterator implements Iterator<double[]> { - - /** Current node. */ - private BSPTree<Euclidean1D> current; - - /** Sub-interval no yet returned. */ - private double[] pending; - - /** Simple constructor. - */ - public SubIntervalsIterator() { - - current = getFirstIntervalBoundary(); - - if (current == null) { - // all the leaf tree nodes share the same inside/outside status - if ((Boolean) getFirstLeaf(getTree(false)).getAttribute()) { - // it is an inside node, it represents the full real line - pending = new double[] { - Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY - }; - } else { - pending = null; - } - } else if (isIntervalEnd(current)) { - // the first boundary is an interval end, - // so the first interval starts at infinity - pending = new double[] { - Double.NEGATIVE_INFINITY, getAngle(current) - }; - } else { - selectPending(); - } - } - - /** Walk the tree to select the pending sub-interval. - */ - private void selectPending() { - - // look for the start of the interval - BSPTree<Euclidean1D> start = current; - while (start != null && !isIntervalStart(start)) { - start = nextInternalNode(start); - } - - if (start == null) { - // we have exhausted the iterator - current = null; - pending = null; - return; - } - - // look for the end of the interval - BSPTree<Euclidean1D> end = start; - while (end != null && !isIntervalEnd(end)) { - end = nextInternalNode(end); - } - - if (end != null) { - - // we have identified the interval - pending = new double[] { - getAngle(start), getAngle(end) - }; - - // prepare search for next interval - current = end; - - } else { - - // the final interval is open toward infinity - pending = new double[] { - getAngle(start), Double.POSITIVE_INFINITY - }; - - // there won't be any other intervals - current = null; - - } - - } - - /** {@inheritDoc} */ - public boolean hasNext() { - return pending != null; - } - - /** {@inheritDoc} */ - public double[] next() { - if (pending == null) { - throw new NoSuchElementException(); - } - final double[] next = pending; - selectPending(); - return next; - } - - /** {@inheritDoc} */ - public void remove() { - throw new UnsupportedOperationException(); - } - - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/OrientedPoint.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/OrientedPoint.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/OrientedPoint.java deleted file mode 100644 index 512bf5d..0000000 --- a/src/main/java/org/apache/commons/math3/geometry/euclidean/oned/OrientedPoint.java +++ /dev/null @@ -1,153 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.geometry.euclidean.oned; - -import org.apache.commons.math3.geometry.Point; -import org.apache.commons.math3.geometry.Vector; -import org.apache.commons.math3.geometry.partitioning.Hyperplane; - -/** This class represents a 1D oriented hyperplane. - * <p>An hyperplane in 1D is a simple point, its orientation being a - * boolean.</p> - * <p>Instances of this class are guaranteed to be immutable.</p> - * @since 3.0 - */ -public class OrientedPoint implements Hyperplane<Euclidean1D> { - - /** Default value for tolerance. */ - private static final double DEFAULT_TOLERANCE = 1.0e-10; - - /** Vector location. */ - private Vector1D location; - - /** Orientation. */ - private boolean direct; - - /** Tolerance below which points are considered to belong to the hyperplane. */ - private final double tolerance; - - /** Simple constructor. - * @param location location of the hyperplane - * @param direct if true, the plus side of the hyperplane is towards - * abscissas greater than {@code location} - * @param tolerance tolerance below which points are considered to belong to the hyperplane - * @since 3.3 - */ - public OrientedPoint(final Vector1D location, final boolean direct, final double tolerance) { - this.location = location; - this.direct = direct; - this.tolerance = tolerance; - } - - /** Simple constructor. - * @param location location of the hyperplane - * @param direct if true, the plus side of the hyperplane is towards - * abscissas greater than {@code location} - * @deprecated as of 3.3, replaced with {@link #OrientedPoint(Vector1D, boolean, double)} - */ - @Deprecated - public OrientedPoint(final Vector1D location, final boolean direct) { - this(location, direct, DEFAULT_TOLERANCE); - } - - /** Copy the instance. - * <p>Since instances are immutable, this method directly returns - * the instance.</p> - * @return the instance itself - */ - public OrientedPoint copySelf() { - return this; - } - - /** Get the offset (oriented distance) of a vector. - * @param vector vector to check - * @return offset of the vector - */ - public double getOffset(Vector<Euclidean1D> vector) { - return getOffset((Point<Euclidean1D>) vector); - } - - /** {@inheritDoc} */ - public double getOffset(final Point<Euclidean1D> point) { - final double delta = ((Vector1D) point).getX() - location.getX(); - return direct ? delta : -delta; - } - - /** Build a region covering the whole hyperplane. - * <p>Since this class represent zero dimension spaces which does - * not have lower dimension sub-spaces, this method returns a dummy - * implementation of a {@link - * org.apache.commons.math3.geometry.partitioning.SubHyperplane SubHyperplane}. - * This implementation is only used to allow the {@link - * org.apache.commons.math3.geometry.partitioning.SubHyperplane - * SubHyperplane} class implementation to work properly, it should - * <em>not</em> be used otherwise.</p> - * @return a dummy sub hyperplane - */ - public SubOrientedPoint wholeHyperplane() { - return new SubOrientedPoint(this, null); - } - - /** Build a region covering the whole space. - * @return a region containing the instance (really an {@link - * IntervalsSet IntervalsSet} instance) - */ - public IntervalsSet wholeSpace() { - return new IntervalsSet(tolerance); - } - - /** {@inheritDoc} */ - public boolean sameOrientationAs(final Hyperplane<Euclidean1D> other) { - return !(direct ^ ((OrientedPoint) other).direct); - } - - /** {@inheritDoc} - * @since 3.3 - */ - public Point<Euclidean1D> project(Point<Euclidean1D> point) { - return location; - } - - /** {@inheritDoc} - * @since 3.3 - */ - public double getTolerance() { - return tolerance; - } - - /** Get the hyperplane location on the real line. - * @return the hyperplane location - */ - public Vector1D getLocation() { - return location; - } - - /** Check if the hyperplane orientation is direct. - * @return true if the plus side of the hyperplane is towards - * abscissae greater than hyperplane location - */ - public boolean isDirect() { - return direct; - } - - /** Revert the instance. - */ - public void revertSelf() { - direct = !direct; - } - -}
