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.spherical.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.Collections;
    21  import java.util.List;
    22  import java.util.stream.Stream;
    23  import java.util.stream.StreamSupport;
    24
    25  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    26  import org.apache.commons.geometry.core.partitioning.Split;
    27  import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
    28  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
    29  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    30  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    31  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    32
    33  /** BSP tree representing regions in 2D spherical space.
    34   */
    35  public class RegionBSPTree2S extends AbstractRegionBSPTree<Point2S, RegionBSPTree2S.RegionNode2S>
    36      implements BoundarySource2S {
    37      /** Constant containing the area of the full spherical space. */
    38      private static final double FULL_SIZE = 4 * PlaneAngleRadians.PI;
    39
    40      /** List of great arc path comprising the region boundary. */
    41      private List<GreatArcPath> boundaryPaths;
    42
    43      /** Create a new, empty instance.
    44       */
    45      public RegionBSPTree2S() {
    46          this(false);
    47      }
    48
    49      /** Create a new region. If {@code full} is true, then the region will
    50       * represent the entire 2-sphere. Otherwise, it will be empty.
    51       * @param full whether or not the region should contain the entire
    52       *      2-sphere or be empty
    53       */
    54      public RegionBSPTree2S(final boolean full) {
    55          super(full);
    56      }
    57
    58      /** Return a deep copy of this instance.
    59       * @return a deep copy of this instance.
    60       * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
    61       */
    62      public RegionBSPTree2S copy() {
    63          final RegionBSPTree2S result = RegionBSPTree2S.empty();
    64          result.copy(this);
    65
    66          return result;
    67      }
    68
    69      /** {@inheritDoc} */
    70      @Override
    71      public Iterable<GreatArc> boundaries() {
    72          return createBoundaryIterable(b -> (GreatArc) b);
    73      }
    74
    75      /** {@inheritDoc} */
    76      @Override
    77      public Stream<GreatArc> boundaryStream() {
    78          return StreamSupport.stream(boundaries().spliterator(), false);
    79      }
    80
    81      /** {@inheritDoc} */
    82      @Override
    83      public List<GreatArc> getBoundaries() {
    84          return createBoundaryList(b -> (GreatArc) b);
    85      }
    86
    87      /** Get the boundary of the region as a list of connected great arc paths. The
    88       * arcs are oriented such that their minus (left) side lies on the interior of
    89       * the region.
    90       * @return great arc paths representing the region boundary
    91       */
    92      public List<GreatArcPath> getBoundaryPaths() {
    93          if (boundaryPaths == null) {
    94              boundaryPaths = Collections.unmodifiableList(computeBoundaryPaths());
    95          }
    96          return boundaryPaths;
    97      }
    98
    99      /** Return a list of {@link ConvexArea2S}s representing the same region
    100      * as this instance. One convex area is returned for each interior leaf
    101      * node in the tree.
    102      * @return a list of convex areas representing the same region as this
    103      *      instance
    104      */
    105     public List<ConvexArea2S> toConvex() {
    106         final List<ConvexArea2S> result = new ArrayList<>();
    107
    108         toConvexRecursive(getRoot(), ConvexArea2S.full(), result);
    109
    110         return result;
    111     }
    112
    113     /** Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given
    114      * node. The computed convex areas are added to the given list.
    115      * @param node root of the subtree to compute the convex areas for
    116      * @param nodeArea the convex area for the current node; this will be split by the node's cut hyperplane to
    117      *      form the convex areas for any child nodes
    118      * @param result list containing the results of the computation
    119      */
    120     private void toConvexRecursive(final RegionNode2S node, final ConvexArea2S nodeArea,
    121             final List<ConvexArea2S> result) {
    122         if (node.isLeaf()) {
    123             // base case; only add to the result list if the node is inside
    124             if (node.isInside()) {
    125                 result.add(nodeArea);
    126             }
    127         } else {
    128             // recurse
    129             final Split<ConvexArea2S> split = nodeArea.split(node.getCutHyperplane());
    130
    131             toConvexRecursive(node.getMinus(), split.getMinus(), result);
    132             toConvexRecursive(node.getPlus(), split.getPlus(), result);
    133         }
    134     }
    135
    136     /** {@inheritDoc} */
    137     @Override
    138     public Split<RegionBSPTree2S> split(final Hyperplane<Point2S> splitter) {
    139         return split(splitter, empty(), empty());
    140     }
    141
    142     /** {@inheritDoc} */
    143     @Override
    144     public Point2S project(final Point2S pt) {
    145         // use our custom projector so that we can disambiguate points that are
    146         // actually equidistant from the target point
    147         final BoundaryProjector2S projector = new BoundaryProjector2S(pt);
    148         accept(projector);
    149
    150         return projector.getProjected();
    151     }
    152
    153     /** Return the current instance.
    154      */
    155     @Override
    156     public RegionBSPTree2S toTree() {
    157         return this;
    158     }
    159
    160     /** {@inheritDoc} */
    161     @Override
    162     protected RegionSizeProperties<Point2S> computeRegionSizeProperties() {
    163         // handle simple cases
    164         if (isFull()) {
    165             return new RegionSizeProperties<>(FULL_SIZE, null);
    166         } else if (isEmpty()) {
    167             return new RegionSizeProperties<>(0, null);
    168         }
    169
    170         final List<ConvexArea2S> areas = toConvex();
    171         final DoublePrecisionContext precision = ((GreatArc) getRoot().getCut()).getPrecision();
    172
    173         double sizeSum = 0;
    174         Vector3D centroidVectorSum = Vector3D.ZERO;
    175
    176         Vector3D centroidVector;
    177         double maxCentroidVectorWeightSq = 0.0;
    178
    179         for (final ConvexArea2S area : areas) {
    180             sizeSum += area.getSize();
    181
    182             centroidVector = area.getWeightedCentroidVector();
    183             maxCentroidVectorWeightSq = Math.max(maxCentroidVectorWeightSq, centroidVector.normSq());
    184
    185             centroidVectorSum = centroidVectorSum.add(centroidVector);
    186         }
    187
    188         // Convert the weighted centroid vector to a point on the sphere surface. If the centroid vector
    189         // length is less than the max length of the combined convex areas and the vector itself is
    190         // equivalent to zero, then we know that there are opposing and approximately equal areas in the
    191         // region, resulting in an indeterminate centroid. This would occur, for example, if there were
    192         // equal areas around each pole.
    193         final Point2S centroid;
    194         if (centroidVectorSum.normSq() < maxCentroidVectorWeightSq &&
    195                 centroidVectorSum.eq(Vector3D.ZERO, precision)) {
    196             centroid = null;
    197         } else {
    198             centroid = Point2S.from(centroidVectorSum);
    199         }
    200
    201         return new RegionSizeProperties<>(sizeSum, centroid);
    202     }
    203
    204     /** {@inheritDoc} */
    205     @Override
    206     protected RegionNode2S createNode() {
    207         return new RegionNode2S(this);
    208     }
    209
    210     /** {@inheritDoc} */
    211     @Override
    212     protected void invalidate() {
    213         super.invalidate();
    214
    215         boundaryPaths = null;
    216     }
    217
    218     /** Compute the great arc paths comprising the region boundary.
    219      * @return the great arc paths comprising the region boundary
    220      */
    221     private List<GreatArcPath> computeBoundaryPaths() {
    222         final InteriorAngleGreatArcConnector connector = new InteriorAngleGreatArcConnector.Minimize();
    223         return connector.connectAll(boundaries());
    224     }
    225
    226     /** Return a new, empty BSP tree.
    227      * @return a new, empty BSP tree.
    228      */
    229     public static RegionBSPTree2S empty() {
    230         return new RegionBSPTree2S(false);
    231     }
    232
    233     /** Return a new, full BSP tree. The returned tree represents the
    234      * full space.
    235      * @return a new, full BSP tree.
    236      */
    237     public static RegionBSPTree2S full() {
    238         return new RegionBSPTree2S(true);
    239     }
    240
    241     /** Construct a new tree from the given boundaries. If no boundaries
    242      * are present, the returned tree is empty.
    243      * @param boundaries boundaries to construct the tree from
    244      * @return a new tree instance constructed from the given boundaries
    245      * @see #from(Iterable, boolean)
    246      */
    247     public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries) {
    248         return from(boundaries, false);
    249     }
    250
    251     /** Construct a new tree from the given boundaries. If {@code full} is true, then
    252      * the initial tree before boundary insertion contains the entire space. Otherwise,
    253      * it is empty.
    254      * @param boundaries boundaries to construct the tree from
    255      * @param full if true, the initial tree will contain the entire space
    256      * @return a new tree instance constructed from the given boundaries
    257      */
    258     public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries, final boolean full) {
    259         final RegionBSPTree2S tree = new RegionBSPTree2S(full);
    260         tree.insert(boundaries);
    261
    262         return tree;
    263     }
    264
    265     /** BSP tree node for two dimensional spherical space.
    266      */
    267     public static final class RegionNode2S extends AbstractRegionBSPTree.AbstractRegionNode<Point2S, RegionNode2S> {
    268         /** Simple constructor.
    269          * @param tree tree owning the instance.
    270          */
    271         private RegionNode2S(final AbstractBSPTree<Point2S, RegionNode2S> tree) {
    272             super(tree);
    273         }
    274
    275         /** Get the region represented by this node. The returned region contains
    276          * the entire area contained in this node, regardless of the attributes of
    277          * any child nodes.
    278          * @return the region represented by this node
    279          */
    280         public ConvexArea2S getNodeRegion() {
    281             ConvexArea2S area = ConvexArea2S.full();
    282
    283             RegionNode2S child = this;
    284             RegionNode2S parent;
    285
    286             while ((parent = child.getParent()) != null) {
    287                 final Split<ConvexArea2S> split = area.split(parent.getCutHyperplane());
    288
    289                 area = child.isMinus() ? split.getMinus() : split.getPlus();
    290
    291                 child = parent;
    292             }
    293
    294             return area;
    295         }
    296
    297         /** {@inheritDoc} */
    298         @Override
    299         protected RegionNode2S getSelf() {
    300             return this;
    301         }
    302     }
    303
    304     /** Class used to project points onto the region boundary.
    305      */
    306     private static final class BoundaryProjector2S extends BoundaryProjector<Point2S, RegionNode2S> {
    307         /** Simple constructor.
    308          * @param point the point to project onto the region's boundary
    309          */
    310         BoundaryProjector2S(final Point2S point) {
    311             super(point);
    312         }
    313
    314         /** {@inheritDoc} */
    315         @Override
    316         protected Point2S disambiguateClosestPoint(final Point2S target, final Point2S a, final Point2S b) {
    317             // return the point with the smallest coordinate values
    318             final int cmp = Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a, b);
    319             return cmp < 0 ? a : b;
    320         }
    321     }
    322 }