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;
    18
    19  import java.util.Arrays;
    20  import java.util.Collections;
    21  import java.util.List;
    22  import java.util.Objects;
    23  import java.util.function.ToDoubleBiFunction;
    24
    25  import org.apache.commons.geometry.core.Embedding;
    26  import org.apache.commons.geometry.core.Point;
    27  import org.apache.commons.geometry.core.Region;
    28  import org.apache.commons.geometry.core.RegionLocation;
    29  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    30  import org.apache.commons.geometry.euclidean.oned.Vector1D;
    31
    32  /** Abstract base class representing an n-sphere, which is a generalization of the ordinary 3 dimensional
    33   * sphere to arbitrary dimensions.
    34   * @param <V> Vector implementation type
    35   * @see <a href="https://wikipedia.org/wiki/N-sphere">N-sphere</a>
    36   */
    37  public abstract class AbstractNSphere<V extends EuclideanVector<V>> implements Region<V> {
    38
    39      /** The center point of the n-sphere. */
    40      private final V center;
    41
    42      /** The radius of the n-sphere. */
    43      private final double radius;
    44
    45      /** Precision object used to perform floating point comparisons. */
    46      private final DoublePrecisionContext precision;
    47
    48      /** Construct a new instance from its component parts.
    49       * @param center the center point of the n-sphere
    50       * @param radius the radius of the n-sphere
    51       * @param precision precision context used to perform floating point comparisons
    52       * @throws IllegalArgumentException if center is not finite or radius is not finite or is
    53       *      less than or equal to zero as evaluated by the given precision context
    54       */
    55      protected AbstractNSphere(final V center, final double radius, final DoublePrecisionContext precision) {
    56          if (!center.isFinite()) {
    57              throw new IllegalArgumentException("Illegal center point: " + center);
    58          }
    59          if (!Double.isFinite(radius) || precision.lte(radius, 0.0)) {
    60              throw new IllegalArgumentException("Illegal radius: " + radius);
    61          }
    62
    63          this.center = center;
    64          this.radius = radius;
    65          this.precision = precision;
    66      }
    67
    68      /** Get the center point of the n-sphere.
    69       * @return the center of the n-sphere
    70       */
    71      public V getCenter() {
    72          return center;
    73      }
    74
    75      /** Get the radius of the n-sphere.
    76       * @return the radius of the n-sphere.
    77       */
    78      public double getRadius() {
    79          return radius;
    80      }
    81
    82      /** Get the precision object used to perform floating point
    83       * comparisons for this instance.
    84       * @return the precision object for this instance
    85       */
    86      public DoublePrecisionContext getPrecision() {
    87          return precision;
    88      }
    89
    90      /** {@inheritDoc}
    91      *
    92      * <p>This method always returns {@code false}.</p>
    93      */
    94      @Override
    95      public boolean isFull() {
    96          return false;
    97      }
    98
    99      /** {@inheritDoc}
    100     *
    101     * <p>This method always returns {@code false}.</p>
    102     */
    103     @Override
    104     public boolean isEmpty() {
    105         return false;
    106     }
    107
    108     /** {@inheritDoc}
    109      *
    110      * <p>This method is an alias for {@link #getCenter()}.</p>
    111      */
    112     @Override
    113     public V getCentroid() {
    114         return getCenter();
    115     }
    116
    117     /** {@inheritDoc} */
    118     @Override
    119     public RegionLocation classify(final V pt) {
    120         final double dist = ((Point<V>) center).distance(pt);
    121         final int cmp = precision.compare(dist, radius);
    122         if (cmp < 0) {
    123             return RegionLocation.INSIDE;
    124         } else if (cmp > 0) {
    125             return RegionLocation.OUTSIDE;
    126         }
    127         return RegionLocation.BOUNDARY;
    128     }
    129
    130     /** {@inheritDoc} */
    131     @Override
    132     public int hashCode() {
    133         return Objects.hash(center, radius, precision);
    134     }
    135
    136     /** {@inheritDoc} */
    137     @Override
    138     public boolean equals(final Object obj) {
    139         if (this == obj) {
    140             return true;
    141         } else if (obj == null || !obj.getClass().equals(this.getClass())) {
    142             return false;
    143         }
    144
    145         final AbstractNSphere<?> other = (AbstractNSphere<?>) obj;
    146
    147         return Objects.equals(this.center, other.center) &&
    148                 Double.compare(this.radius, other.radius) == 0 &&
    149                 Objects.equals(this.getPrecision(), other.getPrecision());
    150     }
    151
    152     /** {@inheritDoc} */
    153     @Override
    154     public String toString() {
    155         final StringBuilder sb = new StringBuilder();
    156         sb.append(this.getClass().getSimpleName())
    157             .append("[center= ")
    158             .append(center)
    159             .append(", radius= ")
    160             .append(radius)
    161             .append(']');
    162
    163         return sb.toString();
    164     }
    165
    166     /** Project the given point to the boundary of the n-sphere. If
    167      * the given point is exactly equal to the n-sphere center, it is
    168      * projected to the boundary in the direction of {@code defaultVector}.
    169      * @param pt the point to project
    170      * @param defaultVector the direction to project the point if it lies
    171      *      exactly at the center of the n-sphere
    172      * @return the projected point
    173      */
    174     protected V project(final V pt, final V defaultVector) {
    175         V vec = center.vectorTo(pt);
    176         if (vec.equals(vec.getZero())) {
    177             // use the default project vector if the given point lies
    178             // exactly_ on the center point
    179             vec = defaultVector;
    180         }
    181
    182         return vec.withNorm(radius).add(center);
    183     }
    184
    185     /** Internal method to compute the intersections between a line and this instance. The returned list will
    186      * contain either 0, 1, or 2 points.
    187      * <ul>
    188      *      <li><strong>2 points</strong> - The line is a secant line and intersects the n-sphere at two
    189      *      distinct points. The points are ordered such that the first point in the list is the first point
    190      *      encountered when traveling in the direction of the line. (In other words, the points are ordered
    191      *      by increasing abscissa value.)
    192      *      </li>
    193      *      <li><strong>1 point</strong> - The line is a tangent line and only intersects the n-sphere at a
    194      *      single point (as evaluated by the n-sphere's precision context).
    195      *      </li>
    196      *      <li><strong>0 points</strong> - The line does not intersect the n-sphere.</li>
    197      * </ul>
    198      * @param <L> Line implementation type
    199      * @param line line to intersect with the n-sphere
    200      * @param abscissaFn function used to compute the abscissa value of a point on a line
    201      * @param distanceFn function used to compute the smallest distance between a point
    202      *      and a line
    203      * @return a list of intersection points between the given line and this n-sphere
    204      */
    205     protected <L extends Embedding<V, Vector1D>> List<V> intersections(final L line,
    206             final ToDoubleBiFunction<L, V> abscissaFn, final ToDoubleBiFunction<L, V> distanceFn) {
    207
    208         final double dist = distanceFn.applyAsDouble(line, center);
    209
    210         final int cmp = precision.compare(dist, radius);
    211         if (cmp <= 0) {
    212             // on the boundary or inside the n-sphere
    213             final double abscissa = abscissaFn.applyAsDouble(line, center);
    214             final double abscissaDelta = Math.sqrt((radius * radius) - (dist * dist));
    215
    216             final V p0 = line.toSpace(Vector1D.of(abscissa - abscissaDelta));
    217             if (cmp < 0) {
    218                 // secant line => two intersections
    219                 final V p1 = line.toSpace(Vector1D.of(abscissa + abscissaDelta));
    220
    221                 return Arrays.asList(p0, p1);
    222             }
    223
    224             // tangent line => one intersection
    225             return Collections.singletonList(p0);
    226         }
    227
    228         // no intersections
    229         return Collections.emptyList();
    230     }
    231
    232     /** Internal method to compute the first intersection between a line and this instance.
    233      * @param <L> Line implementation type
    234      * @param line line to intersect with the n-sphere
    235      * @param abscissaFn function used to compute the abscissa value of a point on a line
    236      * @param distanceFn function used to compute the smallest distance between a point
    237      *      and a line
    238      * @return the first intersection between the given line and this instance or null if
    239      *      no such intersection exists
    240      */
    241     protected <L extends Embedding<V, Vector1D>> V firstIntersection(final L line,
    242             final ToDoubleBiFunction<L, V> abscissaFn, final ToDoubleBiFunction<L, V> distanceFn) {
    243
    244         final double dist = distanceFn.applyAsDouble(line, center);
    245
    246         final int cmp = precision.compare(dist, radius);
    247         if (cmp <= 0) {
    248             // on the boundary or inside the n-sphere
    249             final double abscissa = abscissaFn.applyAsDouble(line, center);
    250             final double abscissaDelta = Math.sqrt((radius * radius) - (dist * dist));
    251
    252             return line.toSpace(Vector1D.of(abscissa - abscissaDelta));
    253         }
    254
    255         return null;
    256     }
    257 }