1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.geometry.core.partitioning.bsp; 18 19 import java.util.Collections; 20 import java.util.Iterator; 21 import java.util.List; 22 23 import org.apache.commons.geometry.core.Point; 24 import org.apache.commons.geometry.core.Sized; 25 import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset; 26 27 /** Class representing the portion of an 28 * {@link AbstractRegionBSPTree.AbstractRegionNode AbstractRegionNode}'s cut that 29 * lies on the boundary of the region. Portions of the node cut may be oriented so 30 * that the plus side of the cut points toward the outside of the region 31 * ({@link #getOutsideFacing()}) and other portions toward the inside of the 32 * region ({@link #getInsideFacing()}). The inside-facing and outside-facing portions 33 * of the region boundary are represented as lists of disjoint hyperplane convex subsets, 34 * all originating from the same hyperplane convex subset forming the node cut. 35 * 36 * @param <P> Point implementation type 37 */ 38 public final class RegionCutBoundary<P extends Point<P>> implements Sized { 39 40 /** Portion of the cut oriented such that the plus side of the cut points to the inside of the region. */ 41 private final List<HyperplaneConvexSubset<P>> insideFacing; 42 43 /** Portion of the cut oriented such that the plus side of the cut points to the outside of the region. */ 44 private final List<HyperplaneConvexSubset<P>> outsideFacing; 45 46 /** Construct a new instance from the inside-facing and outside-facing portions of a node cut. The 47 * given lists are expected to be disjoint regions originating from the same hyperplane convex subset. 48 * No validation is performed. 49 * @param insideFacing the inside-facing portion of the node cut 50 * @param outsideFacing the outside-facing portion of the node cut 51 */ 52 RegionCutBoundary(final List<HyperplaneConvexSubset<P>> insideFacing, 53 final List<HyperplaneConvexSubset<P>> outsideFacing) { 54 this.insideFacing = insideFacing != null ? 55 Collections.unmodifiableList(insideFacing) : 56 Collections.emptyList(); 57 58 this.outsideFacing = outsideFacing != null ? 59 Collections.unmodifiableList(outsideFacing) : 60 Collections.emptyList(); 61 } 62 63 /** Get the portion of the cut with its plus side facing the inside of the region. 64 * @return the portion of the cut with its plus side facing the 65 * inside of the region 66 */ 67 public List<HyperplaneConvexSubset<P>> getInsideFacing() { 68 return insideFacing; 69 } 70 71 /** Get the portion of the cut with its plus side facing the outside of the region. 72 * @return the portion of the cut with its plus side facing the 73 * outside of the region 74 */ 75 public List<HyperplaneConvexSubset<P>> getOutsideFacing() { 76 return outsideFacing; 77 } 78 79 /** Get the total size of the cut boundary, including inside and outside facing components. 80 * @return the total size of the cut boundary, including inside and outside facing components 81 */ 82 @Override 83 public double getSize() { 84 return getTotalSize(insideFacing) + getTotalSize(outsideFacing); 85 } 86 87 /** Get the total size of all boundaries in the given list. 88 * @param boundaries boundaries to compute the size for 89 * @return the total size of all boundaries in the given list 90 */ 91 private double getTotalSize(final List<? extends HyperplaneConvexSubset<P>> boundaries) { 92 double total = 0.0; 93 for (final HyperplaneConvexSubset<P> boundary : boundaries) { 94 total += boundary.getSize(); 95 96 if (Double.isInfinite(total)) { 97 return total; 98 } 99 } 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 }