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.bsp;
018
019import java.util.Collections;
020import java.util.Iterator;
021import java.util.List;
022
023import org.apache.commons.geometry.core.Point;
024import org.apache.commons.geometry.core.Sized;
025import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
026
027/** Class representing the portion of an
028 * {@link AbstractRegionBSPTree.AbstractRegionNode AbstractRegionNode}'s cut that
029 * lies on the boundary of the region. Portions of the node cut may be oriented so
030 * that the plus side of the cut points toward the outside of the region
031 * ({@link #getOutsideFacing()}) and other portions toward the inside of the
032 * region ({@link #getInsideFacing()}). The inside-facing and outside-facing portions
033 * of the region boundary are represented as lists of disjoint hyperplane convex subsets,
034 * all originating from the same hyperplane convex subset forming the node cut.
035 *
036 * @param <P> Point implementation type
037 */
038public final class RegionCutBoundary<P extends Point<P>> implements Sized {
039
040    /** Portion of the cut oriented such that the plus side of the cut points to the inside of the region. */
041    private final List<HyperplaneConvexSubset<P>> insideFacing;
042
043    /** Portion of the cut oriented such that the plus side of the cut points to the outside of the region. */
044    private final List<HyperplaneConvexSubset<P>> outsideFacing;
045
046    /** Construct a new instance from the inside-facing and outside-facing portions of a node cut. The
047     * given lists are expected to be disjoint regions originating from the same hyperplane convex subset.
048     * No validation is performed.
049     * @param insideFacing the inside-facing portion of the node cut
050     * @param outsideFacing the outside-facing portion of the node cut
051     */
052    RegionCutBoundary(final List<HyperplaneConvexSubset<P>> insideFacing,
053            final List<HyperplaneConvexSubset<P>> outsideFacing) {
054        this.insideFacing = insideFacing != null ?
055                Collections.unmodifiableList(insideFacing) :
056                Collections.emptyList();
057
058        this.outsideFacing = outsideFacing != null ?
059                Collections.unmodifiableList(outsideFacing) :
060                Collections.emptyList();
061    }
062
063    /** Get the portion of the cut with its plus side facing the inside of the region.
064     * @return the portion of the cut with its plus side facing the
065     *      inside of the region
066     */
067    public List<HyperplaneConvexSubset<P>> getInsideFacing() {
068        return insideFacing;
069    }
070
071    /** Get the portion of the cut with its plus side facing the outside of the region.
072     * @return the portion of the cut with its plus side facing the
073     *      outside of the region
074     */
075    public List<HyperplaneConvexSubset<P>> getOutsideFacing() {
076        return outsideFacing;
077    }
078
079    /** Get the total size of the cut boundary, including inside and outside facing components.
080     * @return the total size of the cut boundary, including inside and outside facing components
081     */
082    @Override
083    public double getSize() {
084        return getTotalSize(insideFacing) + getTotalSize(outsideFacing);
085    }
086
087    /** Get the total size of all boundaries in the given list.
088     * @param boundaries boundaries to compute the size for
089     * @return the total size of all boundaries in the given list
090     */
091    private double getTotalSize(final List<? extends HyperplaneConvexSubset<P>> boundaries) {
092        double total = 0.0;
093        for (final HyperplaneConvexSubset<P> boundary : boundaries) {
094            total += boundary.getSize();
095
096            if (Double.isInfinite(total)) {
097                return total;
098            }
099        }
100
101        return total;
102    }
103
104    /** Return the closest point to the argument in the inside and outside facing
105     * portions of the cut boundary.
106     * @param pt the reference point
107     * @return the point in the cut boundary closest to the reference point
108     * @see HyperplaneConvexSubset#closest(Point)
109     */
110    public P closest(final P pt) {
111        P closest = null;
112        double closestDist = Double.POSITIVE_INFINITY;
113
114        final Iterator<HyperplaneConvexSubset<P>> insideIt = insideFacing.iterator();
115        final Iterator<HyperplaneConvexSubset<P>> outsideIt = outsideFacing.iterator();
116
117        HyperplaneConvexSubset<P> boundary;
118        P testPt;
119        double dist;
120
121        while (insideIt.hasNext() || outsideIt.hasNext()) {
122            boundary = insideIt.hasNext() ?
123                    insideIt.next() :
124                    outsideIt.next();
125
126            testPt = boundary.closest(pt);
127            dist = pt.distance(testPt);
128
129            if (closest == null || dist < closestDist) {
130                closest = testPt;
131                closestDist = dist;
132            }
133        }
134
135        return closest;
136    }
137
138    /** Return true if the given point is contained in the boundary, in either the
139     * inside facing portion or the outside facing portion.
140     * @param pt point to test
141     * @return true if the point is contained in the boundary
142     * @see HyperplaneConvexSubset#contains(Point)
143     */
144    public boolean contains(final P pt) {
145        return containsInsideFacing(pt) || containsOutsideFacing(pt);
146    }
147
148    /** Return true if the given point is contained in the inside-facing portion of
149     * the region boundary.
150     * @param pt point to test
151     * @return true if the point is contained in the inside-facing portion of the region
152     *      boundary
153     */
154    public boolean containsInsideFacing(final P pt) {
155        return anyContains(pt, insideFacing);
156    }
157
158    /** Return true if the given point is contained in the outside-facing portion of the
159     * region boundary.
160     * @param pt point to test
161     * @return true if the point is contained in the outside-facing portion of the region
162     *      boundary
163     */
164    public boolean containsOutsideFacing(final P pt) {
165        return anyContains(pt, outsideFacing);
166    }
167
168    /** Return true if the point is contained in any of the given boundaries.
169     * @param pt point to test
170     * @param boundaries
171     * @return true if the point is contained in any of the given boundaries
172     */
173    private boolean anyContains(final P pt, final List<? extends HyperplaneConvexSubset<P>> boundaries) {
174        for (final HyperplaneConvexSubset<P> boundary : boundaries) {
175            if (boundary.contains(pt)) {
176                return true;
177            }
178        }
179
180        return false;
181    }
182}