commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r1066664 [3/6] - in /commons/sandbox/bsp: branches/ tags/ trunk/ trunk/src/ trunk/src/main/ trunk/src/main/java/ trunk/src/main/java/org/ trunk/src/main/java/org/apache/ trunk/src/main/java/org/apache/commons/ trunk/src/main/java/org/apache...
Date Wed, 02 Feb 2011 22:21:07 GMT
Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Line.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Line.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Line.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Line.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,512 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import java.awt.geom.AffineTransform;
+
+import org.apache.commons.bsp.BSPException;
+import org.apache.commons.bsp.BSPMessages;
+import org.apache.commons.bsp.euclidean.oneD.IntervalsSet;
+import org.apache.commons.bsp.euclidean.oneD.OrientedPoint;
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.partitioning.BSPTree;
+import org.apache.commons.bsp.partitioning.Hyperplane;
+import org.apache.commons.bsp.partitioning.Point;
+import org.apache.commons.bsp.partitioning.Region;
+import org.apache.commons.bsp.partitioning.SubHyperplane;
+import org.apache.commons.bsp.partitioning.SubSpace;
+import org.apache.commons.bsp.partitioning.Transform;
+import org.apache.commons.math.util.FastMath;
+import org.apache.commons.math.util.MathUtils;
+
+/** This class represents an oriented line in the 2D plane.
+
+ * <p>An oriented line can be defined either by prolongating a line
+ * segment between two points past these points, or by one point and
+ * an angular direction (in trigonometric orientation).</p>
+
+ * <p>Since it is oriented the two half planes at its two sides are
+ * unambiguously identified as a left half plane and a right half
+ * plane. This can be used to identify the interior and the exterior
+ * in a simple way by local properties only when part of a line is
+ * used to define part of a polygon boundary.</p>
+
+ * <p>A line can also be used to completely define a reference frame
+ * in the plane. It is sufficient to select one specific point in the
+ * line (the orthogonal projection of the original reference frame on
+ * the line) and to use the unit vector in the line direction and the
+ * orthogonal vector oriented from left half plane to right half
+ * plane. We define two coordinates by the process, the
+ * <em>abscissa</em> along the line, and the <em>offset</em> across
+ * the line. All points of the plane are uniquely identified by these
+ * two coordinates. The line is the set of points at zero offset, the
+ * left half plane is the set of points with negative offsets and the
+ * right half plane is the set of points with positive offsets.</p>
+
+ * @version $Revision$ $Date$
+ */
+public class Line implements Hyperplane {
+
+    /** Angle with respect to the abscissa axis. */
+    private double angle;
+
+    /** Cosine of the line angle. */
+    private double cos;
+
+    /** Sine of the line angle. */
+    private double sin;
+
+    /** Offset of the frame origin. */
+    private double originOffset;
+
+    /** Build a line from two points.
+     * <p>The line is oriented from p1 to p2</p>
+     * @param p1 first point
+     * @param p2 second point
+     */
+    public Line(final Point2D p1, final Point2D p2) {
+        reset(p1, p2);
+    }
+
+    /** Build a line from a point and an angle.
+     * @param p point belonging to the line
+     * @param angle angle of the line with respect to abscissa axis
+     */
+    public Line(final Point2D p, final double angle) {
+        reset(p, angle);
+    }
+
+    /** Build a line from its internal characteristics.
+     * @param angle angle of the line with respect to abscissa axis
+     * @param cos cosine of the angle
+     * @param sin sine of the angle
+     * @param originOffset offset of the origin
+     */
+    private Line(final double angle, final double cos, final double sin, final double originOffset) {
+        this.angle        = angle;
+        this.cos          = cos;
+        this.sin          = sin;
+        this.originOffset = originOffset;
+    }
+
+    /** Copy constructor.
+     * <p>The created instance is completely independant from the
+     * original instance, it is a deep copy.</p>
+     * @param line line to copy
+     */
+    public Line(final Line line) {
+        angle        = MathUtils.normalizeAngle(line.angle, FastMath.PI);
+        cos          = FastMath.cos(angle);
+        sin          = FastMath.sin(angle);
+        originOffset = line.originOffset;
+    }
+
+    /** {@inheritDoc} */
+    public Hyperplane copySelf() {
+        return new Line(this);
+    }
+
+    /** Reset the instance as if built from two points.
+     * <p>The line is oriented from p1 to p2</p>
+     * @param p1 first point
+     * @param p2 second point
+     */
+    public void reset(final Point2D p1, final Point2D p2) {
+        final double dx = p2.x - p1.x;
+        final double dy = p2.y - p1.y;
+        final double d = FastMath.hypot(dx, dy);
+        if (d == 0.0) {
+            angle        = 0.0;
+            cos          = 1.0;
+            sin          = 0.0;
+            originOffset = p1.y;
+        } else {
+            angle        = FastMath.PI + FastMath.atan2(-dy, -dx);
+            cos          = FastMath.cos(angle);
+            sin          = FastMath.sin(angle);
+            originOffset = (p2.x * p1.y - p1.x * p2.y) / d;
+        }
+    }
+
+    /** Reset the instance as if built from a line and an angle.
+     * @param p point belonging to the line
+     * @param alpha angle of the line with respect to abscissa axis
+     */
+    public void reset(final Point2D p, final double alpha) {
+        this.angle   = MathUtils.normalizeAngle(alpha, FastMath.PI);
+        cos          = FastMath.cos(this.angle);
+        sin          = FastMath.sin(this.angle);
+        originOffset = cos * p.y - sin * p.x;
+    }
+
+    /** Revert the instance.
+     */
+    public void revertSelf() {
+        if (angle < FastMath.PI) {
+            angle += FastMath.PI;
+        } else {
+            angle -= FastMath.PI;
+        }
+        cos          = -cos;
+        sin          = -sin;
+        originOffset = -originOffset;
+    }
+
+    /** Get the reverse of the instance.
+     * <p>Get a line with reversed orientation with respect to the
+     * instance. A new object is built, the instance is untouched.</p>
+     * @return a new line, with orientation opposite to the instance orientation
+     */
+    public Line getReverse() {
+        return new Line((angle < FastMath.PI) ? (angle + FastMath.PI) : (angle - FastMath.PI),
+                        -cos, -sin, -originOffset);
+    }
+
+    /** Transform a 2D space point into a line point.
+     * @param point 2D point (must be a {@link Point2D Point2D}
+     * instance)
+     * @return line point corresponding to the 2D point (really a {@link
+     * org.apache.commons.bsp.euclidean.oneD.Point1D Point1D} instance)
+     * @see #toSpace
+     */
+    public Point toSubSpace(final Point point) {
+        final Point2D p2D = (Point2D) point;
+        return new Point1D(cos * p2D.x + sin * p2D.y);
+    }
+
+    /** Get one point from the line.
+     * @param point desired abscissa for the point (must be a {@link
+     * org.apache.commons.bsp.euclidean.oneD.Point1D Point1D} instance)
+     * @return line point at specified abscissa (really a {@link Point2D
+     * Point2D} instance)
+     */
+    public Point toSpace(final Point point) {
+        final double abscissa = ((Point1D) point).getAbscissa();
+        return new Point2D(abscissa * cos - originOffset * sin,
+                           abscissa * sin + originOffset * cos);
+    }
+
+    /** Get the intersection point of the instance and another line.
+     * @param other other line
+     * @return intersection point of the instance and the other line
+     * (really a {@link Point2D Point2D} instance)
+     */
+    public SubSpace intersection(final Hyperplane other) {
+        final Line otherL = (Line) other;
+        final double d = sin * otherL.cos - otherL.sin * cos;
+        if (FastMath.abs(d) < 1.0e-10) {
+            return null;
+        }
+        return new Point2D((cos * otherL.originOffset - otherL.cos * originOffset) / d,
+                           (sin * otherL.originOffset - otherL.sin * originOffset) / d);
+    }
+
+    /** Build a region covering the whole hyperplane.
+     * @return a region covering the whole hyperplane
+     */
+    public Region wholeHyperplane() {
+        return new IntervalsSet();
+    }
+
+    /** Build a region covering the whole space.
+     * @return a region containing the instance (really a {@link
+     * PolygonsSet PolygonsSet} instance)
+     */
+    public Region wholeSpace() {
+        return new PolygonsSet();
+    }
+
+    /** Get the offset (oriented distance) of a parallel line.
+     * <p>This method should be called only for parallel lines otherwise
+     * the result is not meaningful.</p>
+     * <p>The offset is 0 if both lines are the same, it is
+     * positive if the line is on the right side of the instance and
+     * negative if it is on the left side, according to its natural
+     * orientation.</p>
+     * @param line line to check
+     * @return offset of the line
+     */
+    public double getOffset(final Line line) {
+        return originOffset +
+               ((cos * line.cos + sin * line.sin > 0) ? -line.originOffset : line.originOffset);
+    }
+
+    /** Get the offset (oriented distance) of a point to the line.
+     * <p>The offset is 0 if the point belongs to the line, it is
+     * positive if the point is on the right side of the line and
+     * negative if it is on the left side, according to its natural
+     * orientation.</p>
+     * @param point point to check (must be a {@link Point2D Point2D} instance)
+     * @return offset of the point
+     */
+    public double getOffset(final Point point) {
+        final Point2D p2D = (Point2D) point;
+        return sin * p2D.x - cos * p2D.y + originOffset;
+    }
+
+    /** Check if the instance has the same orientation as another hyperplane.
+     * <p>This method is expected to be called on parallel hyperplanes
+     * (i.e. when the {@link #side side} method would return {@link
+     * org.apache.commons.bsp.partitioning.Hyperplane.Side#HYPER HYPER}
+     * for some sub-hyperplane having the specified hyperplane
+     * as its underlying hyperplane). The method should <em>not</em>
+     * re-check for parallelism, only for orientation, typically by
+     * testing something like the sign of the dot-products of
+     * normals.</p>
+     * @param other other hyperplane to check against the instance
+     * @return true if the instance and the other hyperplane have
+     * the same orientation
+     */
+    public boolean sameOrientationAs(final Hyperplane other) {
+        final Line otherL = (Line) other;
+        return (sin * otherL.sin + cos * otherL.cos) >= 0.0;
+    }
+
+    /** Get one point from the plane.
+     * @param abscissa desired abscissa for the point
+     * @param offset desired offset for the point
+     * @return one point in the plane, with given abscissa and offset
+     * relative to the line
+     */
+    public Point2D getPointAt(final Point1D abscissa, final double offset) {
+        final double x       = abscissa.getAbscissa();
+        final double dOffset = offset - originOffset;
+        return new Point2D(x * cos + dOffset * sin, x * sin - dOffset * cos);
+    }
+
+    /** Check if the line contains a point.
+     * @param p point to check
+     * @return true if p belongs to the line
+     */
+    public boolean contains(final Point2D p) {
+        return FastMath.abs(getOffset(p)) < 1.0e-10;
+    }
+
+    /** Check the instance is parallel to another line.
+     * @param line other line to check
+     * @return true if the instance is parallel to the other line
+     * (they can have either the same or opposite orientations)
+     */
+    public boolean isParallelTo(final Line line) {
+        return FastMath.abs(sin * line.cos - cos * line.sin) < 1.0e-10;
+    }
+
+    /** Translate the line to force it passing by a point.
+     * @param p point by which the line should pass
+     */
+    public void translateToPoint(final Point2D p) {
+        originOffset = cos * p.y - sin * p.x;
+    }
+
+    /** Get the angle of the line.
+     * @return the angle of the line with respect to the abscissa axis
+     */
+    public double getAngle() {
+        return MathUtils.normalizeAngle(angle, FastMath.PI);
+    }
+
+    /** Set the angle of the line.
+     * @param angle new angle of the line with respect to the abscissa axis
+     */
+    public void setAngle(final double angle) {
+        this.angle = MathUtils.normalizeAngle(angle, FastMath.PI);
+        cos        = FastMath.cos(this.angle);
+        sin        = FastMath.sin(this.angle);
+    }
+
+    /** Get the offset of the origin.
+     * @return the offset of the origin
+     */
+    public double getOriginOffset() {
+        return originOffset;
+    }
+
+    /** Set the offset of the origin.
+     * @param offset offset of the origin
+     */
+    public void setOriginOffset(final double offset) {
+        originOffset = offset;
+    }
+
+    /** Compute the relative position of a sub-hyperplane with respect
+     * to the instance.
+     * @param sub sub-hyperplane to check
+     * @return one of {@link org.apache.commons.bsp.partitioning.Hyperplane.Side#PLUS PLUS},
+     * {@link org.apache.commons.bsp.partitioning.Hyperplane.Side#MINUS MINUS},
+     * {@link org.apache.commons.bsp.partitioning.Hyperplane.Side#BOTH BOTH},
+     * {@link org.apache.commons.bsp.partitioning.Hyperplane.Side#HYPER HYPER}
+     */
+    public Side side(final SubHyperplane sub) {
+
+        final Hyperplane otherHyp = sub.getHyperplane();
+        final Point2D    crossing = (Point2D) intersection(otherHyp);
+
+        if (crossing == null) {
+            // the lines are parallel,
+            final double global = getOffset((Line) otherHyp);
+            return (global < -1.0e-10) ? Side.MINUS : ((global > 1.0e-10) ? Side.PLUS : Side.HYPER);
+        }
+
+        // the lines do intersect
+        final boolean direct = FastMath.sin(((Line) otherHyp).angle - angle) < 0;
+        final Point1D x = (Point1D) otherHyp.toSubSpace(crossing);
+        return sub.getRemainingRegion().side(new OrientedPoint(x, direct));
+
+    }
+
+    /** Split a sub-hyperplane in two parts by the instance.
+     * @param sub sub-hyperplane to split
+     * @return an object containing both the part of the sub-hyperplane
+     * on the plus side of the instance and the part of the
+     * sub-hyperplane on the minus side of the instance
+     */
+    public SplitSubHyperplane split(final SubHyperplane sub) {
+
+        final Line    otherLine = (Line) sub.getHyperplane();
+        final Point2D crossing  = (Point2D) intersection(otherLine);
+
+        if (crossing == null) {
+            // the lines are parallel
+            final double global = getOffset(otherLine);
+            return (global < -1.0e-10) ?
+                   new SplitSubHyperplane(null, sub) :
+                   new SplitSubHyperplane(sub, null);
+        }
+
+        // the lines do intersect
+        final boolean direct = FastMath.sin(otherLine.angle - angle) < 0;
+        final Point1D x      = (Point1D) otherLine.toSubSpace(crossing);
+        final SubHyperplane subPlus  = new SubHyperplane(new OrientedPoint(x, !direct));
+        final SubHyperplane subMinus = new SubHyperplane(new OrientedPoint(x, direct));
+
+        final BSPTree splitTree =
+            sub.getRemainingRegion().getTree(false).split(subMinus);
+        final BSPTree plusTree  = Region.isEmpty(splitTree.getPlus()) ?
+                                  new BSPTree(Boolean.FALSE) :
+                                  new BSPTree(subPlus, new BSPTree(Boolean.FALSE),
+                                              splitTree.getPlus(), null);
+        final BSPTree minusTree = Region.isEmpty(splitTree.getMinus()) ?
+                                  new BSPTree(Boolean.FALSE) :
+                                  new BSPTree(subMinus, new BSPTree(Boolean.FALSE),
+                                              splitTree.getMinus(), null);
+
+        return new SplitSubHyperplane(new SubHyperplane(otherLine.copySelf(),
+                                                        new IntervalsSet(plusTree)),
+                                                        new SubHyperplane(otherLine.copySelf(),
+                                                                          new IntervalsSet(minusTree)));
+
+    }
+
+    /** Get a {@link org.apache.commons.bsp.partitioning.Transform
+     * Transform} embedding an affine transform.
+     * @param transform affine transform to embed (must be inversible
+     * otherwise the {@link
+     * org.apache.commons.bsp.partitioning.Transform#apply(Hyperplane)
+     * apply(Hyperplane)} method would work only for some lines, and
+     * fail for other ones)
+     * @return a new transform that can be applied to either {@link
+     * Point2D Point2D}, {@link Line Line} or {@link
+     * org.apache.commons.bsp.partitioning.SubHyperplane
+     * SubHyperplane} instances
+     * @exception BSPException if the transform is non invertible
+     */
+    public static Transform getTransform(final AffineTransform transform) throws BSPException {
+        return new LineTransform(transform);
+    }
+
+    /** Class embedding an affine transform.
+     * <p>This class is used in order to apply an affine transform to a
+     * line. Using a specific object allow to perform some computations
+     * on the transform only once even if the same transform is to be
+     * applied to a large number of lines (for example to a large
+     * polygon)./<p>
+     */
+    private static class LineTransform implements Transform {
+
+        // CHECKSTYLE: stop JavadocVariable check
+        private double cXX;
+        private double cXY;
+        private double cX1;
+        private double cYX;
+        private double cYY;
+        private double cY1;
+
+        private double c1Y;
+        private double c1X;
+        private double c11;
+        // CHECKSTYLE: resume JavadocVariable check
+
+        /** Build an affine line transform from a n {@code AffineTransform}.
+         * @param transform transform to use (must be invertible otherwise
+         * the {@link LineTransform#apply(Hyperplane)} method would work
+         * only for some lines, and fail for other ones)
+         * @exception BSPException if the transform is non invertible
+         */
+        public LineTransform(final AffineTransform transform) throws BSPException {
+
+            final double[] m = new double[6];
+            transform.getMatrix(m);
+            cXX = m[0];
+            cXY = m[2];
+            cX1 = m[4];
+            cYX = m[1];
+            cYY = m[3];
+            cY1 = m[5];
+
+            c1Y = cXY * cY1 - cYY * cX1;
+            c1X = cXX * cY1 - cYX * cX1;
+            c11 = cXX * cYY - cYX * cXY;
+
+            if (FastMath.abs(c11) < 1.0e-20) {
+                throw new BSPException(BSPMessages.NON_INVERTIBLE_TRANSFORM);
+            }
+
+        }
+
+        /** {@inheritDoc} */
+        public Point apply(final Point point) {
+            final Point2D p2D = (Point2D) point;
+            final double  x   = p2D.getX();
+            final double  y   = p2D.getY();
+            return new Point2D(cXX * x + cXY * y + cX1,
+                               cYX * x + cYY * y + cY1);
+        }
+
+        /** {@inheritDoc} */
+        public Hyperplane apply(final Hyperplane hyperplane) {
+            final Line   line    = (Line) hyperplane;
+            final double rOffset = c1X * line.cos + c1Y * line.sin + c11 * line.originOffset;
+            final double rCos    = cXX * line.cos + cXY * line.sin;
+            final double rSin    = cYX * line.cos + cYY * line.sin;
+            final double inv     = 1.0 / FastMath.sqrt(rSin * rSin + rCos * rCos);
+            return new Line(FastMath.PI + FastMath.atan2(-rSin, -rCos),
+                            inv * rCos, inv * rSin,
+                            inv * rOffset);
+        }
+
+        /** {@inheritDoc} */
+        public SubHyperplane apply(final SubHyperplane sub,
+                                   final Hyperplane original, final Hyperplane transformed) {
+            final OrientedPoint op = (OrientedPoint) sub.getHyperplane();
+            final Point1D newLoc =
+                (Point1D) transformed.toSubSpace(apply(original.toSpace(op.getLocation())));
+            return new SubHyperplane(new OrientedPoint(newLoc, op.isDirect()));
+        }
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Line.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Line.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/NestedLoops.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/NestedLoops.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/NestedLoops.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/NestedLoops.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,190 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import org.apache.commons.bsp.BSPException;
+import org.apache.commons.bsp.BSPMessages;
+import org.apache.commons.bsp.euclidean.oneD.OrientedPoint;
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.partitioning.Hyperplane;
+import org.apache.commons.bsp.partitioning.Region;
+import org.apache.commons.bsp.partitioning.SubHyperplane;
+
+import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.Iterator;
+
+/** This class represent a tree of nested 2D boundary loops.
+
+ * <p>This class is used during Piece instances construction.
+ * Beams are built using the outline edges as
+ * representative of facets, the orientation of these facets are
+ * meaningful. However, we want to allow the user to specify its
+ * outline loops without having to take care of this orientation. This
+ * class is devoted to correct mis-oriented loops.<p>
+
+ * <p>Orientation is computed assuming the piece is finite, i.e. the
+ * outermost loops have their exterior side facing points at infinity,
+ * and hence are oriented counter-clockwise. The orientation of
+ * internal loops is computed as the reverse of the orientation of
+ * their immediate surrounding loop.</p>
+
+ * @version $Revision$ $Date$
+ */
+class NestedLoops {
+
+    /** Boundary loop. */
+    private Point2D[] loop;
+
+    /** Surrounded loops. */
+    private ArrayList<NestedLoops> surrounded;
+
+    /** Polygon enclosing a finite region. */
+    private Region polygon;
+
+    /** Indicator for original loop orientation. */
+    private boolean originalIsClockwise;
+
+    /** Simple Constructor.
+     * <p>Build an empty tree of nested loops. This instance will become
+     * the root node of a complete tree, it is not associated with any
+     * loop by itself, the outermost loops are in the root tree child
+     * nodes.</p>
+     */
+    public NestedLoops() {
+        surrounded = new ArrayList<NestedLoops>();
+    }
+
+    /** Constructor.
+     * <p>Build a tree node with neither parent nor children</p>
+     * @param loop boundary loop (will be reversed in place if needed)
+     * @exception BSPException if an outline has an open boundary loop
+     */
+    private NestedLoops(final Point2D[] loop) throws BSPException {
+
+        if (loop[0] == null) {
+            throw new BSPException(BSPMessages.OUTLINE_BOUNDARY_LOOP_OPEN);
+        }
+
+        this.loop = loop;
+        surrounded = new ArrayList<NestedLoops>();
+
+        // build the polygon defined by the loop
+        final ArrayList<SubHyperplane> edges = new ArrayList<SubHyperplane>();
+        Point2D current = loop[loop.length - 1];
+        for (int i = 0; i < loop.length; ++i) {
+            final Point2D previous = current;
+            current = loop[i];
+            final Line   line   = new Line(previous, current);
+            final Region region =  Region.buildConvex(Arrays.asList(new Hyperplane[] {
+                new OrientedPoint((Point1D) line.toSubSpace(previous), false),
+                new OrientedPoint((Point1D) line.toSubSpace(current),  true)
+            }));
+            edges.add(new SubHyperplane(line, region));
+        }
+        polygon = new PolygonsSet(edges);
+
+        // ensure the polygon encloses a finite region of the plane
+        if (Double.isInfinite(polygon.getSize())) {
+            polygon = polygon.getComplement();
+            originalIsClockwise = false;
+        } else {
+            originalIsClockwise = true;
+        }
+
+    }
+
+    /** Add a loop in a tree.
+     * @param bLoop boundary loop (will be reversed in place if needed)
+     * @exception BSPException if an outline has crossing
+     * boundary loops or open boundary loops
+     */
+    public void add(final Point2D[] bLoop) throws BSPException {
+        add(new NestedLoops(bLoop));
+    }
+
+    /** Add a loop in a tree.
+     * @param node boundary loop (will be reversed in place if needed)
+     * @exception BSPException if an outline has boundary
+     * loops that cross each other
+     */
+    private void add(final NestedLoops node) throws BSPException {
+
+        // check if we can go deeper in the tree
+        for (final NestedLoops child : surrounded) {
+            if (child.polygon.contains(node.polygon)) {
+                child.add(node);
+                return;
+            }
+        }
+
+        // check if we can absorb some of the instance children
+        for (final Iterator<NestedLoops> iterator = surrounded.iterator(); iterator.hasNext();) {
+            final NestedLoops child = iterator.next();
+            if (node.polygon.contains(child.polygon)) {
+                node.surrounded.add(child);
+                iterator.remove();
+            }
+        }
+
+        // we should be separate from the remaining children
+        for (final NestedLoops child : surrounded) {
+            if (!Region.intersection(node.polygon, child.polygon).isEmpty()) {
+                throw new BSPException(BSPMessages.CROSSING_BOUNDARY_LOOPS);
+            }
+        }
+
+        surrounded.add(node);
+
+    }
+
+    /** Correct the orientation of the loops contained in the tree.
+     * <p>This is this method that really inverts the loops that where
+     * provided through the {@link #add(Point2D[]) add} method if
+     * they are mis-oriented</p>
+     */
+    public void correctOrientation() {
+        for (NestedLoops child : surrounded) {
+            child.setClockWise(true);
+        }
+    }
+
+    /** Set the loop orientation.
+     * @param clockwise if true, the loop should be set to clockwise
+     * orientation
+     */
+    private void setClockWise(final boolean clockwise) {
+
+        if (originalIsClockwise ^ clockwise) {
+            // we need to inverse the original loop
+            int min = -1;
+            int max = loop.length;
+            while (++min < --max) {
+                final Point2D tmp = loop[min];
+                loop[min] = loop[max];
+                loop[max] = tmp;
+            }
+        }
+
+        // go deeper in the tree
+        for (final NestedLoops child : surrounded) {
+            child.setClockWise(!clockwise);
+        }
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/NestedLoops.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/NestedLoops.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Point2D.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Point2D.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Point2D.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Point2D.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,72 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import org.apache.commons.bsp.partitioning.Point;
+import org.apache.commons.bsp.partitioning.SubSpace;
+
+/** This class represents a 2D point.
+ * <p>Instances of this class are guaranteed to be immutable.</p>
+ * @version $Revision$ $Date$
+ */
+public class Point2D extends java.awt.geom.Point2D.Double implements Point, SubSpace {
+
+    /** Point at undefined (NaN) coordinates. */
+    public static final Point2D UNDEFINED = new Point2D(java.lang.Double.NaN, java.lang.Double.NaN);
+
+    /** Serializable UID. */
+    private static final long serialVersionUID = 8883702098988517151L;
+
+    /** Build a point with default coordinates.
+     */
+    public Point2D() {
+    }
+
+    /** Build a point from its coordinates.
+     * @param x abscissa
+     * @param y ordinate
+     */
+    public Point2D(final double x, final double y) {
+        super(x, y);
+    }
+
+    /** Build a point from a java awt point.
+     * @param point java awt point
+     */
+    public Point2D(final java.awt.geom.Point2D.Double point) {
+        super(point.x, point.y);
+    }
+
+    /** Transform a 2D space point into a sub-space point.
+     * @param point 2D point of the space
+     * @return always return null
+     * @see #toSpace
+     */
+    public Point toSubSpace(final Point point) {
+        return null;
+    }
+
+    /** Transform a sub-space point into a space point.
+     * @param point ignored parameter
+     * @return always return the instance
+     * @see #toSubSpace
+     */
+    public Point toSpace(final Point point) {
+        return this;
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Point2D.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Point2D.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/PolygonsSet.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/PolygonsSet.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/PolygonsSet.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/PolygonsSet.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,343 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.partitioning.BSPTree;
+import org.apache.commons.bsp.partitioning.Hyperplane;
+import org.apache.commons.bsp.partitioning.Region;
+import org.apache.commons.bsp.partitioning.SubHyperplane;
+import org.apache.commons.bsp.utilities.AVLTree;
+import org.apache.commons.math.util.FastMath;
+
+/** This class represents a 2D region: a set of polygons.
+ * @version $Revision$ $Date$
+ */
+public class PolygonsSet extends Region {
+
+    /** Vertices organized as boundary loops. */
+    private Point2D[][] vertices;
+
+    /** Build a polygons set representing the whole real line.
+     */
+    public PolygonsSet() {
+        super();
+    }
+
+    /** Build a polygons set from a BSP tree.
+     * <p>The leaf nodes of the BSP tree <em>must</em> have a
+     * {@code Boolean} attribute representing the inside status of
+     * the corresponding cell (true for inside cells, false for outside
+     * cells). In order to avoid building too many small objects, it is
+     * recommended to use the predefined constants
+     * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
+     * @param tree inside/outside BSP tree representing the region
+     */
+    public PolygonsSet(final BSPTree tree) {
+        super(tree);
+    }
+
+    /** Build a polygons set from a Boundary REPresentation (B-rep).
+     * <p>The boundary is provided as a collection of {@link
+     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
+     * interior part of the region on its minus side and the exterior on
+     * its plus side.</p>
+     * <p>The boundary elements can be in any order, and can form
+     * several non-connected sets (like for example polygons with holes
+     * or a set of disjoints polyhedrons considered as a whole). In
+     * fact, the elements do not even need to be connected together
+     * (their topological connections are not used here). However, if the
+     * boundary does not really separate an inside open from an outside
+     * open (open having here its topological meaning), then subsequent
+     * calls to the {@link
+     * Region#checkPoint(org.apache.commons.bsp.partitioning.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
+     */
+    public PolygonsSet(final Collection<SubHyperplane> boundary) {
+        super(boundary);
+    }
+
+    /** Build a parallellepipedic box.
+     * @param xMin low bound along the x direction
+     * @param xMax high bound along the x direction
+     * @param yMin low bound along the y direction
+     * @param yMax high bound along the y direction
+     */
+    public PolygonsSet(final double xMin, final double xMax,
+                       final double yMin, final double yMax) {
+        this(buildConvex(boxBoundary(xMin, xMax, yMin, yMax)).getTree(false));
+    }
+
+    /** Create a list of hyperplanes representing the boundary of a box.
+     * @param xMin low bound along the x direction
+     * @param xMax high bound along the x direction
+     * @param yMin low bound along the y direction
+     * @param yMax high bound along the y direction
+     * @return boundary of the box
+     */
+    private static List<Hyperplane> boxBoundary(final double xMin, final double xMax,
+                                                final double yMin, final double yMax) {
+        final Point2D minMin = new Point2D(xMin, yMin);
+        final Point2D minMax = new Point2D(xMin, yMax);
+        final Point2D maxMin = new Point2D(xMax, yMin);
+        final Point2D maxMax = new Point2D(xMax, yMax);
+        return Arrays.asList(new Hyperplane[] {
+            new Line(minMin, maxMin),
+            new Line(maxMin, maxMax),
+            new Line(maxMax, minMax),
+            new Line(minMax, minMin)
+        });
+    }
+
+    /** {@inheritDoc} */
+    public Region buildNew(final BSPTree tree) {
+        return new PolygonsSet(tree);
+    }
+
+    /** {@inheritDoc} */
+    protected void computeGeometricalProperties() {
+
+        final Point2D[][] v = getVertices();
+
+        if (v.length == 0) {
+            if ((Boolean) getTree(false).getAttribute()) {
+                setSize(Double.POSITIVE_INFINITY);
+                setBarycenter(Point2D.UNDEFINED);
+            } else {
+                setSize(0);
+                setBarycenter(new Point2D(0, 0));
+            }
+        } else if (v[0][0] == null) {
+            // there is at least one open-loop: the polygon is infinite
+            setSize(Double.POSITIVE_INFINITY);
+            setBarycenter(Point2D.UNDEFINED);
+        } else {
+            // all loops are closed, we compute some integrals around the shape
+
+            double sum  = 0;
+            double sumX = 0;
+            double sumY = 0;
+
+            for (Point2D[] loop : v) {
+                double x1 = loop[loop.length - 1].x;
+                double y1 = loop[loop.length - 1].y;
+                for (final Point2D point : loop) {
+                    final double x0 = x1;
+                    final double y0 = y1;
+                    x1 = point.x;
+                    y1 = point.y;
+                    final double factor = x0 * y1 - y0 * x1;
+                    sum  += factor;
+                    sumX += factor * (x0 + x1);
+                    sumY += factor * (y0 + y1);
+                }
+            }
+
+            if (sum < 0) {
+                // the polygon as a finite outside surrounded by an infinite inside
+                setSize(Double.POSITIVE_INFINITY);
+                setBarycenter(Point2D.UNDEFINED);
+            } else {
+                setSize(sum / 2);
+                setBarycenter(new Point2D(sumX / (3 * sum), sumY / (3 * sum)));
+            }
+
+        }
+
+    }
+
+    /** Get the vertices of the polygon.
+     * <p>The polygon boundary can be represented as an array of loops,
+     * each loop being itself an array of vertices.</p>
+     * <p>In order to identify open loops which start and end by
+     * infinite edges, the open loops arrays start with a null point. In
+     * this case, the first non null point and the last point of the
+     * array do not represent real vertices, they are dummy points
+     * intended only to get the direction of the first and last edge. An
+     * open loop consisting of a single infinite line will therefore be
+     * represented by a three elements array with one null point
+     * followed by two dummy points. The open loops are always the first
+     * ones in the loops array.</p>
+     * <p>If the polygon has no boundary at all, a zero length loop
+     * array will be returned.</p>
+     * <p>All line segments in the various loops have the inside of the
+     * region on their left side and the outside on their right side
+     * when moving in the underlying line direction. This means that
+     * closed loops surrounding finite areas obey the direct
+     * trigonometric orientation.</p>
+     * @return vertices of the polygon, organized as oriented boundary
+     * loops with the open loops first (the returned value is guaranteed
+     * to be non-null)
+     */
+    public Point2D[][] getVertices() {
+        if (vertices == null) {
+            if (getTree(false).getCut() == null) {
+                vertices = new Point2D[0][];
+            } else {
+
+                // sort the segmfinal ents according to their start point
+                final SegmentsBuilder visitor = new SegmentsBuilder();
+                getTree(true).visit(visitor);
+                final AVLTree<Segment> sorted = visitor.getSorted();
+
+                // identify the loops, starting from the open ones
+                // (their start segments final are naturally at the sorted set beginning)
+                final ArrayList<List<Segment>> loops = new ArrayList<List<Segment>>();
+                while (!sorted.isEmpty()) {
+                    final AVLTree<Segment>.Node node = sorted.getSmallest();
+                    final List<Segment> loop = followLoop(node, sorted);
+                    if (loop != null) {
+                        loops.add(loop);
+                    }
+                }
+
+                // tranform the loops in an array of arrays of points
+                vertices = new Point2D[loops.size()][];
+                int i = 0;
+
+                for (final List<Segment> loop : loops) {
+                    if (loop.size() < 2) {
+                        // sifinal ngle infinite line
+                        final Line line = ((Segment) loop.get(0)).getLine();
+                        vertices[i++] = new Point2D[] {
+                            null,
+                            (Point2D) line.toSpace(new Point1D(-Float.MAX_VALUE)),
+                            (Point2D) line.toSpace(new Point1D(+Float.MAX_VALUE))
+                        };
+                    } else if (((Segment) loop.get(0)).getStart() == null) {
+                        // open lofinal op with at least one real point
+                        final Point2D[] array = new Point2D[loop.size() + 2];
+                        int j = 0;
+                        for (Segment segment : loop) {
+
+                            if (j == 0) {
+                                // null point and first dummy point
+                                double x =
+                                    ((Point1D) segment.getLine().toSubSpace(segment.getEnd())).getAbscissa();
+                                x -= FastMath.max(1.0, FastMath.abs(x / 2));
+                                array[j++] = null;
+                                array[j++] = (Point2D) segment.getLine().toSpace(new Point1D(x));
+                            }
+
+                            if (j < (array.length - 1)) {
+                                // current point
+                                array[j++] = segment.getEnd();
+                            }
+
+                            if (j == (array.length - 1)) {
+                                // last dummy point
+                                double x =
+                                    ((Point1D) segment.getLine().toSubSpace(segment.getStart())).getAbscissa();
+                                x += FastMath.max(1.0, FastMath.abs(x / 2));
+                                array[j++] = (Point2D) segment.getLine().toSpace(new Point1D(x));
+                            }
+
+                        }
+                        vertices[i++] = array;
+                    } else {
+                        final Point2D[] array = new Point2D[loop.size()];
+                        int j = 0;
+                        for (Segment segment : loop) {
+                            array[j++] = segment.getStart();
+                        }
+                        vertices[i++] = array;
+                    }
+                }
+
+            }
+        }
+
+        return vertices.clone();
+
+    }
+
+    /** Follow a boundary loop.
+     * @param node node containing the segment starting the loop
+     * @param sorted set of segments belonging to the boundary, sorted by
+     * start points (contains {@code node})
+     * @return a list of connected sub-hyperplanes starting at
+     * {@code node}
+     */
+    private List<Segment> followLoop(final AVLTree<Segment>.Node node,
+                                     final AVLTree<Segment> sorted) {
+
+        final ArrayList<Segment> loop = new ArrayList<Segment>();
+        Segment segment = (Segment) node.getElement();
+        loop.add(segment);
+        final Point2D globalStart = segment.getStart();
+        Point2D end = segment.getEnd();
+        node.delete();
+
+        // is this an open or a closed loop ?
+        final boolean open = segment.getStart() == null;
+
+        while ((end != null) && (open || (globalStart.distance(end) > 1.0e-10))) {
+
+            // search the sub-hyperplane starting where the previous one ended
+            AVLTree<Segment>.Node selectedNode = null;
+            Segment       selectedSegment  = null;
+            double        selectedDistance = Double.POSITIVE_INFINITY;
+            final Segment lowerLeft        = new Segment(end, -1.0e-10, -1.0e-10);
+            final Segment upperRight       = new Segment(end, +1.0e-10, +1.0e-10);
+            for (AVLTree<Segment>.Node n = sorted.getNotSmaller(lowerLeft);
+                 (n != null) && (n.getElement().compareTo(upperRight) <= 0);
+                 n = n.getNext()) {
+                segment = (Segment) n.getElement();
+                final double distance = end.distance(segment.getStart());
+                if (distance < selectedDistance) {
+                    selectedNode     = n;
+                    selectedSegment  = segment;
+                    selectedDistance = distance;
+                }
+            }
+
+            if (selectedDistance > 1.0e-10) {
+                // this is a degenerated loop, it probably comes from a very
+                // tiny region with some segments smaller than the threshold, we
+                // simply ignore it
+                return null;
+            }
+
+            end = selectedSegment.getEnd();
+            loop.add(selectedSegment);
+            selectedNode.delete();
+
+        }
+
+        if ((loop.size() == 2) && !open) {
+            // this is a degenerated infinitely thin loop, we simply ignore it
+            return null;
+        }
+
+        if ((end == null) && !open) {
+            throw new RuntimeException("internal error");
+        }
+
+        return loop;
+
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/PolygonsSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/PolygonsSet.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Segment.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Segment.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Segment.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Segment.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,112 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import org.apache.commons.bsp.utilities.OrderedTuple;
+
+/** This class holds segments information before they are connected.
+ * @version $Revision$ $Date$
+ */
+class Segment implements Comparable<Segment> {
+
+    /** Start point of the segment. */
+    private final Point2D      start;
+
+    /** End point of the segments. */
+    private final Point2D      end;
+
+    /** Line containing the segment. */
+    private final Line         line;
+
+    /** Sorting key. */
+    private      OrderedTuple sortingKey;
+
+    /** Build a segment.
+     * @param start start point of the segment
+     * @param end end point of the segment
+     * @param line line containing the segment
+     */
+    public Segment(final Point2D start, final Point2D end, final Line line) {
+        this.start  = start;
+        this.end    = end;
+        this.line   = line;
+        sortingKey = (start == null) ?
+                     new OrderedTuple(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY) :
+                     new OrderedTuple(start.x, start.y);
+    }
+
+    /** Build a dummy segment.
+     * <p>
+     * The object built is not a real segment, only the sorting key is used to
+     * allow searching in the neighborhood of a point. This is an horrible hack ...
+     * </p>
+     * @param start start point of the segment
+     * @param dx abscissa offset from the start point
+     * @param dy ordinate offset from the start point
+     */
+    public Segment(final Point2D start, final double dx, final double dy) {
+        this.start = null;
+        this.end   = null;
+        this.line  = null;
+        sortingKey = new OrderedTuple(start.x + dx, start.y + dy);
+    }
+
+    /** Get the start point of the segment.
+     * @return start point of the segment
+     */
+    public Point2D getStart() {
+        return start;
+    }
+
+    /** Get the end point of the segment.
+     * @return end point of the segment
+     */
+    public Point2D getEnd() {
+        return end;
+    }
+
+    /** Get the line containing the segment.
+     * @return line containing the segment
+     */
+    public Line getLine() {
+        return line;
+    }
+
+    /** {@inheritDoc} */
+    public int compareTo(final Segment o) {
+        return sortingKey.compareTo(o.sortingKey);
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public boolean equals(final Object other) {
+        if (this == other) {
+            return true;
+        } else if (other instanceof Segment) {
+            return compareTo((Segment) other) == 0;
+        } else {
+            return false;
+        }
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public int hashCode() {
+        return start.hashCode() ^ end.hashCode() ^ line.hashCode() ^ sortingKey.hashCode();
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Segment.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Segment.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/SegmentBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/SegmentBuilder.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/SegmentBuilder.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/SegmentBuilder.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,90 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+import java.util.List;
+
+import org.apache.commons.bsp.euclidean.oneD.Interval;
+import org.apache.commons.bsp.euclidean.oneD.IntervalsSet;
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.partitioning.BSPTree;
+import org.apache.commons.bsp.partitioning.BSPTreeVisitor;
+import org.apache.commons.bsp.partitioning.SubHyperplane;
+import org.apache.commons.bsp.partitioning.Region.BoundaryAttribute;
+import org.apache.commons.bsp.utilities.AVLTree;
+
+/** Visitor building segments.
+ * @version $Revision$ $Date$
+ */
+class SegmentsBuilder implements BSPTreeVisitor {
+
+    /** Sorted segments. */
+    private AVLTree<Segment> sorted;
+
+    /** Simple constructor. */
+    public SegmentsBuilder() {
+        sorted = new AVLTree<Segment>();
+    }
+
+    /** {@inheritDoc} */
+    public Order visitOrder(final BSPTree node) {
+        return Order.MINUS_SUB_PLUS;
+    }
+
+    /** {@inheritDoc} */
+    public void visitInternalNode(final BSPTree node) {
+        final BoundaryAttribute attribute = (BoundaryAttribute) node.getAttribute();
+        if (attribute.getPlusOutside() != null) {
+            addContribution(attribute.getPlusOutside(), false);
+        }
+        if (attribute.getPlusInside() != null) {
+            addContribution(attribute.getPlusInside(), true);
+        }
+    }
+
+    /** {@inheritDoc} */
+    public void visitLeafNode(final BSPTree node) {
+    }
+
+    /** Add he contribution of a boundary facet.
+     * @param sub boundary facet
+     * @param reversed if true, the facet has the inside on its plus side
+     */
+    private void addContribution(final SubHyperplane sub, final boolean reversed) {
+        final Line line      = (Line) sub.getHyperplane();
+        final List<Interval> intervals = ((IntervalsSet) sub.getRemainingRegion()).asList();
+        for (final Interval i : intervals) {
+            final Point2D start = Double.isInfinite(i.getLower()) ?
+                                  null : (Point2D) line.toSpace(new Point1D(i.getLower()));
+            final Point2D end   = Double.isInfinite(i.getUpper()) ?
+                                  null : (Point2D) line.toSpace(new Point1D(i.getUpper()));
+            if (reversed) {
+                sorted.insert(new Segment(end, start, line.getReverse()));
+            } else {
+                sorted.insert(new Segment(start, end, line));
+            }
+        }
+    }
+
+    /** Get the sorted segments.
+     * @return sorted segments
+     */
+    public AVLTree<Segment> getSorted() {
+        return sorted;
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/SegmentBuilder.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/SegmentBuilder.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Vertex.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Vertex.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Vertex.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Vertex.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,93 @@
+/*
+ * 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.bsp.euclidean.twoD;
+
+/** This class represents a specific 2D point that is a vertex between two edges.
+ * @version $Revision$ $Date$
+ */
+public class Vertex extends Point2D {
+
+    /** Serializable UID. */
+    private static final long serialVersionUID = -1579869438572963104L;
+
+    /** Edge ending at this vertex. */
+    private Edge incoming;
+
+    /** Edge starting at this vertex. */
+    private Edge leaving;
+
+    /** Build a vertex from its coordinates.
+     * @param x abscissa
+     * @param y ordinate
+     */
+    public Vertex(final double x, final double y) {
+        super(x, y);
+        incoming = null;
+        leaving = null;
+    }
+
+    /** Build a vertex from a point.
+     * @param point point corresponding to the vertex
+     */
+    public Vertex(final Point2D point) {
+        super(point);
+        incoming = null;
+        leaving = null;
+    }
+
+    /** Get the edge incoming to the vertex.
+     * @return edge incoming to the vertex
+     */
+    public Edge getIncoming() {
+        return incoming;
+    }
+
+    /** Set the edge incoming to the vertex.
+     * @param incoming edge incoming to the vertex
+     */
+    public void setIncoming(final Edge incoming) {
+        this.incoming = incoming;
+    }
+
+    /** Get the edge leaving to the vertex.
+     * @return edge leaving to the vertex
+     */
+    public Edge getLeaving() {
+        return leaving;
+    }
+
+    /** Set the edge leaving the vertex.
+     * @param leaving edge leaving the vertex
+     */
+    public void setLeaving(final Edge leaving) {
+        this.leaving = leaving;
+    }
+
+    /** Recompute the vertex coordinates from the edges.
+     */
+    public void update() {
+        if ((incoming != null) && (leaving != null)) {
+            final Point2D point =
+                (Point2D) incoming.getLine().intersection(leaving.getLine());
+            if (point != null) {
+                x = point.x;
+                y = point.y;
+            }
+        }
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Vertex.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Vertex.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTree.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTree.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTree.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTree.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,631 @@
+/*
+ * 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.bsp.partitioning;
+
+import org.apache.commons.bsp.partitioning.Hyperplane.Side;
+import org.apache.commons.math.util.FastMath;
+
+/** This class represent a Binary Space Partition tree.
+
+ * <p>BSP trees are an efficient way to represent space partitions and
+ * to associate attributes with each cell. Each node in a BSP tree
+ * represents a convex region which is partitioned in two convex
+ * sub-regions at each side of a cut hyperplane. The root tree
+ * contains the complete space.</p>
+
+ * <p>The main use of such partitions is to use a boolean attribute to
+ * define an inside/outside property, hence representing arbitrary
+ * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
+ * 3D) and to operate on them.</p>
+
+ * <p>Another example would be to represent Voronoi tesselations, the
+ * attribute of each cell holding the defining point of the cell.</p>
+
+ * <p>The application-defined attributes are shared among copied
+ * instances and propagated to split parts. These attributes are not
+ * used by the BSP-tree algorithms themselves, so the application can
+ * use them for any purpose. Since the tree visiting method holds
+ * internal and leaf nodes differently, it is possible to use
+ * different classes for internal nodes attributes and leaf nodes
+ * attributes. This should be used with care, though, because if the
+ * tree is modified in any way after attributes have been set, some
+ * internal nodes may become leaf nodes and some leaf nodes may become
+ * internal nodes.</p>
+
+ * <p>One of the main sources for the development of this package was
+ * Bruce Naylor, John Amanatides and William Thibault paper <a
+ * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
+ * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
+ * Computer Graphics 24(4), August 1990, pp 115-124, published by the
+ * Association for Computing Machinery (ACM).</p>
+
+ * @version $Revision$ $Date$
+ */
+public class BSPTree {
+
+    /** Cut sub-hyperplane. */
+    private SubHyperplane cut;
+
+    /** Tree at the plus side of the cut hyperplane. */
+    private BSPTree plus;
+
+    /** Tree at the minus side of the cut hyperplane. */
+    private BSPTree minus;
+
+    /** Parent tree. */
+    private BSPTree parent;
+
+    /** Application-defined attribute. */
+    private Object attribute;
+
+    /** Build a tree having only one root cell representing the whole space.
+     */
+    public BSPTree() {
+        cut       = null;
+        plus      = null;
+        minus     = null;
+        parent    = null;
+        attribute = null;
+    }
+
+    /** Build a tree having only one root cell representing the whole space.
+     * @param attribute attribute of the tree (may be null)
+     */
+    public BSPTree(final Object attribute) {
+        cut    = null;
+        plus   = null;
+        minus  = null;
+        parent = null;
+        this.attribute = attribute;
+    }
+
+    /** Build a BSPTree from its underlying elements.
+     * <p>This method does <em>not</em> perform any verification on
+     * consistency of its arguments, it should therefore be used only
+     * when then caller knows what it is doing.</p>
+     * <p>This method is mainly useful kto build trees
+     * bottom-up. Building trees top-down is realized with the help of
+     * method {@link #insertCut insertCut}.</p>
+     * @param cut cut sub-hyperplane for the tree
+     * @param plus plus side sub-tree
+     * @param minus minus side sub-tree
+     * @param attribute attribute associated with the node (may be null)
+     * @see #insertCut
+     */
+    public BSPTree(final SubHyperplane cut, final BSPTree plus, final BSPTree minus,
+                   final Object attribute) {
+        this.cut       = cut;
+        this.plus      = plus;
+        this.minus     = minus;
+        this.parent    = null;
+        this.attribute = attribute;
+        plus.parent    = this;
+        minus.parent   = this;
+    }
+
+    /** Insert a cut sub-hyperplane in a node.
+     * <p>The sub-tree starting at this node will be completely
+     * overwritten. The new cut sub-hyperplane will be built from the
+     * intersection of the provided hyperplane with the cell. If the
+     * hyperplane does intersect the cell, the cell will have two
+     * children cells with {@code null} attributes on each side of
+     * the inserted cut sub-hyperplane. If the hyperplane does not
+     * intersect the cell then <em>no</em> cut hyperplane will be
+     * inserted and the cell will be changed to a leaf cell. The
+     * attribute of the node is never changed.</p>
+     * <p>This method is mainly useful when called on leaf nodes
+     * (i.e. nodes for which {@link #getCut getCut} returns
+     * {@code null}), in this case it provides a way to build a
+     * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
+     * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
+     * build trees bottom-up).</p>
+     * @param hyperplane hyperplane to insert, it will be chopped in
+     * order to fit in the cell defined by the parent nodes of the
+     * instance
+     * @return true if a cut sub-hyperplane has been inserted (i.e. if
+     * the cell now has two leaf child nodes)
+     * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
+     */
+    public boolean insertCut(final Hyperplane hyperplane) {
+
+        if (cut != null) {
+            plus.parent  = null;
+            minus.parent = null;
+        }
+
+        final SubHyperplane chopped = fitToCell(new SubHyperplane(hyperplane));
+        if (chopped.getRemainingRegion().isEmpty()) {
+            cut          = null;
+            plus         = null;
+            minus        = null;
+            return false;
+        }
+
+        cut          = chopped;
+        plus         = new BSPTree();
+        plus.parent  = this;
+        minus        = new BSPTree();
+        minus.parent = this;
+        return true;
+
+    }
+
+    /** Copy the instance.
+     * <p>The instance created is completely independant of the original
+     * one. A deep copy is used, none of the underlying objects are
+     * shared (except for the nodes attributes and immutable
+     * objects).</p>
+     * @return a new tree, copy of the instance
+     */
+    public BSPTree copySelf() {
+
+        if (cut == null) {
+            return new BSPTree(attribute);
+        }
+
+        return new BSPTree(cut.copySelf(), plus.copySelf(), minus.copySelf(),
+                           attribute);
+
+    }
+
+    /** Get the cut sub-hyperplane.
+     * @return cut sub-hyperplane, null if this is a leaf tree
+     */
+    public SubHyperplane getCut() {
+        return cut;
+    }
+
+    /** Get the tree on the plus side of the cut hyperplane.
+     * @return tree on the plus side of the cut hyperplane, null if this
+     * is a leaf tree
+     */
+    public BSPTree getPlus() {
+        return plus;
+    }
+
+    /** Get the tree on the minus side of the cut hyperplane.
+     * @return tree on the minus side of the cut hyperplane, null if this
+     * is a leaf tree
+     */
+    public BSPTree getMinus() {
+        return minus;
+    }
+
+    /** Get the parent node.
+     * @return parent node, null if the node has no parents
+     */
+    public BSPTree getParent() {
+        return parent;
+    }
+
+    /** Associate an attribute with the instance.
+     * @param attribute attribute to associate with the node
+     * @see #getAttribute
+     */
+    public void setAttribute(final Object attribute) {
+        this.attribute = attribute;
+    }
+
+    /** Get the attribute associated with the instance.
+     * @return attribute associated with the node or null if no
+     * attribute has been explicitly set using the {@link #setAttribute
+     * setAttribute} method
+     * @see #setAttribute
+     */
+    public Object getAttribute() {
+        return attribute;
+    }
+
+    /** Visit the BSP tree nodes.
+     * @param visitor object visiting the tree nodes
+     */
+    public void visit(final BSPTreeVisitor visitor) {
+        if (cut == null) {
+            visitor.visitLeafNode(this);
+        } else {
+            switch (visitor.visitOrder(this)) {
+            case PLUS_MINUS_SUB:
+                plus.visit(visitor);
+                minus.visit(visitor);
+                visitor.visitInternalNode(this);
+                break;
+            case PLUS_SUB_MINUS:
+                plus.visit(visitor);
+                visitor.visitInternalNode(this);
+                minus.visit(visitor);
+                break;
+            case MINUS_PLUS_SUB:
+                minus.visit(visitor);
+                plus.visit(visitor);
+                visitor.visitInternalNode(this);
+                break;
+            case MINUS_SUB_PLUS:
+                minus.visit(visitor);
+                visitor.visitInternalNode(this);
+                plus.visit(visitor);
+                break;
+            case SUB_PLUS_MINUS:
+                visitor.visitInternalNode(this);
+                plus.visit(visitor);
+                minus.visit(visitor);
+                break;
+            case SUB_MINUS_PLUS:
+                visitor.visitInternalNode(this);
+                minus.visit(visitor);
+                plus.visit(visitor);
+                break;
+            default:
+                throw new RuntimeException("internal error");
+            }
+
+        }
+    }
+
+    /** Fit a sub-hyperplane inside the cell defined by the instance.
+     * <p>Fitting is done by chopping off the parts of the
+     * sub-hyperplane that lie outside of the cell using the
+     * cut-hyperplanes of the parent nodes of the instance.</p>
+     * @param sub sub-hyperplane to fit
+     * @return a new sub-hyperplane, gueranteed to have no part outside
+     * of the instance cell
+     */
+    private SubHyperplane fitToCell(final SubHyperplane sub) {
+        SubHyperplane s = sub;
+        for (BSPTree tree = this; tree.parent != null; tree = tree.parent) {
+            if (tree == tree.parent.plus) {
+                s = tree.parent.cut.getHyperplane().split(s).getPlus();
+            } else {
+                s = tree.parent.cut.getHyperplane().split(s).getMinus();
+            }
+        }
+        return s;
+    }
+
+    /** Get the cell to which a point belongs.
+     * <p>If the returned cell is a leaf node the points belongs to the
+     * interior of the node, if the cell is an internal node the points
+     * belongs to the node cut sub-hyperplane.</p>
+     * @param point point to check
+     * @return the tree cell to which the point belongs (can be
+     */
+    public BSPTree getCell(final Point point) {
+
+        if (cut == null) {
+            return this;
+        }
+
+        // position of the point with respect to the cut hyperplane
+        final double offset = cut.getHyperplane().getOffset(point);
+
+        if (FastMath.abs(offset) < 1.0e-10) {
+            return this;
+        } else if (offset <= 0) {
+            // point is on the minus side of the cut hyperplane
+            return minus.getCell(point);
+        } else {
+            // point is on the plus side of the cut hyperplane
+            return plus.getCell(point);
+        }
+
+    }
+
+    /** Perform condensation on a tree.
+     * <p>The condensation operation is not recursive, it must be called
+     * explicitely from leaves to root.</p>
+     */
+    private void condense() {
+        if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
+            (((plus.attribute == null) && (minus.attribute == null)) ||
+             ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
+            attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
+            cut       = null;
+            plus      = null;
+            minus     = null;
+        }
+    }
+
+    /** Merge a BSP tree with the instance.
+     * <p>All trees are modified (parts of them are reused in the new
+     * tree), it is the responsibility of the caller to ensure a copy
+     * has been done before if any of the former tree should be
+     * preserved, <em>no</em> such copy is done here!</p>
+     * <p>The algorithm used here is directly derived from the one
+     * described in the Naylor, Amanatides and Thibault paper (section
+     * III, Binary Partitioning of a BSP Tree).</p>
+     * @param tree other tree to merge with the instance (will be
+     * <em>unusable</em> after the operation, as well as the
+     * instance itself)
+     * @param leafMerger object implementing the final merging phase
+     * (this is where the semantic of the operation occurs, generally
+     * depending on the attribute of the leaf node)
+     * @return a new tree, result of <code>instance &lt;op&gt;
+     * tree</code>, this value can be ignored if parentTree is not null
+     * since all connections have already been established
+     */
+    public BSPTree merge(final BSPTree tree, final LeafMerger leafMerger) {
+        return merge(tree, leafMerger, null, false);
+    }
+
+    /** Merge a BSP tree with the instance.
+     * @param tree other tree to merge with the instance (will be
+     * <em>unusable</em> after the operation, as well as the
+     * instance itself)
+     * @param leafMerger object implementing the final merging phase
+     * (this is where the semantic of the operation occurs, generally
+     * depending on the attribute of the leaf node)
+     * @param parentTree parent tree to connect to (may be null)
+     * @param isPlusChild if true and if parentTree is not null, the
+     * resulting tree should be the plus child of its parent, ignored if
+     * parentTree is null
+     * @return a new tree, result of <code>instance &lt;op&gt;
+     * tree</code>, this value can be ignored if parentTree is not null
+     * since all connections have already been established
+     */
+    private BSPTree merge(final BSPTree tree, final LeafMerger leafMerger,
+                          final BSPTree parentTree, final boolean isPlusChild) {
+        if (cut == null) {
+            // cell/tree operation
+            return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
+        } else if (tree.cut == null) {
+            // tree/cell operation
+            return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
+        } else {
+            // tree/tree operation
+            final BSPTree merged = tree.split(cut);
+            if (parentTree != null) {
+                merged.parent = parentTree;
+                if (isPlusChild) {
+                    parentTree.plus = merged;
+                } else {
+                    parentTree.minus = merged;
+                }
+            }
+
+            // merging phase
+            plus.merge(merged.plus, leafMerger, merged, true);
+            minus.merge(merged.minus, leafMerger, merged, false);
+            merged.condense();
+            if (merged.cut != null) {
+                merged.cut =
+                    merged.fitToCell(new SubHyperplane(merged.cut.getHyperplane()));
+            }
+
+            return merged;
+
+        }
+    }
+
+    /** This interface gather the merging operations between a BSP tree
+     * leaf and another BSP tree.
+     * <p>As explained in Bruce Naylor, John Amanatides and William
+     * Thibault paper <a
+     * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
+     * BSP Trees Yields Polyhedral Set Operations</a>,
+     * the operations on {@link BSPTree BSP trees} can be expressed as a
+     * generic recursive merging operation where only the final part,
+     * when one of the operand is a leaf, is specific to the real
+     * operation semantics. For example, a tree representing a region
+     * using a boolean attribute to identify inside cells and outside
+     * cells would use four different objects to implement the final
+     * merging phase of the four set operations union, intersection,
+     * difference and symmetric difference (exclusive or).</p>
+     * @version $Revision$ $Date$
+     */
+    public static interface LeafMerger {
+
+        /** Merge a leaf node and a tree node.
+         * <p>This method is called at the end of a recursive merging
+         * resulting from a {@code tree1.merge(tree2, leafMerger)}
+         * call, when one of the sub-trees involved is a leaf (i.e. when
+         * its cut-hyperplane is null). This is the only place where the
+         * precise semantics of the operation are required. For all upper
+         * level nodes in the tree, the merging operation is only a
+         * generic partitioning algorithm.</p>
+         * <p>Since the final operation may be non-commutative, it is
+         * important to know if the leaf node comes from the instance tree
+         * ({@code tree1}) or the argument tree
+         * ({@code tree2}). The third argument of the method is
+         * devoted to this. It can be ignored for commutative
+         * operations.</p>
+         * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method
+         * may be useful to implement this method.</p>
+         * @param leaf leaf node (its cut hyperplane is guaranteed to be
+         * null)
+         * @param tree tree node (its cut hyperplane may be null or not)
+         * @param parentTree parent tree to connect to (may be null)
+         * @param isPlusChild if true and if parentTree is not null, the
+         * resulting tree should be the plus child of its parent, ignored if
+         * parentTree is null
+         * @param leafFromInstance if true, the leaf node comes from the
+         * instance tree ({@code tree1}) and the tree node comes from
+         * the argument tree ({@code tree2})
+         * @return the BSP tree resulting from the merging (may be one of
+         * the arguments)
+         */
+        BSPTree merge(BSPTree leaf, BSPTree tree,
+                      BSPTree parentTree, boolean isPlusChild,
+                      boolean leafFromInstance);
+
+    }
+
+    /** Split a BSP tree by an external sub-hyperplane.
+     * <p>Split a tree in two halves, on each side of the
+     * sub-hyperplane. The instance is not modified.</p>
+     * <p>The tree returned is not upward-consistent: despite all of its
+     * sub-trees cut sub-hyperplanes (including its own cut
+     * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
+     * attached to any parent tree yet. This tree is intended to be
+     * later inserted into an higher level tree.</p>
+     * <p>The algorithm used here is the one given in Naylor, Amanatides
+     * and Thibault paper (section III, Binary Partitioning of a BSP
+     * Tree).</p>
+     * @param sub partitioning sub-hyperplane, must be already clipped
+     * to the convex region represented by the instance, will be used as
+     * the cut sub-hyperplane of the returned tree
+     * @return a tree having the specified sub-hyperplane as its cut
+     * sub-hyperplane, the two parts of the split instance as its two
+     * sub-trees and a null parent
+     */
+    public BSPTree split(final SubHyperplane sub) {
+
+        if (cut == null) {
+            return new BSPTree(sub, copySelf(), new BSPTree(attribute), null);
+        }
+
+        final Hyperplane cHyperplane = cut.getHyperplane();
+        final Hyperplane sHyperplane = sub.getHyperplane();
+        switch (cHyperplane.side(sub)) {
+        case PLUS :
+        { // the partitioning sub-hyperplane is entirely in the plus sub-tree
+            final BSPTree split = plus.split(sub);
+            if (sHyperplane.side(cut) == Side.PLUS) {
+                split.plus = new BSPTree(cut.copySelf(),
+                                         split.plus, minus.copySelf(), attribute);
+                split.plus.condense();
+                split.plus.parent = split;
+            } else {
+                split.minus = new BSPTree(cut.copySelf(),
+                                          split.minus, minus.copySelf(), attribute);
+                split.minus.condense();
+                split.minus.parent = split;
+            }
+            return split;
+        }
+        case MINUS :
+        { // the partitioning sub-hyperplane is entirely in the minus sub-tree
+            final BSPTree split = minus.split(sub);
+            if (sHyperplane.side(cut) == Side.PLUS) {
+                split.plus = new BSPTree(cut.copySelf(),
+                                         plus.copySelf(), split.plus, attribute);
+                split.plus.condense();
+                split.plus.parent = split;
+            } else {
+                split.minus = new BSPTree(cut.copySelf(),
+                                          plus.copySelf(), split.minus, attribute);
+                split.minus.condense();
+                split.minus.parent = split;
+            }
+            return split;
+        }
+        case BOTH :
+        {
+            final Hyperplane.SplitSubHyperplane cutParts = sHyperplane.split(cut);
+            final Hyperplane.SplitSubHyperplane subParts = cHyperplane.split(sub);
+            final BSPTree split = new BSPTree(sub,
+                                              plus.split(subParts.getPlus()),
+                                              minus.split(subParts.getMinus()),
+                                              null);
+            split.plus.cut          = cutParts.getPlus();
+            split.minus.cut         = cutParts.getMinus();
+            final BSPTree tmp       = split.plus.minus;
+            split.plus.minus        = split.minus.plus;
+            split.plus.minus.parent = split.plus;
+            split.minus.plus        = tmp;
+            split.minus.plus.parent = split.minus;
+            split.plus.condense();
+            split.minus.condense();
+            return split;
+        }
+        default :
+            return cHyperplane.sameOrientationAs(sHyperplane) ?
+                    new BSPTree(sub, plus.copySelf(), minus.copySelf(), attribute) :
+                        new BSPTree(sub, minus.copySelf(), plus.copySelf(), attribute);
+        }
+
+    }
+
+    /** Insert the instance into another tree.
+     * <p>The instance itself is modified so its former parent should
+     * not be used anymore.</p>
+     * @param parentTree parent tree to connect to (may be null)
+     * @param isPlusChild if true and if parentTree is not null, the
+     * resulting tree should be the plus child of its parent, ignored if
+     * parentTree is null
+     * @see LeafMerger
+     */
+    public void insertInTree(final BSPTree parentTree, final boolean isPlusChild) {
+
+        // set up parent/child links
+        parent = parentTree;
+        if (parentTree != null) {
+            if (isPlusChild) {
+                parentTree.plus = this;
+            } else {
+                parentTree.minus = this;
+            }
+        }
+
+        // make sure the inserted tree lies in the cell defined by its parent nodes
+        if (cut != null) {
+
+            // explore the parent nodes from here towards tree root
+            for (BSPTree tree = this; tree.parent != null; tree = tree.parent) {
+
+                // this is an hyperplane of some parent node
+                final Hyperplane hyperplane = tree.parent.cut.getHyperplane();
+
+                // chop off the parts of the inserted tree that extend
+                // on the wrong side of this parent hyperplane
+                if (tree == tree.parent.plus) {
+                    cut = hyperplane.split(cut).getPlus();
+                    plus.chopOffMinus(hyperplane);
+                    minus.chopOffMinus(hyperplane);
+                } else {
+                    cut = hyperplane.split(cut).getMinus();
+                    plus.chopOffPlus(hyperplane);
+                    minus.chopOffPlus(hyperplane);
+                }
+
+            }
+
+            // since we may have drop some parts of the inserted tree,
+            // perform a condensation pass to keep the tree structure simple
+            condense();
+
+        }
+
+    }
+
+    /** Chop off parts of the tree.
+     * <p>The instance is modified in place, all the parts that are on
+     * the minus side of the chopping hyperplane are disgarded, only the
+     * parts on the plus side remain.</p>
+     * @param hyperplane chopping hyperplane
+     */
+    private void chopOffMinus(final Hyperplane hyperplane) {
+        if (cut != null) {
+            cut = hyperplane.split(cut).getPlus();
+            plus.chopOffMinus(hyperplane);
+            minus.chopOffMinus(hyperplane);
+        }
+    }
+
+    /** Chop off parts of the tree.
+     * <p>The instance is modified in place, all the parts that are on
+     * the plus side of the chopping hyperplane are disgarded, only the
+     * parts on the minus side remain.</p>
+     * @param hyperplane chopping hyperplane
+     */
+    private void chopOffPlus(final Hyperplane hyperplane) {
+        if (cut != null) {
+            cut = hyperplane.split(cut).getMinus();
+            plus.chopOffPlus(hyperplane);
+            minus.chopOffPlus(hyperplane);
+        }
+    }
+
+}

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTree.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/partitioning/BSPTree.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision



Mime
View raw message