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.twod;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.geometry.core.RegionLocation;
023import org.apache.commons.geometry.core.Transform;
024import org.apache.commons.geometry.core.internal.HyperplaneSubsets;
025import org.apache.commons.geometry.core.partitioning.Hyperplane;
026import org.apache.commons.geometry.core.partitioning.Split;
027import org.apache.commons.geometry.core.partitioning.SplitLocation;
028import org.apache.commons.geometry.euclidean.oned.Interval;
029import org.apache.commons.geometry.euclidean.oned.OrientedPoint;
030import org.apache.commons.geometry.euclidean.oned.OrientedPoints;
031import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
032import org.apache.commons.geometry.euclidean.oned.Vector1D;
033import org.apache.commons.geometry.euclidean.twod.Line.SubspaceTransform;
034import org.apache.commons.numbers.core.Precision;
035
036/** Class representing an arbitrary subset of a line using a {@link RegionBSPTree1D}.
037 * This class can represent convex, non-convex, finite, infinite, and empty regions.
038 *
039 * <p>This class is mutable and <em>not</em> thread safe.</p>
040 */
041public final class EmbeddedTreeLineSubset extends LineSubset {
042    /** The 1D region representing the area on the line. */
043    private final RegionBSPTree1D region;
044
045    /** Construct a new, empty subset for the given line.
046     * @param line line defining the subset
047     */
048    public EmbeddedTreeLineSubset(final Line line) {
049        this(line, false);
050    }
051
052    /** Construct a new subset for the given line. If {@code full}
053     * is true, then the subset will cover the entire line; otherwise,
054     * it will be empty.
055     * @param line line defining the subset
056     * @param full if true, the subset will cover the entire space;
057     *      otherwise it will be empty
058     */
059    public EmbeddedTreeLineSubset(final Line line, final boolean full) {
060        this(line, new RegionBSPTree1D(full));
061    }
062
063    /** Construct a new instance from its defining line and subspace region. The give
064     * BSP tree is used directly by this instance; it is not copied.
065     * @param line line defining the subset
066     * @param region subspace region for the instance
067     */
068    public EmbeddedTreeLineSubset(final Line line, final RegionBSPTree1D region) {
069        super(line);
070
071        this.region = region;
072    }
073
074    /** {@inheritDoc} */
075    @Override
076    public boolean isFull() {
077        return region.isFull();
078    }
079
080    /** {@inheritDoc} */
081    @Override
082    public boolean isEmpty() {
083        return region.isEmpty();
084    }
085
086    /** {@inheritDoc} */
087    @Override
088    public double getSize() {
089        return region.getSize();
090    }
091
092    /** {@inheritDoc} */
093    @Override
094    public Vector2D getCentroid() {
095        final Vector1D subspaceCentroid = region.getCentroid();
096        if (subspaceCentroid != null) {
097            return getLine().toSpace(subspaceCentroid);
098        }
099        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}