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.euclidean.threed.Vector3D;
    30  import org.apache.commons.numbers.core.Precision;
    31  import org.apache.commons.numbers.core.Sum;
    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 * Math.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(GreatArc.class::cast);
    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(GreatArc.class::cast);
    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<? super 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 Precision.DoubleEquivalence precision = ((GreatArc) getRoot().getCut()).getPrecision();
    172
    173         final Sum sizeSum = Sum.create();
    174         final Vector3D.Sum centroidVectorSum = Vector3D.Sum.create();
    175
    176         double maxCentroidVectorWeightSq = 0.0;
    177
    178         for (final ConvexArea2S area : areas) {
    179             sizeSum.add(area.getSize());
    180
    181             final Vector3D areaCentroidVector = area.getWeightedCentroidVector();
    182             maxCentroidVectorWeightSq = Math.max(maxCentroidVectorWeightSq, areaCentroidVector.normSq());
    183
    184             centroidVectorSum.add(areaCentroidVector);
    185         }
    186
    187         final double size = sizeSum.getAsDouble();
    188         final Vector3D centroidVector = centroidVectorSum.get();
    189
    190         // Convert the weighted centroid vector to a point on the sphere surface. If the centroid vector
    191         // length is less than the max length of the combined convex areas and the vector itself is
    192         // equivalent to zero, then we know that there are opposing and approximately equal areas in the
    193         // region, resulting in an indeterminate centroid. This would occur, for example, if there were
    194         // equal areas around each pole.
    195         final Point2S centroid;
    196         if (centroidVector.normSq() < maxCentroidVectorWeightSq &&
    197                 centroidVector.eq(Vector3D.ZERO, precision)) {
    198             centroid = null;
    199         } else {
    200             centroid = Point2S.from(centroidVector);
    201         }
    202
    203         return new RegionSizeProperties<>(size, centroid);
    204     }
    205
    206     /** {@inheritDoc} */
    207     @Override
    208     protected RegionNode2S createNode() {
    209         return new RegionNode2S(this);
    210     }
    211
    212     /** {@inheritDoc} */
    213     @Override
    214     protected void invalidate() {
    215         super.invalidate();
    216
    217         boundaryPaths = null;
    218     }
    219
    220     /** Compute the great arc paths comprising the region boundary.
    221      * @return the great arc paths comprising the region boundary
    222      */
    223     private List<GreatArcPath> computeBoundaryPaths() {
    224         final InteriorAngleGreatArcConnector connector = new InteriorAngleGreatArcConnector.Minimize();
    225         return connector.connectAll(boundaries());
    226     }
    227
    228     /** Return a new, empty BSP tree.
    229      * @return a new, empty BSP tree.
    230      */
    231     public static RegionBSPTree2S empty() {
    232         return new RegionBSPTree2S(false);
    233     }
    234
    235     /** Return a new, full BSP tree. The returned tree represents the
    236      * full space.
    237      * @return a new, full BSP tree.
    238      */
    239     public static RegionBSPTree2S full() {
    240         return new RegionBSPTree2S(true);
    241     }
    242
    243     /** Construct a new tree from the given boundaries. If no boundaries
    244      * are present, the returned tree is empty.
    245      * @param boundaries boundaries to construct the tree from
    246      * @return a new tree instance constructed from the given boundaries
    247      * @see #from(Iterable, boolean)
    248      */
    249     public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries) {
    250         return from(boundaries, false);
    251     }
    252
    253     /** Construct a new tree from the given boundaries. If {@code full} is true, then
    254      * the initial tree before boundary insertion contains the entire space. Otherwise,
    255      * it is empty.
    256      * @param boundaries boundaries to construct the tree from
    257      * @param full if true, the initial tree will contain the entire space
    258      * @return a new tree instance constructed from the given boundaries
    259      */
    260     public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries, final boolean full) {
    261         final RegionBSPTree2S tree = new RegionBSPTree2S(full);
    262         tree.insert(boundaries);
    263
    264         return tree;
    265     }
    266
    267     /** BSP tree node for two dimensional spherical space.
    268      */
    269     public static final class RegionNode2S extends AbstractRegionBSPTree.AbstractRegionNode<Point2S, RegionNode2S> {
    270         /** Simple constructor.
    271          * @param tree tree owning the instance.
    272          */
    273         private RegionNode2S(final AbstractBSPTree<Point2S, RegionNode2S> tree) {
    274             super(tree);
    275         }
    276
    277         /** Get the region represented by this node. The returned region contains
    278          * the entire area contained in this node, regardless of the attributes of
    279          * any child nodes.
    280          * @return the region represented by this node
    281          */
    282         public ConvexArea2S getNodeRegion() {
    283             ConvexArea2S area = ConvexArea2S.full();
    284
    285             RegionNode2S child = this;
    286             RegionNode2S parent;
    287
    288             while ((parent = child.getParent()) != null) {
    289                 final Split<ConvexArea2S> split = area.split(parent.getCutHyperplane());
    290
    291                 area = child.isMinus() ? split.getMinus() : split.getPlus();
    292
    293                 child = parent;
    294             }
    295
    296             return area;
    297         }
    298
    299         /** {@inheritDoc} */
    300         @Override
    301         protected RegionNode2S getSelf() {
    302             return this;
    303         }
    304     }
    305
    306     /** Class used to project points onto the region boundary.
    307      */
    308     private static final class BoundaryProjector2S extends BoundaryProjector<Point2S, RegionNode2S> {
    309         /** Simple constructor.
    310          * @param point the point to project onto the region's boundary
    311          */
    312         BoundaryProjector2S(final Point2S point) {
    313             super(point);
    314         }
    315
    316         /** {@inheritDoc} */
    317         @Override
    318         protected Point2S disambiguateClosestPoint(final Point2S target, final Point2S a, final Point2S b) {
    319             // return the point with the smallest coordinate values
    320             final int cmp = Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a, b);
    321             return cmp < 0 ? a : b;
    322         }
    323     }
    324 }