commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject [14/82] [partial] [math] Update for next development iteration: commons-math4
Date Mon, 16 Feb 2015 22:39:44 GMT
http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
deleted file mode 100644
index b234ad5..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
+++ /dev/null
@@ -1,116 +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.twod.hull;
-
-import java.util.Collection;
-
-import org.apache.commons.math3.exception.ConvergenceException;
-import org.apache.commons.math3.exception.MathIllegalArgumentException;
-import org.apache.commons.math3.exception.NullArgumentException;
-import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.math3.util.MathUtils;
-
-/**
- * Abstract base class for convex hull generators in the two-dimensional euclidean space.
- *
- * @since 3.3
- */
-abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
-
-    /** Default value for tolerance. */
-    private static final double DEFAULT_TOLERANCE = 1e-10;
-
-    /** Tolerance below which points are considered identical. */
-    private final double tolerance;
-
-    /**
-     * Indicates if collinear points on the hull shall be present in the output.
-     * If {@code false}, only the extreme points are added to the hull.
-     */
-    private final boolean includeCollinearPoints;
-
-    /**
-     * Simple constructor.
-     * <p>
-     * The default tolerance (1e-10) will be used to determine identical points.
-     *
-     * @param includeCollinearPoints indicates if collinear points on the hull shall be
-     * added as hull vertices
-     */
-    protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints) {
-        this(includeCollinearPoints, DEFAULT_TOLERANCE);
-    }
-
-    /**
-     * Simple constructor.
-     *
-     * @param includeCollinearPoints indicates if collinear points on the hull shall be
-     * added as hull vertices
-     * @param tolerance tolerance below which points are considered identical
-     */
-    protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints, final double tolerance) {
-        this.includeCollinearPoints = includeCollinearPoints;
-        this.tolerance = tolerance;
-    }
-
-    /**
-     * Get the tolerance below which points are considered identical.
-     * @return the tolerance below which points are considered identical
-     */
-    public double getTolerance() {
-        return tolerance;
-    }
-
-    /**
-     * Returns if collinear points on the hull will be added as hull vertices.
-     * @return {@code true} if collinear points are added as hull vertices, or {@code false}
-     * if only extreme points are present.
-     */
-    public boolean isIncludeCollinearPoints() {
-        return includeCollinearPoints;
-    }
-
-    /** {@inheritDoc} */
-    public ConvexHull2D generate(final Collection<Vector2D> points)
-            throws NullArgumentException, ConvergenceException {
-        // check for null points
-        MathUtils.checkNotNull(points);
-
-        Collection<Vector2D> hullVertices = null;
-        if (points.size() < 2) {
-            hullVertices = points;
-        } else {
-            hullVertices = findHullVertices(points);
-        }
-
-        try {
-            return new ConvexHull2D(hullVertices.toArray(new Vector2D[hullVertices.size()]),
-                                    tolerance);
-        } catch (MathIllegalArgumentException e) {
-            // the hull vertices may not form a convex hull if the tolerance value is to large
-            throw new ConvergenceException();
-        }
-    }
-
-    /**
-     * Find the convex hull vertices from the set of input points.
-     * @param points the set of input points
-     * @return the convex hull vertices in CCW winding
-     */
-    protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points);
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
deleted file mode 100644
index f5d1b84..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.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.twod.hull;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.List;
-
-import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
-
-/**
- * A simple heuristic to improve the performance of convex hull algorithms.
- * <p>
- * The heuristic is based on the idea of a convex quadrilateral, which is formed by
- * four points with the lowest and highest x / y coordinates. Any point that lies inside
- * this quadrilateral can not be part of the convex hull and can thus be safely discarded
- * before generating the convex hull itself.
- * <p>
- * The complexity of the operation is O(n), and may greatly improve the time it takes to
- * construct the convex hull afterwards, depending on the point distribution.
- *
- * @see <a href="http://en.wikipedia.org/wiki/Convex_hull_algorithms#Akl-Toussaint_heuristic">
- * Akl-Toussaint heuristic (Wikipedia)</a>
- * @since 3.3
- */
-public final class AklToussaintHeuristic {
-
-    /** Hide utility constructor. */
-    private AklToussaintHeuristic() {
-    }
-
-    /**
-     * Returns a point set that is reduced by all points for which it is safe to assume
-     * that they are not part of the convex hull.
-     *
-     * @param points the original point set
-     * @return a reduced point set, useful as input for convex hull algorithms
-     */
-    public static Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
-
-        // find the leftmost point
-        int size = 0;
-        Vector2D minX = null;
-        Vector2D maxX = null;
-        Vector2D minY = null;
-        Vector2D maxY = null;
-        for (Vector2D p : points) {
-            if (minX == null || p.getX() < minX.getX()) {
-                minX = p;
-            }
-            if (maxX == null || p.getX() > maxX.getX()) {
-                maxX = p;
-            }
-            if (minY == null || p.getY() < minY.getY()) {
-                minY = p;
-            }
-            if (maxY == null || p.getY() > maxY.getY()) {
-                maxY = p;
-            }
-            size++;
-        }
-
-        if (size < 4) {
-            return points;
-        }
-
-        final List<Vector2D> quadrilateral = buildQuadrilateral(minY, maxX, maxY, minX);
-        // if the quadrilateral is not well formed, e.g. only 2 points, do not attempt to reduce
-        if (quadrilateral.size() < 3) {
-            return points;
-        }
-
-        final List<Vector2D> reducedPoints = new ArrayList<Vector2D>(quadrilateral);
-        for (final Vector2D p : points) {
-            // check all points if they are within the quadrilateral
-            // in which case they can not be part of the convex hull
-            if (!insideQuadrilateral(p, quadrilateral)) {
-                reducedPoints.add(p);
-            }
-        }
-
-        return reducedPoints;
-    }
-
-    /**
-     * Build the convex quadrilateral with the found corner points (with min/max x/y coordinates).
-     *
-     * @param points the respective points with min/max x/y coordinate
-     * @return the quadrilateral
-     */
-    private static List<Vector2D> buildQuadrilateral(final Vector2D... points) {
-        List<Vector2D> quadrilateral = new ArrayList<Vector2D>();
-        for (Vector2D p : points) {
-            if (!quadrilateral.contains(p)) {
-                quadrilateral.add(p);
-            }
-        }
-        return quadrilateral;
-    }
-
-    /**
-     * Checks if the given point is located within the convex quadrilateral.
-     * @param point the point to check
-     * @param quadrilateralPoints the convex quadrilateral, represented by 4 points
-     * @return {@code true} if the point is inside the quadrilateral, {@code false} otherwise
-     */
-    private static boolean insideQuadrilateral(final Vector2D point,
-                                               final List<Vector2D> quadrilateralPoints) {
-
-        Vector2D p1 = quadrilateralPoints.get(0);
-        Vector2D p2 = quadrilateralPoints.get(1);
-
-        if (point.equals(p1) || point.equals(p2)) {
-            return true;
-        }
-
-        // get the location of the point relative to the first two vertices
-        final double last = point.crossProduct(p1, p2);
-        final int size = quadrilateralPoints.size();
-        // loop through the rest of the vertices
-        for (int i = 1; i < size; i++) {
-            p1 = p2;
-            p2 = quadrilateralPoints.get((i + 1) == size ? 0 : i + 1);
-
-            if (point.equals(p1) || point.equals(p2)) {
-                return true;
-            }
-
-            // do side of line test: multiply the last location with this location
-            // if they are the same sign then the operation will yield a positive result
-            // -x * -y = +xy, x * y = +xy, -x * y = -xy, x * -y = -xy
-            if (last * point.crossProduct(p1, p2) < 0) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java
deleted file mode 100644
index 5d9734b..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java
+++ /dev/null
@@ -1,172 +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.twod.hull;
-
-import java.io.Serializable;
-
-import org.apache.commons.math3.exception.InsufficientDataException;
-import org.apache.commons.math3.exception.MathIllegalArgumentException;
-import org.apache.commons.math3.exception.util.LocalizedFormats;
-import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
-import org.apache.commons.math3.geometry.euclidean.twod.Line;
-import org.apache.commons.math3.geometry.euclidean.twod.Segment;
-import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.math3.geometry.hull.ConvexHull;
-import org.apache.commons.math3.geometry.partitioning.Region;
-import org.apache.commons.math3.geometry.partitioning.RegionFactory;
-import org.apache.commons.math3.util.MathArrays;
-import org.apache.commons.math3.util.Precision;
-
-/**
- * This class represents a convex hull in an two-dimensional euclidean space.
- *
- * @since 3.3
- */
-public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializable {
-
-    /** Serializable UID. */
-    private static final long serialVersionUID = 20140129L;
-
-    /** Vertices of the hull. */
-    private final Vector2D[] vertices;
-
-    /** Tolerance threshold used during creation of the hull vertices. */
-    private final double tolerance;
-
-    /**
-     * Line segments of the hull.
-     * The array is not serialized and will be created from the vertices on first access.
-     */
-    private transient Segment[] lineSegments;
-
-    /**
-     * Simple constructor.
-     * @param vertices the vertices of the convex hull, must be ordered
-     * @param tolerance tolerance below which points are considered identical
-     * @throws MathIllegalArgumentException if the vertices do not form a convex hull
-     */
-    public ConvexHull2D(final Vector2D[] vertices, final double tolerance)
-        throws MathIllegalArgumentException {
-
-        // assign tolerance as it will be used by the isConvex method
-        this.tolerance = tolerance;
-
-        if (!isConvex(vertices)) {
-            throw new MathIllegalArgumentException(LocalizedFormats.NOT_CONVEX);
-        }
-
-        this.vertices = vertices.clone();
-    }
-
-    /**
-     * Checks whether the given hull vertices form a convex hull.
-     * @param hullVertices the hull vertices
-     * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
-     */
-    private boolean isConvex(final Vector2D[] hullVertices) {
-        if (hullVertices.length < 3) {
-            return true;
-        }
-
-        int sign = 0;
-        for (int i = 0; i < hullVertices.length; i++) {
-            final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1];
-            final Vector2D p2 = hullVertices[i];
-            final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1];
-
-            final Vector2D d1 = p2.subtract(p1);
-            final Vector2D d2 = p3.subtract(p2);
-
-            final double crossProduct = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
-            final int cmp = Precision.compareTo(crossProduct, 0.0, tolerance);
-            // in case of collinear points the cross product will be zero
-            if (cmp != 0.0) {
-                if (sign != 0.0 && cmp != sign) {
-                    return false;
-                }
-                sign = cmp;
-            }
-        }
-
-        return true;
-    }
-
-    /** {@inheritDoc} */
-    public Vector2D[] getVertices() {
-        return vertices.clone();
-    }
-
-    /**
-     * Get the line segments of the convex hull, ordered.
-     * @return the line segments of the convex hull
-     */
-    public Segment[] getLineSegments() {
-        return retrieveLineSegments().clone();
-    }
-
-    /**
-     * Retrieve the line segments from the cached array or create them if needed.
-     *
-     * @return the array of line segments
-     */
-    private Segment[] retrieveLineSegments() {
-        if (lineSegments == null) {
-            // construct the line segments - handle special cases of 1 or 2 points
-            final int size = vertices.length;
-            if (size <= 1) {
-                this.lineSegments = new Segment[0];
-            } else if (size == 2) {
-                this.lineSegments = new Segment[1];
-                final Vector2D p1 = vertices[0];
-                final Vector2D p2 = vertices[1];
-                this.lineSegments[0] = new Segment(p1, p2, new Line(p1, p2, tolerance));
-            } else {
-                this.lineSegments = new Segment[size];
-                Vector2D firstPoint = null;
-                Vector2D lastPoint = null;
-                int index = 0;
-                for (Vector2D point : vertices) {
-                    if (lastPoint == null) {
-                        firstPoint = point;
-                        lastPoint = point;
-                    } else {
-                        this.lineSegments[index++] =
-                                new Segment(lastPoint, point, new Line(lastPoint, point, tolerance));
-                        lastPoint = point;
-                    }
-                }
-                this.lineSegments[index] =
-                        new Segment(lastPoint, firstPoint, new Line(lastPoint, firstPoint, tolerance));
-            }
-        }
-        return lineSegments;
-    }
-
-    /** {@inheritDoc} */
-    public Region<Euclidean2D> createRegion() throws InsufficientDataException {
-        if (vertices.length < 3) {
-            throw new InsufficientDataException();
-        }
-        final RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>();
-        final Segment[] segments = retrieveLineSegments();
-        final Line[] lineArray = new Line[segments.length];
-        for (int i = 0; i < segments.length; i++) {
-            lineArray[i] = segments[i].getLine();
-        }
-        return factory.buildConvex(lineArray);
-    }
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java
deleted file mode 100644
index 3e13e1a..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java
+++ /dev/null
@@ -1,37 +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.twod.hull;
-
-import java.util.Collection;
-
-import org.apache.commons.math3.exception.ConvergenceException;
-import org.apache.commons.math3.exception.NullArgumentException;
-import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
-import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.math3.geometry.hull.ConvexHullGenerator;
-
-/**
- * Interface for convex hull generators in the two-dimensional euclidean space.
- *
- * @since 3.3
- */
-public interface ConvexHullGenerator2D extends ConvexHullGenerator<Euclidean2D, Vector2D> {
-
-    /** {@inheritDoc} */
-    ConvexHull2D generate(Collection<Vector2D> points) throws NullArgumentException, ConvergenceException;
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
deleted file mode 100644
index a811dda..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
+++ /dev/null
@@ -1,179 +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.twod.hull;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-
-import org.apache.commons.math3.geometry.euclidean.twod.Line;
-import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.math3.util.FastMath;
-import org.apache.commons.math3.util.Precision;
-
-/**
- * Implements Andrew's monotone chain method to generate the convex hull of a finite set of
- * points in the two-dimensional euclidean space.
- * <p>
- * The runtime complexity is O(n log n), with n being the number of input points. If the
- * point set is already sorted (by x-coordinate), the runtime complexity is O(n).
- * <p>
- * The implementation is not sensitive to collinear points on the hull. The parameter
- * {@code includeCollinearPoints} allows to control the behavior with regard to collinear points.
- * If {@code true}, all points on the boundary of the hull will be added to the hull vertices,
- * otherwise only the extreme points will be present. By default, collinear points are not added
- * as hull vertices.
- * <p>
- * The {@code tolerance} parameter (default: 1e-10) is used as epsilon criteria to determine
- * identical and collinear points.
- *
- * @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
- * Andrew's monotone chain algorithm (Wikibooks)</a>
- * @since 3.3
- */
-public class MonotoneChain extends AbstractConvexHullGenerator2D {
-
-    /**
-     * Create a new MonotoneChain instance.
-     */
-    public MonotoneChain() {
-        this(false);
-    }
-
-    /**
-     * Create a new MonotoneChain instance.
-     * @param includeCollinearPoints whether collinear points shall be added as hull vertices
-     */
-    public MonotoneChain(final boolean includeCollinearPoints) {
-        super(includeCollinearPoints);
-    }
-
-    /**
-     * Create a new MonotoneChain instance.
-     * @param includeCollinearPoints whether collinear points shall be added as hull vertices
-     * @param tolerance tolerance below which points are considered identical
-     */
-    public MonotoneChain(final boolean includeCollinearPoints, final double tolerance) {
-        super(includeCollinearPoints, tolerance);
-    }
-
-    @Override
-    public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
-
-        final List<Vector2D> pointsSortedByXAxis = new ArrayList<Vector2D>(points);
-
-        // sort the points in increasing order on the x-axis
-        Collections.sort(pointsSortedByXAxis, new Comparator<Vector2D>() {
-            public int compare(final Vector2D o1, final Vector2D o2) {
-                final double tolerance = getTolerance();
-                // need to take the tolerance value into account, otherwise collinear points
-                // will not be handled correctly when building the upper/lower hull
-                final int diff = Precision.compareTo(o1.getX(), o2.getX(), tolerance);
-                if (diff == 0) {
-                    return Precision.compareTo(o1.getY(), o2.getY(), tolerance);
-                } else {
-                    return diff;
-                }
-            }
-        });
-
-        // build lower hull
-        final List<Vector2D> lowerHull = new ArrayList<Vector2D>();
-        for (Vector2D p : pointsSortedByXAxis) {
-            updateHull(p, lowerHull);
-        }
-
-        // build upper hull
-        final List<Vector2D> upperHull = new ArrayList<Vector2D>();
-        for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) {
-            final Vector2D p = pointsSortedByXAxis.get(idx);
-            updateHull(p, upperHull);
-        }
-
-        // concatenate the lower and upper hulls
-        // the last point of each list is omitted as it is repeated at the beginning of the other list
-        final List<Vector2D> hullVertices = new ArrayList<Vector2D>(lowerHull.size() + upperHull.size() - 2);
-        for (int idx = 0; idx < lowerHull.size() - 1; idx++) {
-            hullVertices.add(lowerHull.get(idx));
-        }
-        for (int idx = 0; idx < upperHull.size() - 1; idx++) {
-            hullVertices.add(upperHull.get(idx));
-        }
-
-        // special case: if the lower and upper hull may contain only 1 point if all are identical
-        if (hullVertices.isEmpty() && ! lowerHull.isEmpty()) {
-            hullVertices.add(lowerHull.get(0));
-        }
-
-        return hullVertices;
-    }
-
-    /**
-     * Update the partial hull with the current point.
-     *
-     * @param point the current point
-     * @param hull the partial hull
-     */
-    private void updateHull(final Vector2D point, final List<Vector2D> hull) {
-        final double tolerance = getTolerance();
-
-        if (hull.size() == 1) {
-            // ensure that we do not add an identical point
-            final Vector2D p1 = hull.get(0);
-            if (p1.distance(point) < tolerance) {
-                return;
-            }
-        }
-
-        while (hull.size() >= 2) {
-            final int size = hull.size();
-            final Vector2D p1 = hull.get(size - 2);
-            final Vector2D p2 = hull.get(size - 1);
-
-            final double offset = new Line(p1, p2, tolerance).getOffset(point);
-            if (FastMath.abs(offset) < tolerance) {
-                // the point is collinear to the line (p1, p2)
-
-                final double distanceToCurrent = p1.distance(point);
-                if (distanceToCurrent < tolerance || p2.distance(point) < tolerance) {
-                    // the point is assumed to be identical to either p1 or p2
-                    return;
-                }
-
-                final double distanceToLast = p1.distance(p2);
-                if (isIncludeCollinearPoints()) {
-                    final int index = distanceToCurrent < distanceToLast ? size - 1 : size;
-                    hull.add(index, point);
-                } else {
-                    if (distanceToCurrent > distanceToLast) {
-                        hull.remove(size - 1);
-                        hull.add(point);
-                    }
-                }
-                return;
-            } else if (offset > 0) {
-                hull.remove(size - 1);
-            } else {
-                break;
-            }
-        }
-        hull.add(point);
-    }
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java
deleted file mode 100644
index d0469a4..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java
+++ /dev/null
@@ -1,25 +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 algorithms to generate the convex hull
- * for a set of points in an two-dimensional euclidean space.
- * </p>
- *
- */
-package org.apache.commons.math3.geometry.euclidean.twod.hull;

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/package-info.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/package-info.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/package-info.java
deleted file mode 100644
index feb43b1..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/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 basic 2D geometry components.
- * </p>
- *
- */
-package org.apache.commons.math3.geometry.euclidean.twod;

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHull.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHull.java b/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHull.java
deleted file mode 100644
index 8dfa3f3..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHull.java
+++ /dev/null
@@ -1,48 +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.hull;
-
-import java.io.Serializable;
-
-import org.apache.commons.math3.exception.InsufficientDataException;
-import org.apache.commons.math3.geometry.Point;
-import org.apache.commons.math3.geometry.Space;
-import org.apache.commons.math3.geometry.partitioning.Region;
-
-/**
- * This class represents a convex hull.
- *
- * @param <S> Space type.
- * @param <P> Point type.
- * @since 3.3
- */
-public interface ConvexHull<S extends Space, P extends Point<S>> extends Serializable {
-
-    /**
-     * Get the vertices of the convex hull.
-     * @return vertices of the convex hull
-     */
-    P[] getVertices();
-
-    /**
-     * Returns a new region that is enclosed by the convex hull.
-     * @return the region enclosed by the convex hull
-     * @throws InsufficientDataException if the number of vertices is not enough to
-     * build a region in the respective space
-     */
-    Region<S> createRegion() throws InsufficientDataException;
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHullGenerator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHullGenerator.java b/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHullGenerator.java
deleted file mode 100644
index 8f601d2..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/hull/ConvexHullGenerator.java
+++ /dev/null
@@ -1,49 +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.hull;
-
-import java.util.Collection;
-
-import org.apache.commons.math3.exception.ConvergenceException;
-import org.apache.commons.math3.exception.NullArgumentException;
-import org.apache.commons.math3.geometry.Point;
-import org.apache.commons.math3.geometry.Space;
-
-/**
- * Interface for convex hull generators.
- *
- * @param <S> Type of the {@link Space}
- * @param <P> Type of the {@link Point}
- *
- * @see <a href="http://en.wikipedia.org/wiki/Convex_hull">Convex Hull (Wikipedia)</a>
- * @see <a href="http://mathworld.wolfram.com/ConvexHull.html">Convex Hull (MathWorld)</a>
- *
- * @since 3.3
- */
-public interface ConvexHullGenerator<S extends Space, P extends Point<S>> {
-
-    /**
-     * Builds the convex hull from the set of input points.
-     *
-     * @param points the set of input points
-     * @return the convex hull
-     * @throws NullArgumentException if the input collection is {@code null}
-     * @throws ConvergenceException if generator fails to generate a convex hull for
-     * the given set of input points
-     */
-    ConvexHull<S, P> generate(Collection<P> points) throws NullArgumentException, ConvergenceException;
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/hull/package-info.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/hull/package-info.java b/src/main/java/org/apache/commons/math3/geometry/hull/package-info.java
deleted file mode 100644
index 2246682..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/hull/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 convex hull problem.
- * </p>
- *
- */
-package org.apache.commons.math3.geometry.hull;

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/package-info.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/package-info.java b/src/main/java/org/apache/commons/math3/geometry/package-info.java
deleted file mode 100644
index 31929e2..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/package-info.java
+++ /dev/null
@@ -1,25 +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 is the top level package for geometry. It provides only a few interfaces
- * related to vectorial/affine spaces that are implemented in sub-packages.
- * </p>
- *
- */
-package org.apache.commons.math3.geometry;

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java
deleted file mode 100644
index 6928331..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractRegion.java
+++ /dev/null
@@ -1,533 +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.partitioning;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.TreeSet;
-
-import org.apache.commons.math3.geometry.Point;
-import org.apache.commons.math3.geometry.Space;
-import org.apache.commons.math3.geometry.Vector;
-
-/** Abstract class for all regions, independently of geometry type or dimension.
-
- * @param <S> Type of the space.
- * @param <T> Type of the sub-space.
-
- * @since 3.0
- */
-public abstract class AbstractRegion<S extends Space, T extends Space> implements Region<S> {
-
-    /** Inside/Outside BSP tree. */
-    private BSPTree<S> tree;
-
-    /** Tolerance below which points are considered to belong to hyperplanes. */
-    private final double tolerance;
-
-    /** Size of the instance. */
-    private double size;
-
-    /** Barycenter. */
-    private Point<S> barycenter;
-
-    /** Build a region representing the whole space.
-     * @param tolerance tolerance below which points are considered identical.
-     */
-    protected AbstractRegion(final double tolerance) {
-        this.tree      = new BSPTree<S>(Boolean.TRUE);
-        this.tolerance = tolerance;
-    }
-
-    /** Build a region 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}. The
-     * tree also <em>must</em> have either null internal nodes or
-     * internal nodes representing the boundary as specified in the
-     * {@link #getTree getTree} method).</p>
-     * @param tree inside/outside BSP tree representing the region
-     * @param tolerance tolerance below which points are considered identical.
-     */
-    protected AbstractRegion(final BSPTree<S> tree, final double tolerance) {
-        this.tree      = tree;
-        this.tolerance = tolerance;
-    }
-
-    /** Build a Region 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 #checkPoint(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, as a
-     * collection of {@link SubHyperplane SubHyperplane} objects
-     * @param tolerance tolerance below which points are considered identical.
-     */
-    protected AbstractRegion(final Collection<SubHyperplane<S>> boundary, final double tolerance) {
-
-        this.tolerance = tolerance;
-
-        if (boundary.size() == 0) {
-
-            // the tree represents the whole space
-            tree = new BSPTree<S>(Boolean.TRUE);
-
-        } else {
-
-            // sort the boundary elements in decreasing size order
-            // (we don't want equal size elements to be removed, so
-            // we use a trick to fool the TreeSet)
-            final TreeSet<SubHyperplane<S>> ordered = new TreeSet<SubHyperplane<S>>(new Comparator<SubHyperplane<S>>() {
-                public int compare(final SubHyperplane<S> o1, final SubHyperplane<S> o2) {
-                    final double size1 = o1.getSize();
-                    final double size2 = o2.getSize();
-                    return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
-                }
-            });
-            ordered.addAll(boundary);
-
-            // build the tree top-down
-            tree = new BSPTree<S>();
-            insertCuts(tree, ordered);
-
-            // set up the inside/outside flags
-            tree.visit(new BSPTreeVisitor<S>() {
-
-                /** {@inheritDoc} */
-                public Order visitOrder(final BSPTree<S> node) {
-                    return Order.PLUS_SUB_MINUS;
-                }
-
-                /** {@inheritDoc} */
-                public void visitInternalNode(final BSPTree<S> node) {
-                }
-
-                /** {@inheritDoc} */
-                public void visitLeafNode(final BSPTree<S> node) {
-                    if (node.getParent() == null || node == node.getParent().getMinus()) {
-                        node.setAttribute(Boolean.TRUE);
-                    } else {
-                        node.setAttribute(Boolean.FALSE);
-                    }
-                }
-            });
-
-        }
-
-    }
-
-    /** Build a convex region from an array of bounding hyperplanes.
-     * @param hyperplanes array of bounding hyperplanes (if null, an
-     * empty region will be built)
-     * @param tolerance tolerance below which points are considered identical.
-     */
-    public AbstractRegion(final Hyperplane<S>[] hyperplanes, final double tolerance) {
-        this.tolerance = tolerance;
-        if ((hyperplanes == null) || (hyperplanes.length == 0)) {
-            tree = new BSPTree<S>(Boolean.FALSE);
-        } else {
-
-            // use the first hyperplane to build the right class
-            tree = hyperplanes[0].wholeSpace().getTree(false);
-
-            // chop off parts of the space
-            BSPTree<S> node = tree;
-            node.setAttribute(Boolean.TRUE);
-            for (final Hyperplane<S> hyperplane : hyperplanes) {
-                if (node.insertCut(hyperplane)) {
-                    node.setAttribute(null);
-                    node.getPlus().setAttribute(Boolean.FALSE);
-                    node = node.getMinus();
-                    node.setAttribute(Boolean.TRUE);
-                }
-            }
-
-        }
-
-    }
-
-    /** {@inheritDoc} */
-    public abstract AbstractRegion<S, T> buildNew(BSPTree<S> newTree);
-
-    /** Get the tolerance below which points are considered to belong to hyperplanes.
-     * @return tolerance below which points are considered to belong to hyperplanes
-     */
-    public double getTolerance() {
-        return tolerance;
-    }
-
-    /** Recursively build a tree by inserting cut sub-hyperplanes.
-     * @param node current tree node (it is a leaf node at the beginning
-     * of the call)
-     * @param boundary collection of edges belonging to the cell defined
-     * by the node
-     */
-    private void insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary) {
-
-        final Iterator<SubHyperplane<S>> iterator = boundary.iterator();
-
-        // build the current level
-        Hyperplane<S> inserted = null;
-        while ((inserted == null) && iterator.hasNext()) {
-            inserted = iterator.next().getHyperplane();
-            if (!node.insertCut(inserted.copySelf())) {
-                inserted = null;
-            }
-        }
-
-        if (!iterator.hasNext()) {
-            return;
-        }
-
-        // distribute the remaining edges in the two sub-trees
-        final ArrayList<SubHyperplane<S>> plusList  = new ArrayList<SubHyperplane<S>>();
-        final ArrayList<SubHyperplane<S>> minusList = new ArrayList<SubHyperplane<S>>();
-        while (iterator.hasNext()) {
-            final SubHyperplane<S> other = iterator.next();
-            switch (other.side(inserted)) {
-            case PLUS:
-                plusList.add(other);
-                break;
-            case MINUS:
-                minusList.add(other);
-                break;
-            case BOTH:
-                final SubHyperplane.SplitSubHyperplane<S> split = other.split(inserted);
-                plusList.add(split.getPlus());
-                minusList.add(split.getMinus());
-                break;
-            default:
-                // ignore the sub-hyperplanes belonging to the cut hyperplane
-            }
-        }
-
-        // recurse through lower levels
-        insertCuts(node.getPlus(),  plusList);
-        insertCuts(node.getMinus(), minusList);
-
-    }
-
-    /** {@inheritDoc} */
-    public AbstractRegion<S, T> copySelf() {
-        return buildNew(tree.copySelf());
-    }
-
-    /** {@inheritDoc} */
-    public boolean isEmpty() {
-        return isEmpty(tree);
-    }
-
-    /** {@inheritDoc} */
-    public boolean isEmpty(final BSPTree<S> node) {
-
-        // we use a recursive function rather than the BSPTreeVisitor
-        // interface because we can stop visiting the tree as soon as we
-        // have found an inside cell
-
-        if (node.getCut() == null) {
-            // if we find an inside node, the region is not empty
-            return !((Boolean) node.getAttribute());
-        }
-
-        // check both sides of the sub-tree
-        return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
-
-    }
-
-    /** {@inheritDoc} */
-    public boolean isFull() {
-        return isFull(tree);
-    }
-
-    /** {@inheritDoc} */
-    public boolean isFull(final BSPTree<S> node) {
-
-        // we use a recursive function rather than the BSPTreeVisitor
-        // interface because we can stop visiting the tree as soon as we
-        // have found an outside cell
-
-        if (node.getCut() == null) {
-            // if we find an outside node, the region does not cover full space
-            return (Boolean) node.getAttribute();
-        }
-
-        // check both sides of the sub-tree
-        return isFull(node.getMinus()) && isFull(node.getPlus());
-
-    }
-
-    /** {@inheritDoc} */
-    public boolean contains(final Region<S> region) {
-        return new RegionFactory<S>().difference(region, this).isEmpty();
-    }
-
-    /** {@inheritDoc}
-     * @since 3.3
-     */
-    public BoundaryProjection<S> projectToBoundary(final Point<S> point) {
-        final BoundaryProjector<S, T> projector = new BoundaryProjector<S, T>(point);
-        getTree(true).visit(projector);
-        return projector.getProjection();
-    }
-
-    /** Check a point with respect to the region.
-     * @param point point to check
-     * @return a code representing the point status: either {@link
-     * Region.Location#INSIDE}, {@link Region.Location#OUTSIDE} or
-     * {@link Region.Location#BOUNDARY}
-     */
-    public Location checkPoint(final Vector<S> point) {
-        return checkPoint((Point<S>) point);
-    }
-
-    /** {@inheritDoc} */
-    public Location checkPoint(final Point<S> point) {
-        return checkPoint(tree, point);
-    }
-
-    /** Check a point with respect to the region starting at a given node.
-     * @param node root node of the region
-     * @param point point to check
-     * @return a code representing the point status: either {@link
-     * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE
-     * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY}
-     */
-    protected Location checkPoint(final BSPTree<S> node, final Vector<S> point) {
-        return checkPoint(node, (Point<S>) point);
-    }
-
-    /** Check a point with respect to the region starting at a given node.
-     * @param node root node of the region
-     * @param point point to check
-     * @return a code representing the point status: either {@link
-     * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE
-     * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY}
-     */
-    protected Location checkPoint(final BSPTree<S> node, final Point<S> point) {
-        final BSPTree<S> cell = node.getCell(point, tolerance);
-        if (cell.getCut() == null) {
-            // the point is in the interior of a cell, just check the attribute
-            return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
-        }
-
-        // the point is on a cut-sub-hyperplane, is it on a boundary ?
-        final Location minusCode = checkPoint(cell.getMinus(), point);
-        final Location plusCode  = checkPoint(cell.getPlus(),  point);
-        return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;
-
-    }
-
-    /** {@inheritDoc} */
-    public BSPTree<S> getTree(final boolean includeBoundaryAttributes) {
-        if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
-            // compute the boundary attributes
-            tree.visit(new BoundaryBuilder<S>());
-        }
-        return tree;
-    }
-
-    /** {@inheritDoc} */
-    public double getBoundarySize() {
-        final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>();
-        getTree(true).visit(visitor);
-        return visitor.getSize();
-    }
-
-    /** {@inheritDoc} */
-    public double getSize() {
-        if (barycenter == null) {
-            computeGeometricalProperties();
-        }
-        return size;
-    }
-
-    /** Set the size of the instance.
-     * @param size size of the instance
-     */
-    protected void setSize(final double size) {
-        this.size = size;
-    }
-
-    /** {@inheritDoc} */
-    public Point<S> getBarycenter() {
-        if (barycenter == null) {
-            computeGeometricalProperties();
-        }
-        return barycenter;
-    }
-
-    /** Set the barycenter of the instance.
-     * @param barycenter barycenter of the instance
-     */
-    protected void setBarycenter(final Vector<S> barycenter) {
-        setBarycenter((Point<S>) barycenter);
-    }
-
-    /** Set the barycenter of the instance.
-     * @param barycenter barycenter of the instance
-     */
-    protected void setBarycenter(final Point<S> barycenter) {
-        this.barycenter = barycenter;
-    }
-
-    /** Compute some geometrical properties.
-     * <p>The properties to compute are the barycenter and the size.</p>
-     */
-    protected abstract void computeGeometricalProperties();
-
-    /** {@inheritDoc} */
-    public Side side(final Hyperplane<S> hyperplane) {
-        final InsideFinder<S> finder = new InsideFinder<S>(this);
-        finder.recurseSides(tree, hyperplane.wholeHyperplane());
-        return finder.plusFound() ?
-              (finder.minusFound() ? Side.BOTH  : Side.PLUS) :
-              (finder.minusFound() ? Side.MINUS : Side.HYPER);
-    }
-
-    /** {@inheritDoc} */
-    public SubHyperplane<S> intersection(final SubHyperplane<S> sub) {
-        return recurseIntersection(tree, sub);
-    }
-
-    /** Recursively compute the parts of a sub-hyperplane that are
-     * contained in the region.
-     * @param node current BSP tree node
-     * @param sub sub-hyperplane traversing the region
-     * @return filtered sub-hyperplane
-     */
-    private SubHyperplane<S> recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub) {
-
-        if (node.getCut() == null) {
-            return (Boolean) node.getAttribute() ? sub.copySelf() : null;
-        }
-
-        final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
-        switch (sub.side(hyperplane)) {
-        case PLUS :
-            return recurseIntersection(node.getPlus(), sub);
-        case MINUS :
-            return recurseIntersection(node.getMinus(), sub);
-        case BOTH :
-            final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
-            final SubHyperplane<S> plus  = recurseIntersection(node.getPlus(),  split.getPlus());
-            final SubHyperplane<S> minus = recurseIntersection(node.getMinus(), split.getMinus());
-            if (plus == null) {
-                return minus;
-            } else if (minus == null) {
-                return plus;
-            } else {
-                return plus.reunite(minus);
-            }
-        default :
-            return recurseIntersection(node.getPlus(),
-                                       recurseIntersection(node.getMinus(), sub));
-        }
-
-    }
-
-    /** Transform a region.
-     * <p>Applying a transform to a region consist in applying the
-     * transform to all the hyperplanes of the underlying BSP tree and
-     * of the boundary (and also to the sub-hyperplanes embedded in
-     * these hyperplanes) and to the barycenter. The instance is not
-     * modified, a new instance is built.</p>
-     * @param transform transform to apply
-     * @return a new region, resulting from the application of the
-     * transform to the instance
-     */
-    public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) {
-
-        // transform the tree, except for boundary attribute splitters
-        final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<BSPTree<S>, BSPTree<S>>();
-        final BSPTree<S> transformedTree = recurseTransform(getTree(false), transform, map);
-
-        // set up the boundary attributes splitters
-        for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) {
-            if (entry.getKey().getCut() != null) {
-                @SuppressWarnings("unchecked")
-                BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute();
-                if (original != null) {
-                    @SuppressWarnings("unchecked")
-                    BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute();
-                    for (final BSPTree<S> splitter : original.getSplitters()) {
-                        transformed.getSplitters().add(map.get(splitter));
-                    }
-                }
-            }
-        }
-
-        return buildNew(transformedTree);
-
-    }
-
-    /** Recursively transform an inside/outside BSP-tree.
-     * @param node current BSP tree node
-     * @param transform transform to apply
-     * @param map transformed nodes map
-     * @return a new tree
-     */
-    @SuppressWarnings("unchecked")
-    private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform,
-                                        final Map<BSPTree<S>, BSPTree<S>> map) {
-
-        final BSPTree<S> transformedNode;
-        if (node.getCut() == null) {
-            transformedNode = new BSPTree<S>(node.getAttribute());
-        } else {
-
-            final SubHyperplane<S>  sub = node.getCut();
-            final SubHyperplane<S> tSub = ((AbstractSubHyperplane<S, T>) sub).applyTransform(transform);
-            BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute();
-            if (attribute != null) {
-                final SubHyperplane<S> tPO = (attribute.getPlusOutside() == null) ?
-                    null : ((AbstractSubHyperplane<S, T>) attribute.getPlusOutside()).applyTransform(transform);
-                final SubHyperplane<S> tPI = (attribute.getPlusInside()  == null) ?
-                    null  : ((AbstractSubHyperplane<S, T>) attribute.getPlusInside()).applyTransform(transform);
-                // we start with an empty list of splitters, it will be filled in out of recursion
-                attribute = new BoundaryAttribute<S>(tPO, tPI, new NodesSet<S>());
-            }
-
-            transformedNode = new BSPTree<S>(tSub,
-                                             recurseTransform(node.getPlus(),  transform, map),
-                                             recurseTransform(node.getMinus(), transform, map),
-                                             attribute);
-        }
-
-        map.put(node, transformedNode);
-        return transformedNode;
-
-    }
-
-}

http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java
deleted file mode 100644
index 3fd6b54..0000000
--- a/src/main/java/org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.java
+++ /dev/null
@@ -1,188 +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.partitioning;
-
-import java.util.HashMap;
-import java.util.Map;
-
-import org.apache.commons.math3.geometry.Space;
-
-/** This class implements the dimension-independent parts of {@link SubHyperplane}.
-
- * <p>sub-hyperplanes are obtained when parts of an {@link
- * Hyperplane hyperplane} are chopped off by other hyperplanes that
- * intersect it. The remaining part is a convex region. Such objects
- * appear in {@link BSPTree BSP trees} as the intersection of a cut
- * hyperplane with the convex region which it splits, the chopping
- * hyperplanes are the cut hyperplanes closer to the tree root.</p>
-
- * @param <S> Type of the embedding space.
- * @param <T> Type of the embedded sub-space.
-
- * @since 3.0
- */
-public abstract class AbstractSubHyperplane<S extends Space, T extends Space>
-    implements SubHyperplane<S> {
-
-    /** Underlying hyperplane. */
-    private final Hyperplane<S> hyperplane;
-
-    /** Remaining region of the hyperplane. */
-    private final Region<T> remainingRegion;
-
-    /** Build a sub-hyperplane from an hyperplane and a region.
-     * @param hyperplane underlying hyperplane
-     * @param remainingRegion remaining region of the hyperplane
-     */
-    protected AbstractSubHyperplane(final Hyperplane<S> hyperplane,
-                                    final Region<T> remainingRegion) {
-        this.hyperplane      = hyperplane;
-        this.remainingRegion = remainingRegion;
-    }
-
-    /** Build a sub-hyperplane from an hyperplane and a region.
-     * @param hyper underlying hyperplane
-     * @param remaining remaining region of the hyperplane
-     * @return a new sub-hyperplane
-     */
-    protected abstract AbstractSubHyperplane<S, T> buildNew(final Hyperplane<S> hyper,
-                                                            final Region<T> remaining);
-
-    /** {@inheritDoc} */
-    public AbstractSubHyperplane<S, T> copySelf() {
-        return buildNew(hyperplane.copySelf(), remainingRegion);
-    }
-
-    /** Get the underlying hyperplane.
-     * @return underlying hyperplane
-     */
-    public Hyperplane<S> getHyperplane() {
-        return hyperplane;
-    }
-
-    /** Get the remaining region of the hyperplane.
-     * <p>The returned region is expressed in the canonical hyperplane
-     * frame and has the hyperplane dimension. For example a chopped
-     * hyperplane in the 3D euclidean is a 2D plane and the
-     * corresponding region is a convex 2D polygon.</p>
-     * @return remaining region of the hyperplane
-     */
-    public Region<T> getRemainingRegion() {
-        return remainingRegion;
-    }
-
-    /** {@inheritDoc} */
-    public double getSize() {
-        return remainingRegion.getSize();
-    }
-
-    /** {@inheritDoc} */
-    public AbstractSubHyperplane<S, T> reunite(final SubHyperplane<S> other) {
-        @SuppressWarnings("unchecked")
-        AbstractSubHyperplane<S, T> o = (AbstractSubHyperplane<S, T>) other;
-        return buildNew(hyperplane,
-                        new RegionFactory<T>().union(remainingRegion, o.remainingRegion));
-    }
-
-    /** Apply a transform to the instance.
-     * <p>The instance must be a (D-1)-dimension sub-hyperplane with
-     * respect to the transform <em>not</em> a (D-2)-dimension
-     * sub-hyperplane the transform knows how to transform by
-     * itself. The transform will consist in transforming first the
-     * hyperplane and then the all region using the various methods
-     * provided by the transform.</p>
-     * @param transform D-dimension transform to apply
-     * @return the transformed instance
-     */
-    public AbstractSubHyperplane<S, T> applyTransform(final Transform<S, T> transform) {
-        final Hyperplane<S> tHyperplane = transform.apply(hyperplane);
-
-        // transform the tree, except for boundary attribute splitters
-        final Map<BSPTree<T>, BSPTree<T>> map = new HashMap<BSPTree<T>, BSPTree<T>>();
-        final BSPTree<T> tTree =
-            recurseTransform(remainingRegion.getTree(false), tHyperplane, transform, map);
-
-        // set up the boundary attributes splitters
-        for (final Map.Entry<BSPTree<T>, BSPTree<T>> entry : map.entrySet()) {
-            if (entry.getKey().getCut() != null) {
-                @SuppressWarnings("unchecked")
-                BoundaryAttribute<T> original = (BoundaryAttribute<T>) entry.getKey().getAttribute();
-                if (original != null) {
-                    @SuppressWarnings("unchecked")
-                    BoundaryAttribute<T> transformed = (BoundaryAttribute<T>) entry.getValue().getAttribute();
-                    for (final BSPTree<T> splitter : original.getSplitters()) {
-                        transformed.getSplitters().add(map.get(splitter));
-                    }
-                }
-            }
-        }
-
-        return buildNew(tHyperplane, remainingRegion.buildNew(tTree));
-
-    }
-
-    /** Recursively transform a BSP-tree from a sub-hyperplane.
-     * @param node current BSP tree node
-     * @param transformed image of the instance hyperplane by the transform
-     * @param transform transform to apply
-     * @param map transformed nodes map
-     * @return a new tree
-     */
-    private BSPTree<T> recurseTransform(final BSPTree<T> node,
-                                        final Hyperplane<S> transformed,
-                                        final Transform<S, T> transform,
-                                        final Map<BSPTree<T>, BSPTree<T>> map) {
-
-        final BSPTree<T> transformedNode;
-        if (node.getCut() == null) {
-            transformedNode = new BSPTree<T>(node.getAttribute());
-        } else {
-
-            @SuppressWarnings("unchecked")
-            BoundaryAttribute<T> attribute = (BoundaryAttribute<T>) node.getAttribute();
-            if (attribute != null) {
-                final SubHyperplane<T> tPO = (attribute.getPlusOutside() == null) ?
-                    null : transform.apply(attribute.getPlusOutside(), hyperplane, transformed);
-                final SubHyperplane<T> tPI = (attribute.getPlusInside() == null) ?
-                    null : transform.apply(attribute.getPlusInside(), hyperplane, transformed);
-                // we start with an empty list of splitters, it will be filled in out of recursion
-                attribute = new BoundaryAttribute<T>(tPO, tPI, new NodesSet<T>());
-            }
-
-            transformedNode = new BSPTree<T>(transform.apply(node.getCut(), hyperplane, transformed),
-                    recurseTransform(node.getPlus(),  transformed, transform, map),
-                    recurseTransform(node.getMinus(), transformed, transform, map),
-                    attribute);
-        }
-
-        map.put(node, transformedNode);
-        return transformedNode;
-
-    }
-
-    /** {@inheritDoc} */
-    public abstract Side side(Hyperplane<S> hyper);
-
-    /** {@inheritDoc} */
-    public abstract SplitSubHyperplane<S> split(Hyperplane<S> hyper);
-
-    /** {@inheritDoc} */
-    public boolean isEmpty() {
-        return remainingRegion.isEmpty();
-    }
-
-}


Mime
View raw message