View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.geometry.euclidean.threed;
18  
19  import java.util.ArrayList;
20  import java.util.List;
21  
22  import org.apache.commons.geometry.core.Transform;
23  import org.apache.commons.geometry.core.partitioning.Hyperplane;
24  import org.apache.commons.geometry.core.partitioning.Split;
25  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
26  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
27  import org.apache.commons.geometry.euclidean.twod.Vector2D;
28  import org.apache.commons.geometry.euclidean.twod.rotation.Rotation2D;
29  import org.apache.commons.numbers.core.Precision;
30  
31  /** Class representing an arbitrary subset of a plane using a {@link RegionBSPTree2D}.
32   * This class can represent convex, non-convex, finite, infinite, and empty regions.
33   *
34   * <p>This class is mutable and <em>not</em> thread safe.</p>
35   */
36  public final class EmbeddedTreePlaneSubset extends AbstractEmbeddedRegionPlaneSubset {
37  
38      /** The 2D region representing the area on the plane. */
39      private final RegionBSPTree2D region;
40  
41      /** Construct a new, empty plane subset for the given plane.
42       * @param plane plane containing the subset
43       */
44      public EmbeddedTreePlaneSubset(final EmbeddingPlane plane) {
45          this(plane, false);
46      }
47  
48      /** Construct a new subset for the given plane. If {@code full}
49       * is true, then the subset will cover the entire plane; otherwise,
50       * it will be empty.
51       * @param plane plane containing the subset
52       * @param full if true, the subset will cover the entire space;
53       *      otherwise it will be empty
54       */
55      public EmbeddedTreePlaneSubset(final EmbeddingPlane plane, final boolean full) {
56          this(plane, new RegionBSPTree2D(full));
57      }
58  
59      /** Construct a new instance from its defining plane and subspace region.
60       * @param plane plane containing the subset
61       * @param region subspace region for the plane subset
62       */
63      public EmbeddedTreePlaneSubset(final EmbeddingPlane plane, final RegionBSPTree2D region) {
64          super(plane);
65  
66          this.region = region;
67      }
68  
69      /** {@inheritDoc} */
70      @Override
71      public PlaneSubset.Embedded getEmbedded() {
72          return this;
73      }
74  
75      /** {@inheritDoc} */
76      @Override
77      public RegionBSPTree2D getSubspaceRegion() {
78          return region;
79      }
80  
81      /** {@inheritDoc} */
82      @Override
83      public List<PlaneConvexSubset> toConvex() {
84          final List<ConvexArea> areas = region.toConvex();
85  
86          final List<PlaneConvexSubset> facets = new ArrayList<>(areas.size());
87  
88          for (final ConvexArea area : areas) {
89              facets.add(Planes.subsetFromConvexArea(getPlane(), area));
90          }
91  
92          return facets;
93      }
94  
95      /** {@inheritDoc} */
96      @Override
97      public List<Triangle3D> toTriangles() {
98          final EmbeddingPlane plane = getPlane();
99          final List<Triangle3D> triangles = new ArrayList<>();
100 
101         List<Vector3D> vertices;
102         for (final ConvexArea area : region.toConvex()) {
103             if (area.isInfinite()) {
104                 throw new IllegalStateException("Cannot convert infinite plane subset to triangles: " + this);
105             }
106 
107             vertices = plane.toSpace(area.getVertices());
108 
109             triangles.addAll(Planes.convexPolygonToTriangleFan(plane, vertices));
110         }
111 
112         return triangles;
113     }
114 
115     /** {@inheritDoc} */
116     @Override
117     public Bounds3D getBounds() {
118         return getBoundsFromSubspace(region);
119     }
120 
121     /** {@inheritDoc}
122      *
123      * <p>In all cases, the current instance is not modified. However, In order to avoid
124      * unnecessary copying, this method will use the current instance as the split value when
125      * the instance lies entirely on the plus or minus side of the splitter. For example, if
126      * this instance lies entirely on the minus side of the splitter, the plane subset
127      * returned by {@link Split#getMinus()} will be this instance. Similarly, {@link Split#getPlus()}
128      * will return the current instance if it lies entirely on the plus side. Callers need to make
129      * special note of this, since this class is mutable.</p>
130      */
131     @Override
132     public Split<EmbeddedTreePlaneSubset> split(final Hyperplane<Vector3D> splitter) {
133         return Planes.subspaceSplit((Plane) splitter, this,
134             (p, r) -> new EmbeddedTreePlaneSubset(p, (RegionBSPTree2D) r));
135     }
136 
137     /** {@inheritDoc} */
138     @Override
139     public EmbeddedTreePlaneSubset transform(final Transform<Vector3D> transform) {
140         final EmbeddingPlane.SubspaceTransform subTransform =
141                 getPlane().getEmbedding().subspaceTransform(transform);
142 
143         final RegionBSPTree2D tRegion = RegionBSPTree2D.empty();
144         tRegion.copy(region);
145         tRegion.transform(subTransform.getTransform());
146 
147         return new EmbeddedTreePlaneSubset(subTransform.getPlane(), tRegion);
148     }
149 
150     /** Add a plane convex subset to this instance.
151      * @param subset plane convex subset to add
152      * @throws IllegalArgumentException if the given plane subset is not from
153      *      a plane equivalent to this instance
154      */
155     public void add(final PlaneConvexSubset subset) {
156         Planes.validatePlanesEquivalent(getPlane(), subset.getPlane());
157 
158         final PlaneConvexSubset.Embedded embedded = subset.getEmbedded();
159         final Rotation2D rot = getEmbeddedRegionRotation(embedded);
160 
161         final ConvexArea subspaceArea = embedded.getSubspaceRegion();
162 
163         final ConvexArea toAdd = rot != null ?
164                 subspaceArea.transform(rot) :
165                 subspaceArea;
166 
167         region.add(toAdd);
168     }
169 
170     /** Add a plane subset to this instance.
171      * @param subset plane subset to add
172      * @throws IllegalArgumentException if the given plane subset is not from
173      *      a plane equivalent to this instance
174      */
175     public void add(final EmbeddedTreePlaneSubset subset) {
176         Planes.validatePlanesEquivalent(getPlane(), subset.getPlane());
177 
178         final RegionBSPTree2D otherTree = subset.getSubspaceRegion();
179         final Rotation2D rot = getEmbeddedRegionRotation(subset);
180 
181         final RegionBSPTree2D regionToAdd;
182         if (rot != null) {
183             // we need to transform the subspace region before adding
184             regionToAdd = otherTree.copy();
185             regionToAdd.transform(rot);
186         } else {
187             regionToAdd = otherTree;
188         }
189 
190         region.union(regionToAdd);
191     }
192 
193     /** Construct a rotation transform used to transform the subspace of the given embedded region plane
194      * subset into the subspace of this instance. Returns null if no transform is needed. This method must only
195      * be called with embedded regions that share an equivalent plane with this instance, meaning that the
196      * planes have the same origin point and normal
197      * @param embedded the embedded region plane subset to compare with the current instance
198      * @return a rotation transform to convert from the subspace of the argument into the current subspace; returns
199      *      null if no such transform is needed
200      */
201     private Rotation2D getEmbeddedRegionRotation(final PlaneSubset.Embedded embedded) {
202         // check if we need to apply a rotation to the given embedded subspace
203         final EmbeddingPlane thisPlane = getPlane();
204         final EmbeddingPlane otherPlane = embedded.getPlane();
205 
206         final Precision.DoubleEquivalence precision = thisPlane.getPrecision();
207 
208         final double uDot = thisPlane.getU().dot(otherPlane.getU());
209         if (!precision.eq(uDot, 1.0)) {
210             final Vector2D otherPlaneU = thisPlane.toSubspace(otherPlane.getOrigin().add(otherPlane.getU()));
211             final double angle = Math.atan2(otherPlaneU.getY(), otherPlaneU.getX());
212 
213             return Rotation2D.of(angle);
214         }
215 
216         return null;
217     }
218 }