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.core.precision.DoublePrecisionContext;
    26  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
    27  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
    28  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    29  import org.apache.commons.geometry.euclidean.twod.rotation.Rotation2D;
    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 DoublePrecisionContext 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 }