EmbeddedTreeLineSubset.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.geometry.euclidean.twod;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.internal.HyperplaneSubsets;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;
import org.apache.commons.geometry.euclidean.oned.Interval;
import org.apache.commons.geometry.euclidean.oned.OrientedPoint;
import org.apache.commons.geometry.euclidean.oned.OrientedPoints;
import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
import org.apache.commons.geometry.euclidean.oned.Vector1D;
import org.apache.commons.geometry.euclidean.twod.Line.SubspaceTransform;
import org.apache.commons.numbers.core.Precision;

/** Class representing an arbitrary subset of a line using a {@link RegionBSPTree1D}.
 * This class can represent convex, non-convex, finite, infinite, and empty regions.
 *
 * <p>This class is mutable and <em>not</em> thread safe.</p>
 */
public final class EmbeddedTreeLineSubset extends LineSubset {
    /** The 1D region representing the area on the line. */
    private final RegionBSPTree1D region;

    /** Construct a new, empty subset for the given line.
     * @param line line defining the subset
     */
    public EmbeddedTreeLineSubset(final Line line) {
        this(line, false);
    }

    /** Construct a new subset for the given line. If {@code full}
     * is true, then the subset will cover the entire line; otherwise,
     * it will be empty.
     * @param line line defining the subset
     * @param full if true, the subset will cover the entire space;
     *      otherwise it will be empty
     */
    public EmbeddedTreeLineSubset(final Line line, final boolean full) {
        this(line, new RegionBSPTree1D(full));
    }

    /** Construct a new instance from its defining line and subspace region. The give
     * BSP tree is used directly by this instance; it is not copied.
     * @param line line defining the subset
     * @param region subspace region for the instance
     */
    public EmbeddedTreeLineSubset(final Line line, final RegionBSPTree1D region) {
        super(line);

        this.region = region;
    }

    /** {@inheritDoc} */
    @Override
    public boolean isFull() {
        return region.isFull();
    }

    /** {@inheritDoc} */
    @Override
    public boolean isEmpty() {
        return region.isEmpty();
    }

    /** {@inheritDoc} */
    @Override
    public double getSize() {
        return region.getSize();
    }

    /** {@inheritDoc} */
    @Override
    public Vector2D getCentroid() {
        final Vector1D subspaceCentroid = region.getCentroid();
        if (subspaceCentroid != null) {
            return getLine().toSpace(subspaceCentroid);
        }
        return null;
    }

    /** {@inheritDoc} */
    @Override
    public Bounds2D getBounds() {
        final double min = region.getMin();
        final double max = region.getMax();

        if (Double.isFinite(min) && Double.isFinite(max)) {
            final Line line = getLine();

            return Bounds2D.builder()
                    .add(line.toSpace(min))
                    .add(line.toSpace(max))
                    .build();
        }

        return null;
    }

    /** {@inheritDoc} */
    @Override
    public Vector2D closest(final Vector2D pt) {
        return HyperplaneSubsets.closestToEmbeddedRegion(pt, getLine(), region);
    }

    /** {@inheritDoc} */
    @Override
    public EmbeddedTreeLineSubset transform(final Transform<Vector2D> transform) {
        final SubspaceTransform st = getLine().subspaceTransform(transform);

        final RegionBSPTree1D tRegion = RegionBSPTree1D.empty();
        tRegion.copy(region);
        tRegion.transform(st.getTransform());

        return new EmbeddedTreeLineSubset(st.getLine(), tRegion);
    }

    /** {@inheritDoc} */
    @Override
    public List<LineConvexSubset> toConvex() {
        final List<Interval> intervals = region.toIntervals();

        final Line line = getLine();
        final List<LineConvexSubset> convexSubsets = new ArrayList<>(intervals.size());

        for (final Interval interval : intervals) {
            convexSubsets.add(Lines.subsetFromInterval(line, interval));
        }

        return convexSubsets;
    }

    /** {@inheritDoc} */
    @Override
    public RegionBSPTree1D getSubspaceRegion() {
        return region;
    }

    /** {@inheritDoc}
     *
     * <p>In all cases, the current instance is not modified. However, In order to avoid
     * unnecessary copying, this method will use the current instance as the split value when
     * the instance lies entirely on the plus or minus side of the splitter. For example, if
     * this instance lies entirely on the minus side of the splitter, the subplane
     * returned by {@link Split#getMinus()} will be this instance. Similarly, {@link Split#getPlus()}
     * will return the current instance if it lies entirely on the plus side. Callers need to make
     * special note of this, since this class is mutable.</p>
     */
    @Override
    public Split<EmbeddedTreeLineSubset> split(final Hyperplane<Vector2D> splitter) {
        final Line thisLine = getLine();
        final Line splitterLine = (Line) splitter;
        final Precision.DoubleEquivalence precision = getPrecision();

        final Vector2D intersection = splitterLine.intersection(thisLine);
        if (intersection == null) {
            return getNonIntersectingSplitResult(splitterLine, this);
        }

        final double abscissa = thisLine.abscissa(intersection);
        final OrientedPoint subspaceSplitter = OrientedPoints.fromLocationAndDirection(
                abscissa,
                splitterPlusIsPositiveFacing(splitterLine),
                precision);

        final Split<RegionBSPTree1D> subspaceSplit = region.split(subspaceSplitter);
        final SplitLocation subspaceSplitLoc = subspaceSplit.getLocation();

        if (SplitLocation.MINUS == subspaceSplitLoc) {
            return new Split<>(this, null);
        } else if (SplitLocation.PLUS == subspaceSplitLoc) {
            return new Split<>(null, this);
        }

        final EmbeddedTreeLineSubset minus = (subspaceSplit.getMinus() != null) ?
                new EmbeddedTreeLineSubset(thisLine, subspaceSplit.getMinus()) :
                null;
        final EmbeddedTreeLineSubset plus = (subspaceSplit.getPlus() != null) ?
                new EmbeddedTreeLineSubset(thisLine, subspaceSplit.getPlus()) :
                null;

        return new Split<>(minus, plus);
    }

    /** Add a line subset to this instance.
     * @param subset the line subset to add
     * @throws IllegalArgumentException if the given line subset is not from
     *      a line equivalent to this instance
     */
    public void add(final LineConvexSubset subset) {
        Lines.validateLinesEquivalent(getLine(), subset.getLine());

        region.add(subset.getInterval());
    }

    /** Add the region represented by the given line subset to this instance.
     * The argument is not modified.
     * @param subset line subset to add
     * @throws IllegalArgumentException if the given line subset is not from
     *      a line equivalent to this instance
     */
    public void add(final EmbeddedTreeLineSubset subset) {
        Lines.validateLinesEquivalent(getLine(), subset.getLine());

        region.union(subset.getSubspaceRegion());
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        final Line line = getLine();

        final StringBuilder sb = new StringBuilder();
        sb.append(this.getClass().getSimpleName())
            .append('[')
            .append("lineOrigin= ")
            .append(line.getOrigin())
            .append(", lineDirection= ")
            .append(line.getDirection())
            .append(", region= ")
            .append(region)
            .append(']');

        return sb.toString();
    }

    /** {@inheritDoc} */
    @Override
    RegionLocation classifyAbscissa(final double abscissa) {
        return region.classify(abscissa);
    }
}