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.core.partitioning;
018
019import java.util.List;
020
021import org.apache.commons.geometry.core.Point;
022import org.apache.commons.geometry.core.RegionLocation;
023import org.apache.commons.geometry.core.Sized;
024import org.apache.commons.geometry.core.Transform;
025
026/** Interface representing a subset of the points lying in a hyperplane. Examples include
027 * rays and line segments in Euclidean 2D space and triangular facets in Euclidean 3D space.
028 * Hyperplane subsets can have finite or infinite size and can represent contiguous regions
029 * of the hyperplane (as in the examples above); multiple, disjoint regions; or the
030 * {@link Hyperplane#span() entire hyperplane}.
031 *
032 * <p>This interface is very similar to the {@link org.apache.commons.geometry.core.Region Region}
033 * interface but has slightly different semantics. Whereas {@code Region} instances represent sets
034 * of points that can expand through all of the dimensions of a space, {@code HyperplaneSubset} instances
035 * are constrained to their containing hyperplane and are more accurately defined as {@code Region}s
036 * of the {@code n-1} dimension subspace defined by the hyperplane. This makes the methods of this interface
037 * have slightly different meanings as compared to their {@code Region} counterparts. For example, consider
038 * a triangular facet in Euclidean 3D space. The {@link #getSize()} method of this hyperplane subset does
039 * not return the <em>volume</em> of the instance (which would be {@code 0}) as a regular 3D region would, but
040 * rather returns the <em>area</em> of the 2D polygon defined by the facet. Similarly, the {@link #classify(Point)}
041 * method returns {@link RegionLocation#INSIDE} for points that lie inside of the 2D polygon defined by the
042 * facet, instead of the {@link RegionLocation#BOUNDARY} value that would be expected if the facet was considered
043 * as a true 3D region with zero thickness.
044 * </p>
045 *
046 * @param <P> Point implementation type
047 * @see Hyperplane
048 */
049public interface HyperplaneSubset<P extends Point<P>> extends Splittable<P, HyperplaneSubset<P>>, Sized {
050
051    /** Get the hyperplane containing this instance.
052     * @return the hyperplane containing this instance
053     */
054    Hyperplane<P> getHyperplane();
055
056    /** Return true if this instance contains all points in the
057     * hyperplane.
058     * @return true if this instance contains all points in the
059     *      hyperplane
060     */
061    boolean isFull();
062
063    /** Return true if this instance does not contain any points.
064     * @return true if this instance does not contain any points
065     */
066    boolean isEmpty();
067
068    /** Get the centroid, or geometric center, of the hyperplane subset or null
069     * if no centroid exists or one exists but is not unique. A centroid will not
070     * exist for empty or infinite subsets.
071     *
072     * <p>The centroid of a geometric object is defined as the mean position of
073     * all points in the object, including interior points, vertices, and other points
074     * lying on the boundary. If a physical object has a uniform density, then its center
075     * of mass is the same as its geometric centroid.
076     * </p>
077     * @return the centroid of the hyperplane subset or null if no unique centroid exists
078     * @see <a href="https://en.wikipedia.org/wiki/Centroid">Centroid</a>
079     */
080    P getCentroid();
081
082    /** Classify a point with respect to the subset region. The point is classified as follows:
083     * <ul>
084     *  <li>{@link RegionLocation#INSIDE INSIDE} - The point lies on the hyperplane
085     *      and inside of the subset region.</li>
086     *  <li>{@link RegionLocation#BOUNDARY BOUNDARY} - The point lies on the hyperplane
087     *      and is on the boundary of the subset region.</li>
088     *  <li>{@link RegionLocation#OUTSIDE OUTSIDE} - The point does not lie on
089     *      the hyperplane or it does lie on the hyperplane but is outside of the
090     *      subset region.</li>
091     * </ul>
092     * @param pt the point to classify
093     * @return classification of the point with respect to the hyperplane
094     *      and subspace region
095     */
096    RegionLocation classify(P pt);
097
098    /** Return true if the hyperplane subset contains the given point, meaning that the point
099     * lies on the hyperplane and is not on the outside of the subset region.
100     * @param pt the point to check
101     * @return true if the point is contained in the hyperplane subset
102     */
103    default boolean contains(final P pt) {
104        final RegionLocation loc = classify(pt);
105        return loc != null && loc != RegionLocation.OUTSIDE;
106    }
107
108    /** Return the closest point to the argument that is contained in the subset
109     * (ie, not classified as {@link RegionLocation#OUTSIDE outside}), or null if no
110     * such point exists.
111     * @param pt the reference point
112     * @return the closest point to the reference point that is contained in the subset,
113     *      or null if no such point exists
114     */
115    P closest(P pt);
116
117    /** Return a new hyperplane subset resulting from the application of the given transform.
118     * The current instance is not modified.
119     * @param transform the transform instance to apply
120     * @return new transformed hyperplane subset
121     */
122    HyperplaneSubset<P> transform(Transform<P> transform);
123
124    /** Convert this instance into a list of convex child subsets representing the same region.
125     * Implementations are not required to return an optimal convex subdivision of the current
126     * instance. They are free to return whatever subdivision is readily available.
127     * @return a list of hyperplane convex subsets representing the same subspace
128     *      region as this instance
129     */
130    List<? extends HyperplaneConvexSubset<P>> toConvex();
131}