001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.geometry.euclidean;
018
019import java.util.Arrays;
020import java.util.Collections;
021import java.util.List;
022import java.util.Objects;
023import java.util.function.ToDoubleBiFunction;
024
025import org.apache.commons.geometry.core.Embedding;
026import org.apache.commons.geometry.core.Point;
027import org.apache.commons.geometry.core.Region;
028import org.apache.commons.geometry.core.RegionLocation;
029import org.apache.commons.geometry.euclidean.oned.Vector1D;
030import org.apache.commons.numbers.core.Precision;
031
032/** Abstract base class representing an n-sphere, which is a generalization of the ordinary 3 dimensional
033 * sphere to arbitrary dimensions.
034 * @param <V> Vector implementation type
035 * @see <a href="https://wikipedia.org/wiki/N-sphere">N-sphere</a>
036 */
037public abstract class AbstractNSphere<V extends EuclideanVector<V>> implements Region<V> {
038
039    /** The center point of the n-sphere. */
040    private final V center;
041
042    /** The radius of the n-sphere. */
043    private final double radius;
044
045    /** Precision object used to perform floating point comparisons. */
046    private final Precision.DoubleEquivalence precision;
047
048    /** Construct a new instance from its component parts.
049     * @param center the center point of the n-sphere
050     * @param radius the radius of the n-sphere
051     * @param precision precision context used to perform floating point comparisons
052     * @throws IllegalArgumentException if center is not finite or radius is not finite or is
053     *      less than or equal to zero as evaluated by the given precision context
054     */
055    protected AbstractNSphere(final V center, final double radius, final Precision.DoubleEquivalence precision) {
056        if (!center.isFinite()) {
057            throw new IllegalArgumentException("Illegal center point: " + center);
058        }
059        if (!Double.isFinite(radius) || precision.lte(radius, 0.0)) {
060            throw new IllegalArgumentException("Illegal radius: " + radius);
061        }
062
063        this.center = center;
064        this.radius = radius;
065        this.precision = precision;
066    }
067
068    /** Get the center point of the n-sphere.
069     * @return the center of the n-sphere
070     */
071    public V getCenter() {
072        return center;
073    }
074
075    /** Get the radius of the n-sphere.
076     * @return the radius of the n-sphere.
077     */
078    public double getRadius() {
079        return radius;
080    }
081
082    /** Get the precision object used to perform floating point
083     * comparisons for this instance.
084     * @return the precision object for this instance
085     */
086    public Precision.DoubleEquivalence getPrecision() {
087        return precision;
088    }
089
090    /** {@inheritDoc}
091    *
092    * <p>This method always returns {@code false}.</p>
093    */
094    @Override
095    public boolean isFull() {
096        return false;
097    }
098
099    /** {@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(30);
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}