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(); - } - -}
