You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2011/02/02 23:21:07 UTC
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...
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 <op>
+ * 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 <op>
+ * 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