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 [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...
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 (α) around Z
+ * (0 is +X, π/2 is +Y, π is -X and 3π/2 is -Y)
+ * @param delta elevation (δ) above (XY) plane, from -π/2 to +π/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