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.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.List;
    21
    22  import org.apache.commons.geometry.core.RegionLocation;
    23  import org.apache.commons.geometry.core.Transform;
    24  import org.apache.commons.geometry.core.internal.HyperplaneSubsets;
    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.SplitLocation;
    28  import org.apache.commons.geometry.euclidean.oned.Interval;
    29  import org.apache.commons.geometry.euclidean.oned.OrientedPoint;
    30  import org.apache.commons.geometry.euclidean.oned.OrientedPoints;
    31  import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
    32  import org.apache.commons.geometry.euclidean.oned.Vector1D;
    33  import org.apache.commons.geometry.euclidean.twod.Line.SubspaceTransform;
    34  import org.apache.commons.numbers.core.Precision;
    35
    36  /** Class representing an arbitrary subset of a line using a {@link RegionBSPTree1D}.
    37   * This class can represent convex, non-convex, finite, infinite, and empty regions.
    38   *
    39   * <p>This class is mutable and <em>not</em> thread safe.</p>
    40   */
    41  public final class EmbeddedTreeLineSubset extends LineSubset {
    42      /** The 1D region representing the area on the line. */
    43      private final RegionBSPTree1D region;
    44
    45      /** Construct a new, empty subset for the given line.
    46       * @param line line defining the subset
    47       */
    48      public EmbeddedTreeLineSubset(final Line line) {
    49          this(line, false);
    50      }
    51
    52      /** Construct a new subset for the given line. If {@code full}
    53       * is true, then the subset will cover the entire line; otherwise,
    54       * it will be empty.
    55       * @param line line defining the subset
    56       * @param full if true, the subset will cover the entire space;
    57       *      otherwise it will be empty
    58       */
    59      public EmbeddedTreeLineSubset(final Line line, final boolean full) {
    60          this(line, new RegionBSPTree1D(full));
    61      }
    62
    63      /** Construct a new instance from its defining line and subspace region. The give
    64       * BSP tree is used directly by this instance; it is not copied.
    65       * @param line line defining the subset
    66       * @param region subspace region for the instance
    67       */
    68      public EmbeddedTreeLineSubset(final Line line, final RegionBSPTree1D region) {
    69          super(line);
    70
    71          this.region = region;
    72      }
    73
    74      /** {@inheritDoc} */
    75      @Override
    76      public boolean isFull() {
    77          return region.isFull();
    78      }
    79
    80      /** {@inheritDoc} */
    81      @Override
    82      public boolean isEmpty() {
    83          return region.isEmpty();
    84      }
    85
    86      /** {@inheritDoc} */
    87      @Override
    88      public double getSize() {
    89          return region.getSize();
    90      }
    91
    92      /** {@inheritDoc} */
    93      @Override
    94      public Vector2D getCentroid() {
    95          final Vector1D subspaceCentroid = region.getCentroid();
    96          if (subspaceCentroid != null) {
    97              return getLine().toSpace(subspaceCentroid);
    98          }
    99          return null;
    100     }
    101
    102     /** {@inheritDoc} */
    103     @Override
    104     public Bounds2D getBounds() {
    105         final double min = region.getMin();
    106         final double max = region.getMax();
    107
    108         if (Double.isFinite(min) && Double.isFinite(max)) {
    109             final Line line = getLine();
    110
    111             return Bounds2D.builder()
    112                     .add(line.toSpace(min))
    113                     .add(line.toSpace(max))
    114                     .build();
    115         }
    116
    117         return null;
    118     }
    119
    120     /** {@inheritDoc} */
    121     @Override
    122     public Vector2D closest(final Vector2D pt) {
    123         return HyperplaneSubsets.closestToEmbeddedRegion(pt, getLine(), region);
    124     }
    125
    126     /** {@inheritDoc} */
    127     @Override
    128     public EmbeddedTreeLineSubset transform(final Transform<Vector2D> transform) {
    129         final SubspaceTransform st = getLine().subspaceTransform(transform);
    130
    131         final RegionBSPTree1D tRegion = RegionBSPTree1D.empty();
    132         tRegion.copy(region);
    133         tRegion.transform(st.getTransform());
    134
    135         return new EmbeddedTreeLineSubset(st.getLine(), tRegion);
    136     }
    137
    138     /** {@inheritDoc} */
    139     @Override
    140     public List<LineConvexSubset> toConvex() {
    141         final List<Interval> intervals = region.toIntervals();
    142
    143         final Line line = getLine();
    144         final List<LineConvexSubset> convexSubsets = new ArrayList<>(intervals.size());
    145
    146         for (final Interval interval : intervals) {
    147             convexSubsets.add(Lines.subsetFromInterval(line, interval));
    148         }
    149
    150         return convexSubsets;
    151     }
    152
    153     /** {@inheritDoc} */
    154     @Override
    155     public RegionBSPTree1D getSubspaceRegion() {
    156         return region;
    157     }
    158
    159     /** {@inheritDoc}
    160      *
    161      * <p>In all cases, the current instance is not modified. However, In order to avoid
    162      * unnecessary copying, this method will use the current instance as the split value when
    163      * the instance lies entirely on the plus or minus side of the splitter. For example, if
    164      * this instance lies entirely on the minus side of the splitter, the subplane
    165      * returned by {@link Split#getMinus()} will be this instance. Similarly, {@link Split#getPlus()}
    166      * will return the current instance if it lies entirely on the plus side. Callers need to make
    167      * special note of this, since this class is mutable.</p>
    168      */
    169     @Override
    170     public Split<EmbeddedTreeLineSubset> split(final Hyperplane<Vector2D> splitter) {
    171         final Line thisLine = getLine();
    172         final Line splitterLine = (Line) splitter;
    173         final Precision.DoubleEquivalence precision = getPrecision();
    174
    175         final Vector2D intersection = splitterLine.intersection(thisLine);
    176         if (intersection == null) {
    177             return getNonIntersectingSplitResult(splitterLine, this);
    178         }
    179
    180         final double abscissa = thisLine.abscissa(intersection);
    181         final OrientedPoint subspaceSplitter = OrientedPoints.fromLocationAndDirection(
    182                 abscissa,
    183                 splitterPlusIsPositiveFacing(splitterLine),
    184                 precision);
    185
    186         final Split<RegionBSPTree1D> subspaceSplit = region.split(subspaceSplitter);
    187         final SplitLocation subspaceSplitLoc = subspaceSplit.getLocation();
    188
    189         if (SplitLocation.MINUS == subspaceSplitLoc) {
    190             return new Split<>(this, null);
    191         } else if (SplitLocation.PLUS == subspaceSplitLoc) {
    192             return new Split<>(null, this);
    193         }
    194
    195         final EmbeddedTreeLineSubset minus = (subspaceSplit.getMinus() != null) ?
    196                 new EmbeddedTreeLineSubset(thisLine, subspaceSplit.getMinus()) :
    197                 null;
    198         final EmbeddedTreeLineSubset plus = (subspaceSplit.getPlus() != null) ?
    199                 new EmbeddedTreeLineSubset(thisLine, subspaceSplit.getPlus()) :
    200                 null;
    201
    202         return new Split<>(minus, plus);
    203     }
    204
    205     /** Add a line subset to this instance.
    206      * @param subset the line subset to add
    207      * @throws IllegalArgumentException if the given line subset is not from
    208      *      a line equivalent to this instance
    209      */
    210     public void add(final LineConvexSubset subset) {
    211         Lines.validateLinesEquivalent(getLine(), subset.getLine());
    212
    213         region.add(subset.getInterval());
    214     }
    215
    216     /** Add the region represented by the given line subset to this instance.
    217      * The argument is not modified.
    218      * @param subset line subset to add
    219      * @throws IllegalArgumentException if the given line subset is not from
    220      *      a line equivalent to this instance
    221      */
    222     public void add(final EmbeddedTreeLineSubset subset) {
    223         Lines.validateLinesEquivalent(getLine(), subset.getLine());
    224
    225         region.union(subset.getSubspaceRegion());
    226     }
    227
    228     /** {@inheritDoc} */
    229     @Override
    230     public String toString() {
    231         final Line line = getLine();
    232
    233         final StringBuilder sb = new StringBuilder();
    234         sb.append(this.getClass().getSimpleName())
    235             .append('[')
    236             .append("lineOrigin= ")
    237             .append(line.getOrigin())
    238             .append(", lineDirection= ")
    239             .append(line.getDirection())
    240             .append(", region= ")
    241             .append(region)
    242             .append(']');
    243
    244         return sb.toString();
    245     }
    246
    247     /** {@inheritDoc} */
    248     @Override
    249     RegionLocation classifyAbscissa(final double abscissa) {
    250         return region.classify(abscissa);
    251     }
    252 }