commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r1066664 [2/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/threeD/Line.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Line.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Line.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Line.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,154 @@
+/*
+ * 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.threeD;
+
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.partitioning.Point;
+import org.apache.commons.bsp.partitioning.SubSpace;
+import org.apache.commons.math.geometry.Vector3D;
+import org.apache.commons.math.util.FastMath;
+
+/** The class represent lines in a three dimensional space.
+
+ * <p>Each oriented line is intrinsically associated with an abscissa
+ * wich is a coordinate on the line. The point at abscissa 0 is the
+ * orthogonal projection of the origin on the line, another equivalent
+ * way to express this is to say that it is the point of the line
+ * which is closest to the origin. Abscissa increases in the line
+ * direction.</p>
+
+ * @version $Revision$ $Date$
+ */
+public class Line implements SubSpace {
+
+    /** Line direction. */
+    private Vector3D direction;
+
+    /** Line point closest to the origin. */
+    private Point3D zero;
+
+    /** Build a line from a point and a direction.
+     * @param p point belonging to the line (this can be any point)
+     * @param direction direction of the line
+     * @exception IllegalArgumentException if the direction norm is too small
+     */
+    public Line(final Vector3D p, final Vector3D direction) {
+        reset(p, direction);
+    }
+
+    /** Reset the instance as if built from a point and a normal.
+     * @param p point belonging to the line (this can be any point)
+     * @param dir direction of the line
+     * @exception IllegalArgumentException if the direction norm is too small
+     */
+    public void reset(final Vector3D p, final Vector3D dir) {
+        final double norm = dir.getNorm();
+        if (norm == 0.0) {
+            throw new IllegalArgumentException("null norm");
+        }
+        this.direction = new Vector3D(1.0 / norm, dir);
+        zero = new Point3D(1.0, p, -Vector3D.dotProduct(p, this.direction), this.direction);
+    }
+
+    /** Revert the line direction.
+     */
+    public void revertSelf() {
+        direction = direction.negate();
+    }
+
+    /** Get the normalized direction vector.
+     * @return normalized direction vector
+     */
+    public Vector3D getDirection() {
+        return direction;
+    }
+
+    /** Get the abscissa of a point with respect to the line.
+     * <p>The abscissa is 0 if the projection of the point and the
+     * projection of the frame origin on the line are the same
+     * point.</p>
+     * @param point point to check (must be a {@link Vector3D Vector3D}
+     * instance)
+     * @return abscissa of the point (really a
+     * {org.apache.commons.bsp.euclidean.oneD.Point1D Point1D} instance)
+     */
+    public Point toSubSpace(final Point point) {
+        final double x = Vector3D.dotProduct(((Vector3D) point).subtract(zero), direction);
+        return new Point1D(x);
+    }
+
+    /** Get one point from the line.
+     * @param point desired abscissa for the point (must be a
+     * {org.apache.commons.bsp.euclidean.oneD.Point1D Point1D} instance)
+     * @return one point belonging to the line, at specified abscissa
+     * (really a {@link Vector3D Vector3D} instance)
+     */
+    public Point toSpace(final Point point) {
+        return new Point3D(1.0, zero, ((Point1D) point).getAbscissa(), direction);
+    }
+
+    /** Check if the instance is similar to another line.
+     * <p>Lines are considered similar if they contain the same
+     * points. This does not mean they are equal since they can have
+     * opposite directions.</p>
+     * @param line line to which instance should be compared
+     * @return true if the lines are similar
+     */
+    public boolean isSimilarTo(final Line line) {
+        final double angle = Vector3D.angle(direction, line.direction);
+        return ((angle < 1.0e-10) || (angle > (FastMath.PI - 1.0e-10))) && contains(line.zero);
+    }
+
+    /** Check if the instance contains a point.
+     * @param p point to check
+     * @return true if p belongs to the line
+     */
+    public boolean contains(final Vector3D p) {
+        return distance(p) < 1.0e-10;
+    }
+
+    /** Compute the distance between the instance and a point.
+     * @param p to check
+     * @return distance between the instance and the point
+     */
+    public double distance(final Vector3D p) {
+        final Vector3D d = p.subtract(zero);
+        final Vector3D n = new Vector3D(1.0, d, -Vector3D.dotProduct(d, direction), direction);
+        return n.getNorm();
+    }
+
+    /** Compute the shortest distance between the instance and another line.
+     * @param line line to check agains the instance
+     * @return shortest distance between the instance and the line
+     */
+    public double distance(final Line line) {
+
+        final Vector3D normal = Vector3D.crossProduct(direction, line.direction);
+        if (normal.getNorm() < 1.0e-10) {
+            // lines are parallel
+            return distance(line.zero);
+        }
+
+        // separating middle plane
+        final Plane middle = new Plane(new Vector3D(0.5, zero, 0.5, line.zero), normal);
+
+        // the lines are at the same distance on either side of the plane
+        return 2 * FastMath.abs(middle.getOffset(zero));
+
+    }
+
+}

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

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

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/OutlineExtractor.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/OutlineExtractor.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/OutlineExtractor.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/OutlineExtractor.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,249 @@
+/*
+ * 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.threeD;
+
+import org.apache.commons.bsp.euclidean.twoD.Line;
+import org.apache.commons.bsp.euclidean.twoD.Point2D;
+import org.apache.commons.bsp.euclidean.twoD.PolygonsSet;
+import org.apache.commons.bsp.partitioning.BSPTree;
+import org.apache.commons.bsp.partitioning.BSPTreeVisitor;
+import org.apache.commons.bsp.partitioning.Region;
+import org.apache.commons.bsp.partitioning.SubHyperplane;
+import org.apache.commons.math.geometry.Vector3D;
+import org.apache.commons.math.util.FastMath;
+
+import java.util.ArrayList;
+
+/** Extractor for {@link PolygonsSet polyhedrons sets} outlines.
+ * <p>This class extracts the 2D outlines from {{@link PolygonsSet
+ * polyhedrons sets} in a specified projection plane.</p>
+ * @version $Revision$ $Date$
+ */
+public class OutlineExtractor {
+
+    /** Abscissa axis of the projection plane. */
+    private Vector3D u;
+
+    /** Ordinate axis of the projection plane. */
+    private Vector3D v;
+
+    /** Normal of the projection plane (viewing direction). */
+    private Vector3D w;
+
+    /** Build an extractor for a specific projection plane.
+     * @param u abscissa axis of the projection point
+     * @param v ordinate axis of the projection point
+     */
+    public OutlineExtractor(final Vector3D u, final Vector3D v) {
+        this.u = u;
+        this.v = v;
+        w = Vector3D.crossProduct(u, v);
+    }
+
+    /** Extract the outline of a polyhedrons set.
+     * @param polyhedronsSet polyhedrons set whose outline must be extracted
+     * @return an outline, as an array of loops.
+     */
+    public Point2D[][] getOutline(final PolyhedronsSet polyhedronsSet) {
+
+        // project all boundary facets into one polygons set
+        final BoundaryProjector projector = new BoundaryProjector();
+        polyhedronsSet.getTree(true).visit(projector);
+        final PolygonsSet projected = projector.getProjected();
+
+        // Remove the spurious intermediate vertices from the outline
+        final Point2D[][] outline = projected.getVertices();
+        for (int i = 0; i < outline.length; ++i) {
+            final Point2D[] rawLoop = outline[i];
+            int end = rawLoop.length;
+            int j = 0;
+            while (j < end) {
+                if (pointIsBetween(rawLoop, end, j)) {
+                    // the point should be removed
+                    for (int k = j; k < (end - 1); ++k) {
+                        rawLoop[k] = rawLoop[k + 1];
+                    }
+                    --end;
+                } else {
+                    // the point remains in the loop
+                    ++j;
+                }
+            }
+            if (end != rawLoop.length) {
+                // resize the array
+                outline[i] = new Point2D[end];
+                System.arraycopy(rawLoop, 0, outline[i], 0, end);
+            }
+        }
+
+        return outline;
+
+    }
+
+    /** Check if a point is geometrically between its neighbour in an array.
+     * <p>The neighbours are computed considering the array is a loop
+     * (i.e. point at index (n-1) is before point at index 0)</p>
+     * @param loop points array
+     * @param n number of points to consider in the array
+     * @param i index of the point to check (must be between 0 and n-1)
+     * @return true if the point is exactly between its neighbours
+     */
+    private boolean pointIsBetween(final Point2D[] loop, final int n, final int i) {
+        final Point2D previous = loop[(i + n - 1) % n];
+        final Point2D current  = loop[i];
+        final Point2D next     = loop[(i + 1) % n];
+        final double dx1       = current.x - previous.x;
+        final double dy1       = current.y - previous.y;
+        final double dx2       = next.x    - current.x;
+        final double dy2       = next.y    - current.y;
+        final double cross     = dx1 * dy2 - dx2 * dy1;
+        final double dot       = dx1 * dx2 + dy1 * dy2;
+        final double d1d2      = FastMath.sqrt((dx1 * dx1 + dy1 * dy1) * (dx2 * dx2 + dy2 * dy2));
+        return (FastMath.abs(cross) <= (1.0e-6 * d1d2)) && (dot >= 0.0);
+    }
+
+    /** Visitor projecting the boundary facets on a plane. */
+    private class BoundaryProjector implements BSPTreeVisitor {
+
+        /** Projection of the polyhedrons set on the plane. */
+        private PolygonsSet projected;
+
+        /** Simple constructor.
+         */
+        public BoundaryProjector() {
+            projected = new PolygonsSet(new BSPTree(Boolean.FALSE));
+        }
+
+        /** {@inheritDoc} */
+        public Order visitOrder(final BSPTree node) {
+            return Order.MINUS_SUB_PLUS;
+        }
+
+        /** {@inheritDoc} */
+        public void visitInternalNode(final BSPTree node) {
+            final Region.BoundaryAttribute attribute =
+                (Region.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 facet boundary facet
+         * @param reversed if true, the facet has the inside on its plus side
+         */
+        private void addContribution(final SubHyperplane facet, final boolean reversed) {
+
+            // extract the vertices of the facet
+            final Plane plane    = (Plane) facet.getHyperplane();
+            Point2D[][] vertices =
+                ((PolygonsSet) facet.getRemainingRegion()).getVertices();
+
+            final double scal = Vector3D.dotProduct(plane.getNormal(), w);
+            if (FastMath.abs(scal) > 1.0e-3) {
+
+                if ((scal < 0) ^ reversed) {
+                    // the facet is seen from the inside,
+                    // we need to invert its boundary orientation
+                    final Point2D[][] newVertices = new Point2D[vertices.length][];
+                    for (int i = 0; i < vertices.length; ++i) {
+                        final Point2D[] loop = vertices[i];
+                        final Point2D[] newLoop = new Point2D[loop.length];
+                        if (loop[0] == null) {
+                            newLoop[0] = null;
+                            for (int j = 1; j < loop.length; ++j) {
+                                newLoop[j] = loop[loop.length - j];
+                            }
+                        } else {
+                            for (int j = 0; j < loop.length; ++j) {
+                                newLoop[j] = loop[loop.length - (j + 1)];
+                            }
+                        }
+                        newVertices[i] = newLoop;
+                    }
+
+                    // use the reverted vertices
+                    vertices = newVertices;
+
+                }
+
+                // compute the projection of the facet in the outline plane
+                final ArrayList<SubHyperplane> edges = new ArrayList<SubHyperplane>();
+                for (Point2D[] loop : vertices) {
+                    final boolean closed = loop[0] != null;
+                    int previous         = closed ? (loop.length - 1) : 1;
+                    Vector3D previous3D  = (Vector3D) plane.toSpace(loop[previous]);
+                    int current          = (previous + 1) % loop.length;
+                    Point2D pPoint       = new Point2D(Vector3D.dotProduct(previous3D, u),
+                                                       Vector3D.dotProduct(previous3D, v));
+                    while (current < loop.length) {
+
+                        final Vector3D current3D = (Vector3D) plane.toSpace(loop[current]);
+                        final Point2D  cPoint    = new Point2D(Vector3D.dotProduct(current3D, u),
+                                                               Vector3D.dotProduct(current3D, v));
+                        final Line line          = new Line(pPoint, cPoint);
+                        SubHyperplane edge = new SubHyperplane(line);
+
+                        if (closed || (previous != 1)) {
+                            // the previous point is a real vertex
+                            // it defines one bounding point of the edge
+                            final double angle = line.getAngle() + 0.5 * FastMath.PI;
+                            final Line l = new Line(pPoint, angle);
+                            edge = l.split(edge).getPlus();
+                        }
+
+                        if (closed || (current != (loop.length - 1))) {
+                            // the current point is a real vertex
+                            // it defines one bounding point of the edge
+                            final double angle = line.getAngle() + 0.5 * FastMath.PI;
+                            final Line l = new Line(cPoint, angle);
+                            edge = l.split(edge).getMinus();
+                        }
+
+                        edges.add(edge);
+
+                        previous   = current++;
+                        previous3D = current3D;
+                        pPoint     = cPoint;
+
+                    }
+                }
+                final PolygonsSet projectedFacet = new PolygonsSet(edges);
+
+                // add the contribution of the facet to the global outline
+                projected = (PolygonsSet) Region.union(projected, projectedFacet);
+
+            }
+        }
+
+        /** Get the projecion of the polyhedrons set on the plane.
+         * @return projecion of the polyhedrons set on the plane
+         */
+        public PolygonsSet getProjected() {
+            return projected;
+        }
+
+    }
+
+}

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

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

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Plane.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Plane.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Plane.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Plane.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,528 @@
+/*
+ * 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.threeD;
+
+import org.apache.commons.bsp.euclidean.oneD.Point1D;
+import org.apache.commons.bsp.euclidean.twoD.Point2D;
+import org.apache.commons.bsp.euclidean.twoD.PolygonsSet;
+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.math.geometry.Rotation;
+import org.apache.commons.math.geometry.Vector3D;
+import org.apache.commons.math.util.FastMath;
+
+/** The class represent planes in a three dimensional space.
+ * @version $Revision$ $Date$
+ */
+public class Plane implements Hyperplane {
+
+    /** Offset of the origin with respect to the plane. */
+    private double originOffset;
+
+    /** Origin of the plane frame. */
+    private Point3D origin;
+
+    /** First vector of the plane frame (in plane). */
+    private Vector3D u;
+
+    /** Second vector of the plane frame (in plane). */
+    private Vector3D v;
+
+    /** Third vector of the plane frame (plane normal). */
+    private Vector3D w;
+
+    /** Build a plane normal to a given direction and containing the origin.
+     * @param normal normal direction to the plane
+     * @exception IllegalArgumentException if the normal norm is too small
+     */
+    public Plane(final Vector3D normal) {
+        setNormal(normal);
+        originOffset = 0;
+        setFrame();
+    }
+
+    /** Build a plane from a point and a normal.
+     * @param p point belonging to the plane
+     * @param normal normal direction to the plane
+     * @exception IllegalArgumentException if the normal norm is too small
+     */
+    public Plane(final Vector3D p, final Vector3D normal) {
+        setNormal(normal);
+        originOffset = -Vector3D.dotProduct(p, w);
+        setFrame();
+    }
+
+    /** Build a plane from three points.
+     * <p>The plane is oriented in the direction of
+     * {@code (p2-p1) ^ (p3-p1)}</p>
+     * @param p1 first point belonging to the plane
+     * @param p2 second point belonging to the plane
+     * @param p3 third point belonging to the plane
+     * @exception IllegalArgumentException if the points do not constitute a plane
+     */
+    public Plane(final Vector3D p1, final Vector3D p2, final Vector3D p3) {
+        this(p1, Vector3D.crossProduct(p2.subtract(p1), p3.subtract(p1)));
+    }
+
+    /** Copy constructor.
+     * <p>The instance created is completely independant of the original
+     * one. A deep copy is used, none of the underlying object are
+     * shared.</p>
+     * @param plane plane to copy
+     */
+    public Plane(final Plane plane) {
+        originOffset = plane.originOffset;
+        origin = plane.origin;
+        u      = plane.u;
+        v      = plane.v;
+        w      = plane.w;
+    }
+
+    /** 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 immutable objects).</p>
+     * @return a new hyperplane, copy of the instance
+     */
+    public Hyperplane copySelf() {
+        return new Plane(this);
+    }
+
+    /** Reset the instance as if built from a point and a normal.
+     * @param p point belonging to the plane
+     * @param normal normal direction to the plane
+     */
+    public void reset(final Vector3D p, final Vector3D normal) {
+        setNormal(normal);
+        originOffset = -Vector3D.dotProduct(p, w);
+        setFrame();
+    }
+
+    /** Reset the instance from another one.
+     * <p>The updated instance is completely independant of the original
+     * one. A deep reset is used none of the underlying object is
+     * shared.</p>
+     * @param original plane to reset from
+     */
+    public void reset(final Plane original) {
+        originOffset = original.originOffset;
+        origin       = original.origin;
+        u            = original.u;
+        v            = original.v;
+        w            = original.w;
+    }
+
+    /** Set the normal vactor.
+     * @param normal normal direction to the plane (will be copied)
+     * @exception IllegalArgumentException if the normal norm is too small
+     */
+    private void setNormal(final Vector3D normal) {
+        final double norm = normal.getNorm();
+        if (norm < 1.0e-10) {
+            throw new IllegalArgumentException("null norm");
+        }
+        w = new Vector3D(1.0 / norm, normal);
+    }
+
+    /** Reset the plane frame.
+     */
+    private void setFrame() {
+        origin = new Point3D(-originOffset, w);
+        u = w.orthogonal();
+        v = Vector3D.crossProduct(w, u);
+    }
+
+    /** Get the origin point of the plane frame.
+     * <p>The point returned is the orthogonal projection of the
+     * 3D-space origin in the plane.</p>
+     * @return the origin point of the plane frame (point closest to the
+     * 3D-space origin)
+     */
+    public Point3D getOrigin() {
+        return origin;
+    }
+
+    /** Get the normalized normal vector.
+     * <p>The frame defined by ({@link #getU getU}, {@link #getV getV},
+     * {@link #getNormal getNormal}) is a rigth-handed orthonormalized
+     * frame).</p>
+     * @return normalized normal vector
+     * @see #getU
+     * @see #getV
+     */
+    public Vector3D getNormal() {
+        return w;
+    }
+
+    /** Get the plane first canonical vector.
+     * <p>The frame defined by ({@link #getU getU}, {@link #getV getV},
+     * {@link #getNormal getNormal}) is a rigth-handed orthonormalized
+     * frame).</p>
+     * @return normalized first canonical vector
+     * @see #getV
+     * @see #getNormal
+     */
+    public Vector3D getU() {
+        return u;
+    }
+
+    /** Get the plane second canonical vector.
+     * <p>The frame defined by ({@link #getU getU}, {@link #getV getV},
+     * {@link #getNormal getNormal}) is a rigth-handed orthonormalized
+     * frame).</p>
+     * @return normalized second canonical vector
+     * @see #getU
+     * @see #getNormal
+     */
+    public Vector3D getV() {
+        return v;
+    }
+
+    /** Revert the plane.
+     * <p>Replace the instance by a similar plane with opposite orientation.</p>
+     * <p>The new plane frame is chosen in such a way that a 3D point that had
+     * {@code (x, y)} in-plane coordinates and {@code z} offset with
+     * respect to the plane and is unaffected by the change will have
+     * {@code (y, x)} in-plane coordinates and {@code -z} offset with
+     * respect to the new plane. This means that the {@code u} and {@code v}
+     * vectors returned by the {@link #getU} and {@link #getV} methods are exchanged,
+     * and the {@code w} vector returned by the {@link #getNormal} method is
+     * reversed.</p>
+     */
+    public void revertSelf() {
+        final Vector3D tmp = u;
+        u = v;
+        v = tmp;
+        w = w.negate();
+        originOffset = -originOffset;
+    }
+
+    /** Transform a 3D space point into an in-plane point.
+     * @param point point of the space (must be a {@link Vector3D
+     * Vector3D} instance)
+     * @return in-plane point (really a {@link
+     * org.apache.commons.bsp.euclidean.twoD.Point2D Point2D} instance)
+     * @see #toSpace
+     */
+    public Point toSubSpace(final Point point) {
+        final Vector3D p3D = (Vector3D) point;
+        return new Point2D(Vector3D.dotProduct(p3D, u),
+                           Vector3D.dotProduct(p3D, v));
+    }
+
+    /** Transform an in-plane point into a 3D space point.
+     * @param point in-plane point (must be a {@link
+     * org.apache.commons.bsp.euclidean.twoD.Point2D Point2D} instance)
+     * @return 3D space point (really a {@link Vector3D Vector3D} instance)
+     * @see #toSubSpace
+     */
+    public Point toSpace(final Point point) {
+        final Point2D p2D = (Point2D) point;
+        return new Point3D(p2D.x, u, p2D.y, v, -originOffset, w);
+    }
+
+    /** Get one point from the 3D-space.
+     * @param inPlane desired in-plane coordinates for the point in the
+     * plane
+     * @param offset desired offset for the point
+     * @return one point in the 3D-space, with given coordinates and offset
+     * relative to the plane
+     */
+    public Vector3D getPointAt(final Point2D inPlane, final double offset) {
+        return new Vector3D(inPlane.x, u, inPlane.y, v, offset - originOffset, w);
+    }
+
+    /** Check if the instance is similar to another plane.
+     * <p>Planes are considered similar if they contain the same
+     * points. This does not mean they are equal since they can have
+     * opposite normals.</p>
+     * @param plane plane to which the instance is compared
+     * @return true if the planes are similar
+     */
+    public boolean isSimilarTo(final Plane plane) {
+        final double angle = Vector3D.angle(w, plane.w);
+        return ((angle < 1.0e-10) && (FastMath.abs(originOffset - plane.originOffset) < 1.0e-10)) ||
+               ((angle > (FastMath.PI - 1.0e-10)) && (FastMath.abs(originOffset + plane.originOffset) < 1.0e-10));
+    }
+
+    /** Rotate the plane around the specified point.
+     * <p>The instance is not modified, a new instance is created.</p>
+     * @param center rotation center
+     * @param rotation vectorial rotation operator
+     * @return a new plane
+     */
+    public Plane rotate(final Vector3D center, final Rotation rotation) {
+
+        final Vector3D delta = origin.subtract(center);
+        final Plane plane = new Plane(center.add(rotation.applyTo(delta)),
+                                rotation.applyTo(w));
+
+        // make sure the frame is transformed as desired
+        plane.u = rotation.applyTo(u);
+        plane.v = rotation.applyTo(v);
+
+        return plane;
+
+    }
+
+    /** Translate the plane by the specified amount.
+     * <p>The instance is not modified, a new instance is created.</p>
+     * @param translation translation to apply
+     * @return a new plane
+     */
+    public Plane translate(final Vector3D translation) {
+
+        final Plane plane = new Plane(origin.add(translation), w);
+
+        // make sure the frame is transformed as desired
+        plane.u = u;
+        plane.v = v;
+
+        return plane;
+
+    }
+
+    /** Get the intersection of a line with the instance.
+     * @param line line intersecting the instance
+     * @return intersection point between between the line and the
+     * instance (null if the line is parallel to the instance)
+     */
+    public Point3D intersection(final Line line) {
+        final Vector3D direction = line.getDirection();
+        final double   dot       = Vector3D.dotProduct(w, direction);
+        if (FastMath.abs(dot) < 1.0e-10) {
+            return null;
+        }
+        final Vector3D point = (Vector3D) line.toSpace(Point1D.ZERO);
+        final double   k     = -(originOffset + Vector3D.dotProduct(w, point)) / dot;
+        return new Point3D(1.0, point, k, direction);
+    }
+
+    /** Build the line shared by the instance and another plane.
+     * @param other other plane
+     * @return line at the intersection of the instance and the
+     * other plane (really a {@link Line Line} instance)
+     */
+    public SubSpace intersection(final Hyperplane other) {
+        final Plane otherP = (Plane) other;
+        final Vector3D direction = Vector3D.crossProduct(w, otherP.w);
+        if (direction.getNorm() < 1.0e-10) {
+            return null;
+        }
+        return new Line(intersection(this, otherP, new Plane(direction)),
+                        direction);
+    }
+
+    /** Get the intersection point of three planes.
+     * @param plane1 first plane1
+     * @param plane2 second plane2
+     * @param plane3 third plane2
+     * @return intersection point of three planes, null if some planes are parallel
+     */
+    public static Vector3D intersection(final Plane plane1, final Plane plane2, final Plane plane3) {
+
+        // coefficients of the three planes linear equations
+        final double a1 = plane1.w.getX();
+        final double b1 = plane1.w.getY();
+        final double c1 = plane1.w.getZ();
+        final double d1 = plane1.originOffset;
+
+        final double a2 = plane2.w.getX();
+        final double b2 = plane2.w.getY();
+        final double c2 = plane2.w.getZ();
+        final double d2 = plane2.originOffset;
+
+        final double a3 = plane3.w.getX();
+        final double b3 = plane3.w.getY();
+        final double c3 = plane3.w.getZ();
+        final double d3 = plane3.originOffset;
+
+        // direct Cramer resolution of the linear system
+        // (this is still feasible for a 3x3 system)
+        final double a23         = b2 * c3 - b3 * c2;
+        final double b23         = c2 * a3 - c3 * a2;
+        final double c23         = a2 * b3 - a3 * b2;
+        final double determinant = a1 * a23 + b1 * b23 + c1 * c23;
+        if (FastMath.abs(determinant) < 1.0e-10) {
+            return null;
+        }
+
+        final double r = 1.0 / determinant;
+        return new Vector3D(
+                            (-a23 * d1 - (c1 * b3 - c3 * b1) * d2 - (c2 * b1 - c1 * b2) * d3) * r,
+                            (-b23 * d1 - (c3 * a1 - c1 * a3) * d2 - (c1 * a2 - c2 * a1) * d3) * r,
+                            (-c23 * d1 - (b1 * a3 - b3 * a1) * d2 - (b2 * a1 - b1 * a2) * d3) * r);
+
+    }
+
+    /** Build a region covering the whole hyperplane.
+     * @return a region covering the whole hyperplane
+     */
+    public Region wholeHyperplane() {
+        return new PolygonsSet();
+    }
+
+    /** Build a region covering the whole space.
+     * @return a region containing the instance (really a {@link
+     * PolyhedronsSet PolyhedronsSet} instance)
+     */
+    public Region wholeSpace() {
+        return new PolyhedronsSet();
+    }
+
+    /** Check if the instance contains a point.
+     * @param p point to check
+     * @return true if p belongs to the plane
+     */
+    public boolean contains(final Point3D p) {
+        return FastMath.abs(getOffset(p)) < 1.0e-10;
+    }
+
+    /** Get the offset (oriented distance) of a parallel plane.
+     * <p>This method should be called only for parallel planes otherwise
+     * the result is not meaningful.</p>
+     * <p>The offset is 0 if both planes are the same, it is
+     * positive if the plane is on the plus side of the instance and
+     * negative if it is on the minus side, according to its natural
+     * orientation.</p>
+     * @param plane plane to check
+     * @return offset of the plane
+     */
+    public double getOffset(final Plane plane) {
+        return originOffset + (sameOrientationAs(plane) ? -plane.originOffset : plane.originOffset);
+    }
+
+    /** Get the offset (oriented distance) of a point.
+     * <p>The offset is 0 if the point is on the underlying hyperplane,
+     * it is positive if the point is on one particular side of the
+     * hyperplane, and it is negative if the point is on the other side,
+     * according to the hyperplane natural orientation.</p>
+     * @param point point to check
+     * @return offset of the point
+     */
+    public double getOffset(final Point point) {
+        return Vector3D.dotProduct((Vector3D) point, w) + originOffset;
+    }
+
+    /** Check if the instance has the same orientation as another hyperplane.
+     * @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) {
+        return Vector3D.dotProduct(((Plane) other).w, w) > 0.0;
+    }
+
+    /** 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 Plane otherPlane = (Plane) sub.getHyperplane();
+        final Line  inter      = (Line) intersection(otherPlane);
+
+        if (inter == null) {
+            // the hyperplanes are parallel,
+            // any point can be used to check their relative position
+            final double global = getOffset(otherPlane);
+            return (global < -1.0e-10) ? Side.MINUS : ((global > 1.0e-10) ? Side.PLUS : Side.HYPER);
+        }
+
+        // create a 2D line in the otherPlane canonical 2D frame such that:
+        //   - the line is the crossing line of the two planes in 3D
+        //   - the line splits the otherPlane in two half planes with an
+        //     orientation consistent with the orientation of the instance
+        //     (i.e. the 3D half space on the plus side (resp. minus side)
+        //      of the instance contains the 2D half plane on the plus side
+        //      (resp. minus side) of the 2D line
+        Point2D p = (Point2D) otherPlane.toSubSpace(inter.toSpace(Point1D.ZERO));
+        Point2D q = (Point2D) otherPlane.toSubSpace(inter.toSpace(Point1D.ONE));
+        if (Vector3D.dotProduct(Vector3D.crossProduct(inter.getDirection(),
+                                                      otherPlane.getNormal()),
+                                                      w) < 0) {
+            final Point2D tmp = p;
+            p           = q;
+            q           = tmp;
+        }
+        final Hyperplane line2D = new org.apache.commons.bsp.euclidean.twoD.Line(p, q);
+
+        // check the side on the 2D plane
+        return sub.getRemainingRegion().side(line2D);
+
+    }
+
+    /** 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 Plane otherPlane = (Plane) sub.getHyperplane();
+        final Line  inter      = (Line) intersection(otherPlane);
+
+        if (inter == null) {
+            // the hyperplanes are parallel
+            final double global = getOffset(otherPlane);
+            return (global < -1.0e-10) ? new SplitSubHyperplane(null, sub) : new SplitSubHyperplane(sub, null);
+        }
+
+        // the hyperplanes do intersect
+        Point2D p = (Point2D) otherPlane.toSubSpace(inter.toSpace(Point1D.ZERO));
+        Point2D q = (Point2D) otherPlane.toSubSpace(inter.toSpace(Point1D.ONE));
+        if (Vector3D.dotProduct(Vector3D.crossProduct(inter.getDirection(),
+                                                      otherPlane.getNormal()),
+                                                      w) < 0) {
+            final Point2D tmp = p;
+            p           = q;
+            q           = tmp;
+        }
+        final SubHyperplane l2DMinus =
+            new SubHyperplane(new org.apache.commons.bsp.euclidean.twoD.Line(p, q));
+        final SubHyperplane l2DPlus =
+            new SubHyperplane(new org.apache.commons.bsp.euclidean.twoD.Line(q, p));
+
+        final BSPTree splitTree =
+            sub.getRemainingRegion().getTree(false).split(l2DMinus);
+        final BSPTree plusTree  = Region.isEmpty(splitTree.getPlus()) ?
+                                  new BSPTree(Boolean.FALSE) :
+                                  new BSPTree(l2DPlus, new BSPTree(Boolean.FALSE),
+                                              splitTree.getPlus(), null);
+
+        final BSPTree minusTree = Region.isEmpty(splitTree.getMinus()) ?
+                                  new BSPTree(Boolean.FALSE) :
+                                  new BSPTree(l2DMinus, new BSPTree(Boolean.FALSE),
+                                              splitTree.getMinus(), null);
+
+        return new SplitSubHyperplane(new SubHyperplane(otherPlane.copySelf(),
+                                                        new PolygonsSet(plusTree)),
+                                                        new SubHyperplane(otherPlane.copySelf(),
+                                                                          new PolygonsSet(minusTree)));
+
+    }
+
+}

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

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

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Point3D.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Point3D.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Point3D.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/Point3D.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,113 @@
+/*
+ * 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.threeD;
+
+import org.apache.commons.bsp.partitioning.Point;
+import org.apache.commons.math.geometry.Vector3D;
+
+/** This class represents a 3D point.
+ * <p>Instances of this class are guaranteed to be immutable.</p>
+ * @version $Revision$ $Date$
+ */
+public class Point3D extends Vector3D implements Point {
+
+    /** Point at undefined (NaN) coordinates. */
+    public static final Point3D UNDEFINED = new Point3D(Double.NaN, Double.NaN, Double.NaN);
+
+    /** Serializable UID. */
+    private static final long serialVersionUID = 9128130934224884451L;
+
+    /** Simple constructor.
+     * Build a vector from its coordinates
+     * @param x abscissa
+     * @param y ordinate
+     * @param z height
+     * @see #getX()
+     * @see #getY()
+     * @see #getZ()
+     */
+    public Point3D(final double x, final double y, final double z) {
+        super(x, y, z);
+    }
+
+    /** Simple constructor.
+     * Build a vector from its azimuthal coordinates
+     * @param alpha azimuth (&alpha;) around Z
+     *              (0 is +X, &pi;/2 is +Y, &pi; is -X and 3&pi;/2 is -Y)
+     * @param delta elevation (&delta;) above (XY) plane, from -&pi;/2 to +&pi;/2
+     * @see #getAlpha()
+     * @see #getDelta()
+     */
+    public Point3D(final double alpha, final double delta) {
+        super(alpha, delta);
+    }
+
+    /** Multiplicative constructor
+     * Build a vector from another one and a scale factor.
+     * The vector built will be a * u
+     * @param a scale factor
+     * @param u base (unscaled) vector
+     */
+    public Point3D(final double a, final Vector3D u) {
+        super(a, u);
+    }
+
+    /** Linear constructor
+     * Build a vector from two other ones and corresponding scale factors.
+     * The vector built will be a1 * u1 + a2 * u2
+     * @param a1 first scale factor
+     * @param u1 first base (unscaled) vector
+     * @param a2 second scale factor
+     * @param u2 second base (unscaled) vector
+     */
+    public Point3D(final double a1, final Vector3D u1, final double a2, final Vector3D u2) {
+        super(a1, u1, a2, u2);
+    }
+
+    /** Linear constructor
+     * Build a vector from three other ones and corresponding scale factors.
+     * The vector built will be a1 * u1 + a2 * u2 + a3 * u3
+     * @param a1 first scale factor
+     * @param u1 first base (unscaled) vector
+     * @param a2 second scale factor
+     * @param u2 second base (unscaled) vector
+     * @param a3 third scale factor
+     * @param u3 third base (unscaled) vector
+     */
+    public Point3D(final double a1, final Vector3D u1, final double a2, final Vector3D u2,
+                   final double a3, final Vector3D u3) {
+        super(a1, u1, a2, u2, a3, u3);
+    }
+
+    /** Linear constructor
+     * Build a vector from four other ones and corresponding scale factors.
+     * The vector built will be a1 * u1 + a2 * u2 + a3 * u3 + a4 * u4
+     * @param a1 first scale factor
+     * @param u1 first base (unscaled) vector
+     * @param a2 second scale factor
+     * @param u2 second base (unscaled) vector
+     * @param a3 third scale factor
+     * @param u3 third base (unscaled) vector
+     * @param a4 fourth scale factor
+     * @param u4 fourth base (unscaled) vector
+     */
+    public Point3D(final double a1, final Vector3D u1, final double a2, final Vector3D u2,
+                   final double a3, final Vector3D u3, final double a4, final Vector3D u4) {
+        super(a1, u1, a2, u2, a3, u3, a4, u4);
+    }
+
+}

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

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

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSet.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSet.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSet.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/threeD/PolyhedronsSet.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,416 @@
+/*
+ * 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.threeD;
+
+import java.awt.geom.AffineTransform;
+import java.util.Arrays;
+import java.util.Collection;
+
+import org.apache.commons.bsp.euclidean.twoD.Point2D;
+import org.apache.commons.bsp.partitioning.BSPTree;
+import org.apache.commons.bsp.partitioning.BSPTreeVisitor;
+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.Transform;
+import org.apache.commons.math.geometry.Rotation;
+import org.apache.commons.math.geometry.Vector3D;
+import org.apache.commons.math.util.FastMath;
+
+/** This class represents a 3D region: a set of polyhedrons.
+ * @version $Revision$ $Date$
+ */
+public class PolyhedronsSet extends Region {
+
+    /** Build a polyhedrons set representing the whole real line.
+     */
+    public PolyhedronsSet() {
+        super();
+    }
+
+    /** Build a polyhedrons 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 PolyhedronsSet(final BSPTree tree) {
+        super(tree);
+    }
+
+    /** Build a polyhedrons 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 polyhedrons 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(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 PolyhedronsSet(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
+     * @param zMin low bound along the z direction
+     * @param zMax high bound along the z direction
+     */
+    public PolyhedronsSet(final double xMin, final double xMax,
+                          final double yMin, final double yMax,
+                          final double zMin, final double zMax) {
+        this(buildConvex(Arrays.asList(new Hyperplane[] {
+            new Plane(new Vector3D(xMin, 0,    0),   Vector3D.MINUS_I),
+            new Plane(new Vector3D(xMax, 0,    0),   Vector3D.PLUS_I),
+            new Plane(new Vector3D(0,    yMin, 0),   Vector3D.MINUS_J),
+            new Plane(new Vector3D(0,    yMax, 0),   Vector3D.PLUS_J),
+            new Plane(new Vector3D(0,    0,   zMin), Vector3D.MINUS_K),
+            new Plane(new Vector3D(0,    0,   zMax), Vector3D.PLUS_K)
+        })).getTree(false));
+    }
+
+    /** {@inheritDoc} */
+    public Region buildNew(final BSPTree tree) {
+        return new PolyhedronsSet(tree);
+    }
+
+    /** {@inheritDoc} */
+    protected void computeGeometricalProperties() {
+
+        // compute the contribution of all boundary facets
+        getTree(true).visit(new FacetsContributionVisitor());
+
+        if (getSize() < 0) {
+            // the polyhedrons set as a finite outside
+            // surrounded by an infinite inside
+            setSize(Double.POSITIVE_INFINITY);
+            setBarycenter(Point3D.UNDEFINED);
+        } else {
+            // the polyhedrons set is finite, apply the remaining scaling factors
+            setSize(getSize() / 3.0);
+            setBarycenter(new Point3D(1.0 / (4 * getSize()), (Vector3D) getBarycenter()));
+        }
+
+    }
+
+    /** Visitor computing geometrical properties. */
+    private class FacetsContributionVisitor implements BSPTreeVisitor {
+
+        /** Simple constructor. */
+        public FacetsContributionVisitor() {
+            setSize(0);
+            setBarycenter(new Point3D(0, 0, 0));
+        }
+
+        /** {@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 facet boundary facet
+         * @param reversed if true, the facet has the inside on its plus side
+         */
+        private void addContribution(final SubHyperplane facet, final boolean reversed) {
+
+            final Region polygon = facet.getRemainingRegion();
+            final double area    = polygon.getSize();
+
+            if (Double.isInfinite(area)) {
+                setSize(Double.POSITIVE_INFINITY);
+                setBarycenter(Point3D.UNDEFINED);
+            } else {
+
+                final Plane    plane  = (Plane) facet.getHyperplane();
+                final Vector3D facetB = (Point3D) plane.toSpace(polygon.getBarycenter());
+                double   scaled = area * Vector3D.dotProduct(facetB, plane.getNormal());
+                if (reversed) {
+                    scaled = -scaled;
+                }
+
+                setSize(getSize() + scaled);
+                setBarycenter(new Point3D(1.0, (Point3D) getBarycenter(), scaled, facetB));
+
+            }
+
+        }
+
+    }
+
+    /** Get the first sub-hyperplane crossed by a semi-infinite line.
+     * @param point start point of the part of the line considered
+     * @param line line to consider (contains point)
+     * @return the first sub-hyperplaned crossed by the line after the
+     * given point, or null if the line does not intersect any
+     * sub-hyperplaned
+     */
+    public SubHyperplane firstIntersection(final Vector3D point, final Line line) {
+        return recurseFirstIntersection(getTree(true), point, line);
+    }
+
+    /** Get the first sub-hyperplane crossed by a semi-infinite line.
+     * @param node current node
+     * @param point start point of the part of the line considered
+     * @param line line to consider (contains point)
+     * @return the first sub-hyperplaned crossed by the line after the
+     * given point, or null if the line does not intersect any
+     * sub-hyperplaned
+     */
+    private SubHyperplane recurseFirstIntersection(final BSPTree node,
+                                                   final Vector3D point,
+                                                   final Line line) {
+
+        final SubHyperplane cut = node.getCut();
+        if (cut == null) {
+            return null;
+        }
+        final BSPTree minus = node.getMinus();
+        final BSPTree plus  = node.getPlus();
+        final Plane   plane = (Plane) cut.getHyperplane();
+
+        // establish search order
+        final double offset = plane.getOffset((Point) point);
+        final boolean in    = FastMath.abs(offset) < 1.0e-10;
+        final BSPTree near;
+        final BSPTree far;
+        if (offset < 0) {
+            near = minus;
+            far  = plus;
+        } else {
+            near = plus;
+            far  = minus;
+        }
+
+        if (in) {
+            // search in the cut hyperplane
+            final SubHyperplane facet = boundaryFacet(point, node);
+            if (facet != null) {
+                return facet;
+            }
+        }
+
+        // search in the near branch
+        final SubHyperplane crossed = recurseFirstIntersection(near, point, line);
+        if (crossed != null) {
+            return crossed;
+        }
+
+        if (!in) {
+            // search in the cut hyperplane
+            final Vector3D hit3D = plane.intersection(line);
+            if (hit3D != null) {
+                final SubHyperplane facet = boundaryFacet(hit3D, node);
+                if (facet != null) {
+                    return facet;
+                }
+            }
+        }
+
+        // search in the far branch
+        return recurseFirstIntersection(far, point, line);
+
+    }
+
+    /** Check if a point belongs to the boundary part of a node.
+     * @param point point to check
+     * @param node node containing the boundary facet to check
+     * @return the boundary facet this points belongs to (or null if it
+     * does not belong to any boundary facet)
+     */
+    private SubHyperplane boundaryFacet(final Vector3D point, final BSPTree node) {
+        final Point point2D = node.getCut().getHyperplane().toSubSpace((Point) point);
+        final BoundaryAttribute attribute = (BoundaryAttribute) node.getAttribute();
+        if ((attribute.getPlusOutside() != null) &&
+            (attribute.getPlusOutside().getRemainingRegion().checkPoint(point2D) == Location.INSIDE)) {
+            return attribute.getPlusOutside();
+        }
+        if ((attribute.getPlusInside() != null) &&
+            (attribute.getPlusInside().getRemainingRegion().checkPoint(point2D) == Location.INSIDE)) {
+            return attribute.getPlusInside();
+        }
+        return null;
+    }
+
+    /** Rotate the region around the specified point.
+     * <p>The instance is not modified, a new instance is created.</p>
+     * @param center rotation center
+     * @param rotation vectorial rotation operator
+     * @return a new instance representing the rotated region
+     */
+    public PolyhedronsSet rotate(final Vector3D center, final Rotation rotation) {
+        return (PolyhedronsSet) applyTransform(new RotationTransform(center, rotation));
+    }
+
+    /** 3D rotation as a Transform. */
+    private static class RotationTransform implements Transform {
+
+        /** Center point of the rotation. */
+        private Vector3D   center;
+
+        /** Vectorial rotation. */
+        private Rotation   rotation;
+
+        /** Cached original hyperplane. */
+        private Hyperplane cachedOriginal;
+
+        /** Cached 2D transform valid inside the cached original hyperplane. */
+        private Transform  cachedTransform;
+
+        /** Build a rotation transform.
+         * @param center center point of the rotation
+         * @param rotation vectorial rotation
+         */
+        public RotationTransform(final Vector3D center, final Rotation rotation) {
+            this.center   = center;
+            this.rotation = rotation;
+        }
+
+        /** {@inheritDoc} */
+        public Point apply(final Point point) {
+            final Vector3D delta = ((Vector3D) point).subtract(center);
+            return new Point3D(1.0, center, 1.0, rotation.applyTo(delta));
+        }
+
+        /** {@inheritDoc} */
+        public Hyperplane apply(final Hyperplane hyperplane) {
+            return ((Plane) hyperplane).rotate(center, rotation);
+        }
+
+        /** {@inheritDoc} */
+        public SubHyperplane apply(final SubHyperplane sub,
+                                   final Hyperplane original, final Hyperplane transformed) {
+            if (original != cachedOriginal) {
+                // we have changed hyperplane, reset the in-hyperplane transform
+
+                final Plane    oPlane = (Plane) original;
+                final Plane    tPlane = (Plane) transformed;
+                final Vector3D p00    = oPlane.getOrigin();
+                final Vector3D p10    = (Vector3D) oPlane.toSpace(new Point2D(1.0, 0.0));
+                final Vector3D p01    = (Vector3D) oPlane.toSpace(new Point2D(0.0, 1.0));
+                final Point2D  tP00   = (Point2D) tPlane.toSubSpace(apply((Point) p00));
+                final Point2D  tP10   = (Point2D) tPlane.toSubSpace(apply((Point) p10));
+                final Point2D  tP01   = (Point2D) tPlane.toSubSpace(apply((Point) p01));
+                final AffineTransform at =
+                    new AffineTransform(tP10.getX() - tP00.getX(), tP10.getY() - tP00.getY(),
+                                        tP01.getX() - tP00.getX(), tP01.getY() - tP00.getY(),
+                                        tP00.getX(), tP00.getY());
+
+                cachedOriginal  = original;
+                cachedTransform =
+                    org.apache.commons.bsp.euclidean.twoD.Line.getTransform(at);
+
+            }
+            return sub.applyTransform(cachedTransform);
+        }
+
+    }
+
+    /** Translate the region by the specified amount.
+     * <p>The instance is not modified, a new instance is created.</p>
+     * @param translation translation to apply
+     * @return a new instance representing the translated region
+     */
+    public PolyhedronsSet translate(final Vector3D translation) {
+        return (PolyhedronsSet) applyTransform(new TranslationTransform(translation));
+    }
+
+    /** 3D translation as a transform. */
+    private static class TranslationTransform implements Transform {
+
+        /** Translation vector. */
+        private Vector3D   translation;
+
+        /** Cached original hyperplane. */
+        private Hyperplane cachedOriginal;
+
+        /** Cached 2D transform valid inside the cached original hyperplane. */
+        private Transform  cachedTransform;
+
+        /** Build a translation transform.
+         * @param translation translation vector
+         */
+        public TranslationTransform(final Vector3D translation) {
+            this.translation = translation;
+        }
+
+        /** {@inheritDoc} */
+        public Point apply(final Point point) {
+            return new Point3D(1.0, (Vector3D) point, 1.0, translation);
+        }
+
+        /** {@inheritDoc} */
+        public Hyperplane apply(final Hyperplane hyperplane) {
+            return ((Plane) hyperplane).translate(translation);
+        }
+
+        /** {@inheritDoc} */
+        public SubHyperplane apply(final SubHyperplane sub,
+                                   final Hyperplane original, final Hyperplane transformed) {
+            if (original != cachedOriginal) {
+                // we have changed hyperplane, reset the in-hyperplane transform
+
+                final Plane   oPlane = (Plane) original;
+                final Plane   tPlane = (Plane) transformed;
+                final Point2D shift  = (Point2D) tPlane.toSubSpace(apply((Point) oPlane.getOrigin()));
+                final AffineTransform at =
+                    AffineTransform.getTranslateInstance(shift.getX(), shift.getY());
+
+                cachedOriginal  = original;
+                cachedTransform =
+                    org.apache.commons.bsp.euclidean.twoD.Line.getTransform(at);
+
+            }
+
+            return sub.applyTransform(cachedTransform);
+
+        }
+
+    }
+
+}

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

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

Added: commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Edge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Edge.java?rev=1066664&view=auto
==============================================================================
--- commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Edge.java (added)
+++ commons/sandbox/bsp/trunk/src/main/java/org/apache/commons/bsp/euclidean/twoD/Edge.java Wed Feb  2 22:21:05 2011
@@ -0,0 +1,332 @@
+/*
+ * 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.euclidean.oneD.Point1D;
+import org.apache.commons.math.util.FastMath;
+
+/** This class represents an edge between two {@link Vertex vertices}.
+
+ * <p>When they are used for editable paths, edges are built from
+ * initial estimates of the {@link Vertex vertices} that interconnect
+ * them. When the editable path edges is complete, user defined
+ * constraints can be added and solved for. These constraints apply to
+ * the edge underlying {@link Line line} data (angle and origin
+ * offset), the vertices are recomputed afterwards from the adjusted
+ * lines intersections.</p>
+
+ * <p>So from the user point of view edges are defined in terms of
+ * vertices, but from an internal algorithmical point of view edges
+ * are defined in terms of lines and interconnection data.</p>
+
+ * <p>When non-closed polygons are handled, they have some unbounded
+ * edges. These edges have at least one null vertex. Such edges are
+ * supported, their length is positive infinity.</p>
+
+ * @version $Revision$ $Date$
+ */
+public class Edge {
+
+    /** Line containing the edge. */
+    private Line   line;
+
+    /** Start point of the edge. */
+    private Vertex start;
+
+    /** Start point abscissa. */
+    private double startX;
+
+    /** End point of the edge. */
+    private Vertex end;
+
+    /** End point abscissa. */
+    private double endX;
+
+    /** Build a bounded edge from two points.
+     * @param start starting point
+     * @param end ending point
+     */
+    public Edge(final Vertex start, final Vertex end) {
+        reset(start, end);
+    }
+
+    /** Build an edge from a line and from two points.
+     * <p>The line is oriented from start to end. If either start or end
+     * is null, the edge is unbounded.</p>
+     * @param line line containing the edge
+     * @param start starting point
+     * @param end ending point
+     */
+    public Edge(final Line line, final Vertex start, final Vertex end) {
+        reset(line, start, end);
+    }
+
+    /** Reset the instance as if built from a two points.
+     * <p>The line is oriented from start to end</p>
+     * @param newStart starting point
+     * @param newEnd ending point
+     */
+    public void reset(final Vertex newStart, final Vertex newEnd) {
+        this.line  = new Line(newStart, newEnd);
+        this.start = newStart;
+        this.end   = newEnd;
+        startX = ((Point1D) line.toSubSpace(newStart)).getAbscissa();
+        endX   = ((Point1D) line.toSubSpace(newEnd)).getAbscissa();
+        newStart.setLeaving(this);
+        newEnd.setIncoming(this);
+    }
+
+    /** Reset the instance as if built from a line and two points.
+     * <p>The line is oriented from start to end</p>
+     * @param newLine line containing the edge
+     * @param newStart starting point
+     * @param newEnd ending point
+     */
+    public void reset(final Line newLine, final Vertex newStart, final Vertex newEnd) {
+        this.line  = newLine;
+        this.start = newStart;
+        this.end   = newEnd;
+        if (newStart == null) {
+            startX = Double.NEGATIVE_INFINITY;
+        } else {
+            startX = ((Point1D) newLine.toSubSpace(newStart)).getAbscissa();
+            newStart.setLeaving(this);
+        }
+        if (newEnd == null) {
+            endX = Double.POSITIVE_INFINITY;
+        } else {
+            endX = ((Point1D) newLine.toSubSpace(newEnd)).getAbscissa();
+            newEnd.setIncoming(this);
+        }
+    }
+
+    /** Check is the instance is bounded.
+     * <p>An edge is bounded if it has non null start and end
+     * vertices.</p>
+     * @return true if the edge is bounded
+     */
+    public boolean isBounded() {
+        return (start != null) && (end != null);
+    }
+
+    /** Get the line containing the edge.
+     * @return line containing the edge
+     */
+    public Line getLine() {
+        return line;
+    }
+
+    /** Get the start point.
+     * @return start point of the edge
+     * @see #getStartAbscissa
+     * @see #getEnd
+     */
+    public Vertex getStart() {
+        return start;
+    }
+
+    /** Get the start point abscissa.
+     * @return start point abscissa
+     * @see #getStart
+     * @see #getEndAbscissa
+     */
+    public double getStartAbscissa() {
+        return startX;
+    }
+
+    /** Get the end point.
+     * @return end point of the edge
+     * @see #getStart
+     * @see #getEndAbscissa
+     */
+    public Vertex getEnd() {
+        return end;
+    }
+
+    /** Get the end point abscissa.
+     * @return end point abscissa
+     * @see #getStartAbscissa
+     * @see #getEnd
+     */
+    public double getEndAbscissa() {
+        return endX;
+    }
+
+    /** Check if the instance is connected to an edge.
+     * <p>Edges are connected if the start Vertex of one edge (i.e. the
+     * one given by {@link #getStart getStart()}) is the end Vertex of
+     * the other edge (i.e. the one given by {@link #getEnd
+     * getEnd()}).</p>
+     * @param edge edge to check against the instance
+     * @return true if the edge is connected to the instance, false
+     * otherwise
+     */
+    public boolean isConnected(final Edge edge) {
+        return ((start != null) && (start.getIncoming() == edge)) ||
+               ((end   != null) && (end.getLeaving()    == edge));
+    }
+
+    /** Get the length of the edge.
+     * @return length of the edge
+     */
+    public double getLength() {
+
+        if ((start == null) || (end == null)) {
+            return Double.POSITIVE_INFINITY;
+        }
+
+        return FastMath.hypot(end.x - start.x, end.y - start.y);
+
+    }
+
+    /** Get the linear coefficients of the edge length.
+     * <p>The edge is contained in a line l<sub>0</sub>,
+     * and bounded at its start vertex by line
+     * l<sub>s</sub> and at its end vertex by line
+     * l<sub>e</sub>. These lines are defined by their
+     * angles a<sub>0</sub>, a<sub>s</sub> and
+     * a<sub>e</sub> and by their offsets
+     * o<sub>0</sub>, o<sub>s</sub> and
+     * o<sub>e</sub>. The length of the edge depends
+     * linearly on the offsets : d = k<sub>s</sub>o<sub>s</sub> +
+     * k<sub>0</sub>o<sub>0</sub> + k<sub>e</sub>o<sub>e</sub>.</p>
+     * <p>This method computes the k<sub>s</sub>, k<sub>0</sub> and
+     * k<sub>e</sub> factors.</p>
+     * <p>This method can only be applied if all vertices have been
+     * bound to edges, otherwise {@code NullPointerException} will
+     * be triggered</p>
+     * @return a three elements array containing in order k<sub>s</sub>,
+     * k<sub>0</sub> and k<sub>e</sub> (the elements are all Double.NaN
+     * if the edge is unbounded)
+     */
+    public double[] lengthFactors() {
+        if ((start == null) | (end == null)) {
+            return new double[] {
+                Double.NaN, Double.NaN, Double.NaN
+            };
+        }
+
+        final double as = start.getIncoming().getLine().getAngle();
+        final double a0 = line.getAngle();
+        final double ae = end.getLeaving().getLine().getAngle();
+
+        return new double[] {
+            -1 / FastMath.sin(a0 - as),
+            +1 / FastMath.tan(ae - a0) + 1 / FastMath.tan(a0 - as),
+            -1 / FastMath.sin(ae - a0)
+        };
+
+    }
+
+    /** Get the linear coefficients of a parallel edge offset.
+     * <p>The edge is contained in a line l<sub>0</sub>,
+     * which is defined by its angle a<sub>0</sub> and its
+     * offset o<sub>0</sub>. The offset of another parallel
+     * edge depends linearly on the offsets of the line and of its own
+     * line: d = k<sub>0</sub>o<sub>0</sub> + k<sub>e</sub>o<sub>e</sub>.</p>
+     * <p>This method computes the k<sub>0</sub> and k<sub>e</sub>
+     * factors.</p>
+     * <p>This method can only be applied if all vertices have been
+     * bound to edges, otherwise {@code NullPointerException} will
+     * be triggered</p>
+     * @param edge parallel edge to consider
+     * @return a two elements array containing in order k<sub>0</sub>
+     * and k<sub>e</sub> (the elements are all Double.NaN
+     * if the edge is unbounded)
+     */
+    public double[] parallelEdgeOffsetFactors(final Edge edge) {
+        if ((start == null) | (end == null)) {
+            return new double[] {
+                Double.NaN, Double.NaN
+            };
+        }
+
+        final double da = edge.getLine().getAngle() - line.getAngle();
+        return new double[] {
+            1, (FastMath.cos(da) > 0) ? -1 : 1
+        };
+
+    }
+
+    /** Get the linear coefficients of vertex offset.
+     * <p>The edge is contained in a line {@code l<sub>0</sub>},
+     * which is defined by its angle {@code a<sub>0</sub>} and its
+     * offset {@code o<sub>0</sub>}. The offset of a vertex depends
+     * linearly on the offsets of the line and of its incoming and
+     * leaving edges: <code>d = k<sub>0</sub>o<sub>0</sub> +
+     * k<sub>i</sub>o<sub>i</sub> +
+     * k<sub>l</sub>o<sub>l</sub></code>.</p>
+     * <p>This method computes the k<sub>0</sub>, k<sub>i</sub> and
+     * k<sub>l</sub> factors.</p>
+     * <p>This method can only be applied if all vertices have been
+     * bound to edges, otherwise {@code NullPointerException} will
+     * be triggered</p>
+     * @param v vertex to consider
+     * @return a three elements array containing in order k<sub>0</sub>,
+     * k<sub>i</sub> and k<sub>l</sub> (the elements are all Double.NaN
+     * if the edge is unbounded)
+     */
+    public double[] vertexOffsetFactors(final Vertex v) {
+        if ((start == null) | (end == null)) {
+            return new double[] {
+                Double.NaN, Double.NaN, Double.NaN
+            };
+        }
+
+        final double a0 = line.getAngle();
+        final double ai = v.getIncoming().getLine().getAngle();
+        final double al = v.getLeaving().getLine().getAngle();
+        final double inv = 1.0 / FastMath.sin(ai - al);
+        return new double[] {
+            1,
+            inv * FastMath.sin(al - a0),
+            inv * FastMath.sin(a0 - ai)
+        };
+
+    }
+
+    /** Get the intersection point of a line with the instance.
+     * @param otherLine line intersecting (perhaps) the edge
+     * @return intersection point with line, null if the underlying line
+     * is parallel to specified line or if the lines intersection is out
+     * of edge range
+     */
+    public Point2D intersection(final Line otherLine) {
+        final Point2D point = (Point2D) line.intersection(otherLine);
+        if (point == null) {
+            return null;
+        }
+        final double x = ((Point1D) line.toSubSpace(point)).getAbscissa();
+        return (((startX - 1.0e-10) <= x) && (x <= (endX + 1.0e-10))) ? point : (Point2D) null;
+    }
+
+    /** Get the distance of a point to this edge.
+     * @param point point to check
+     * @return distance between the point and the edge
+     */
+    public double distance(final Point2D point) {
+        final double x = ((Point1D) line.toSubSpace(point)).getAbscissa();
+        if (x <= startX) {
+            return point.distance(start);
+        } else if (x >= endX) {
+            return point.distance(end);
+        } else {
+            return FastMath.abs(line.getOffset(point));
+        }
+    }
+
+}

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

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



Mime
View raw message