EmbeddedTreePlaneSubset.java

  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;

  19. import java.util.ArrayList;
  20. import java.util.List;

  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;

  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 {

  38.     /** The 2D region representing the area on the plane. */
  39.     private final RegionBSPTree2D region;

  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.     }

  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.     }

  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);

  66.         this.region = region;
  67.     }

  69.     /** {@inheritDoc} */
  70.     @Override
  71.     public PlaneSubset.Embedded getEmbedded() {
  72.         return this;
  73.     }

  75.     /** {@inheritDoc} */
  76.     @Override
  77.     public RegionBSPTree2D getSubspaceRegion() {
  78.         return region;
  79.     }

  81.     /** {@inheritDoc} */
  82.     @Override
  83.     public List<PlaneConvexSubset> toConvex() {
  84.         final List<ConvexArea> areas = region.toConvex();

  86.         final List<PlaneConvexSubset> facets = new ArrayList<>(areas.size());

  88.         for (final ConvexArea area : areas) {
  89.             facets.add(Planes.subsetFromConvexArea(getPlane(), area));
  90.         }

  92.         return facets;
  93.     }

  95.     /** {@inheritDoc} */
  96.     @Override
  97.     public List<Triangle3D> toTriangles() {
  98.         final EmbeddingPlane plane = getPlane();
  99.         final List<Triangle3D> triangles = new ArrayList<>();

  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.             }

  107.             vertices = plane.toSpace(area.getVertices());

  109.             triangles.addAll(Planes.convexPolygonToTriangleFan(plane, vertices));
  110.         }

  112.         return triangles;
  113.     }

  115.     /** {@inheritDoc} */
  116.     @Override
  117.     public Bounds3D getBounds() {
  118.         return getBoundsFromSubspace(region);
  119.     }

  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.     }

  137.     /** {@inheritDoc} */
  138.     @Override
  139.     public EmbeddedTreePlaneSubset transform(final Transform<Vector3D> transform) {
  140.         final EmbeddingPlane.SubspaceTransform subTransform =
  141.                 getPlane().getEmbedding().subspaceTransform(transform);

  143.         final RegionBSPTree2D tRegion = RegionBSPTree2D.empty();
  144.         tRegion.copy(region);
  145.         tRegion.transform(subTransform.getTransform());

  147.         return new EmbeddedTreePlaneSubset(subTransform.getPlane(), tRegion);
  148.     }

  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());

  158.         final PlaneConvexSubset.Embedded embedded = subset.getEmbedded();
  159.         final Rotation2D rot = getEmbeddedRegionRotation(embedded);

  161.         final ConvexArea subspaceArea = embedded.getSubspaceRegion();

  163.         final ConvexArea toAdd = rot != null ?
  164.                 subspaceArea.transform(rot) :
  165.                 subspaceArea;

  167.         region.add(toAdd);
  168.     }

  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());

  178.         final RegionBSPTree2D otherTree = subset.getSubspaceRegion();
  179.         final Rotation2D rot = getEmbeddedRegionRotation(subset);

  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.         }

  190.         region.union(regionToAdd);
  191.     }

  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();

  206.         final Precision.DoubleEquivalence precision = thisPlane.getPrecision();

  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());

  213.             return Rotation2D.of(angle);
  214.         }

  216.         return null;
  217.     }
  218. }
Created with JaCoCo 0.8.5.201910111838