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.core.partitioning.bsp;
    18
    19  import java.util.Collections;
    20  import java.util.Iterator;
    21  import java.util.List;
    22
    23  import org.apache.commons.geometry.core.Point;
    24  import org.apache.commons.geometry.core.Sized;
    25  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    26
    27  /** Class representing the portion of an
    28   * {@link AbstractRegionBSPTree.AbstractRegionNode AbstractRegionNode}'s cut that
    29   * lies on the boundary of the region. Portions of the node cut may be oriented so
    30   * that the plus side of the cut points toward the outside of the region
    31   * ({@link #getOutsideFacing()}) and other portions toward the inside of the
    32   * region ({@link #getInsideFacing()}). The inside-facing and outside-facing portions
    33   * of the region boundary are represented as lists of disjoint hyperplane convex subsets,
    34   * all originating from the same hyperplane convex subset forming the node cut.
    35   *
    36   * @param <P> Point implementation type
    37   */
    38  public final class RegionCutBoundary<P extends Point<P>> implements Sized {
    39
    40      /** Portion of the cut oriented such that the plus side of the cut points to the inside of the region. */
    41      private final List<HyperplaneConvexSubset<P>> insideFacing;
    42
    43      /** Portion of the cut oriented such that the plus side of the cut points to the outside of the region. */
    44      private final List<HyperplaneConvexSubset<P>> outsideFacing;
    45
    46      /** Construct a new instance from the inside-facing and outside-facing portions of a node cut. The
    47       * given lists are expected to be disjoint regions originating from the same hyperplane convex subset.
    48       * No validation is performed.
    49       * @param insideFacing the inside-facing portion of the node cut
    50       * @param outsideFacing the outside-facing portion of the node cut
    51       */
    52      RegionCutBoundary(final List<HyperplaneConvexSubset<P>> insideFacing,
    53              final List<HyperplaneConvexSubset<P>> outsideFacing) {
    54          this.insideFacing = insideFacing != null ?
    55                  Collections.unmodifiableList(insideFacing) :
    56                  Collections.emptyList();
    57
    58          this.outsideFacing = outsideFacing != null ?
    59                  Collections.unmodifiableList(outsideFacing) :
    60                  Collections.emptyList();
    61      }
    62
    63      /** Get the portion of the cut with its plus side facing the inside of the region.
    64       * @return the portion of the cut with its plus side facing the
    65       *      inside of the region
    66       */
    67      public List<HyperplaneConvexSubset<P>> getInsideFacing() {
    68          return insideFacing;
    69      }
    70
    71      /** Get the portion of the cut with its plus side facing the outside of the region.
    72       * @return the portion of the cut with its plus side facing the
    73       *      outside of the region
    74       */
    75      public List<HyperplaneConvexSubset<P>> getOutsideFacing() {
    76          return outsideFacing;
    77      }
    78
    79      /** Get the total size of the cut boundary, including inside and outside facing components.
    80       * @return the total size of the cut boundary, including inside and outside facing components
    81       */
    82      @Override
    83      public double getSize() {
    84          return getTotalSize(insideFacing) + getTotalSize(outsideFacing);
    85      }
    86
    87      /** Get the total size of all boundaries in the given list.
    88       * @param boundaries boundaries to compute the size for
    89       * @return the total size of all boundaries in the given list
    90       */
    91      private double getTotalSize(final List<HyperplaneConvexSubset<P>> boundaries) {
    92          double total = 0.0;
    93          for (final HyperplaneConvexSubset<P> boundary : boundaries) {
    94              total += boundary.getSize();
    95
    96              if (Double.isInfinite(total)) {
    97                  return total;
    98              }
    99          }
    100
    101         return total;
    102     }
    103
    104     /** Return the closest point to the argument in the inside and outside facing
    105      * portions of the cut boundary.
    106      * @param pt the reference point
    107      * @return the point in the cut boundary closest to the reference point
    108      * @see HyperplaneConvexSubset#closest(Point)
    109      */
    110     public P closest(final P pt) {
    111         P closest = null;
    112         double closestDist = Double.POSITIVE_INFINITY;
    113
    114         final Iterator<HyperplaneConvexSubset<P>> insideIt = insideFacing.iterator();
    115         final Iterator<HyperplaneConvexSubset<P>> outsideIt = outsideFacing.iterator();
    116
    117         HyperplaneConvexSubset<P> boundary;
    118         P testPt;
    119         double dist;
    120
    121         while (insideIt.hasNext() || outsideIt.hasNext()) {
    122             boundary = insideIt.hasNext() ?
    123                     insideIt.next() :
    124                     outsideIt.next();
    125
    126             testPt = boundary.closest(pt);
    127             dist = pt.distance(testPt);
    128
    129             if (closest == null || dist < closestDist) {
    130                 closest = testPt;
    131                 closestDist = dist;
    132             }
    133         }
    134
    135         return closest;
    136     }
    137
    138     /** Return true if the given point is contained in the boundary, in either the
    139      * inside facing portion or the outside facing portion.
    140      * @param pt point to test
    141      * @return true if the point is contained in the boundary
    142      * @see HyperplaneConvexSubset#contains(Point)
    143      */
    144     public boolean contains(final P pt) {
    145         return containsInsideFacing(pt) || containsOutsideFacing(pt);
    146     }
    147
    148     /** Return true if the given point is contained in the inside-facing portion of
    149      * the region boundary.
    150      * @param pt point to test
    151      * @return true if the point is contained in the inside-facing portion of the region
    152      *      boundary
    153      */
    154     public boolean containsInsideFacing(final P pt) {
    155         return anyContains(pt, insideFacing);
    156     }
    157
    158     /** Return true if the given point is contained in the outside-facing portion of the
    159      * region boundary.
    160      * @param pt point to test
    161      * @return true if the point is contained in the outside-facing portion of the region
    162      *      boundary
    163      */
    164     public boolean containsOutsideFacing(final P pt) {
    165         return anyContains(pt, outsideFacing);
    166     }
    167
    168     /** Return true if the point is contained in any of the given boundaries.
    169      * @param pt point to test
    170      * @param boundaries
    171      * @return true if the point is contained in any of the given boundaries
    172      */
    173     private boolean anyContains(final P pt, final List<HyperplaneConvexSubset<P>> boundaries) {
    174         for (final HyperplaneConvexSubset<P> boundary : boundaries) {
    175             if (boundary.contains(pt)) {
    176                 return true;
    177             }
    178         }
    179
    180         return false;
    181     }
    182 }