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.math3.geometry.partitioning; 18 19 import java.util.ArrayList; 20 import java.util.List; 21 22 import org.apache.commons.math3.geometry.Point; 23 import org.apache.commons.math3.geometry.Space; 24 import org.apache.commons.math3.geometry.partitioning.Region.Location; 25 import org.apache.commons.math3.util.FastMath; 26 27 /** Local tree visitor to compute projection on boundary. 28 * @param <S> Type of the space. 29 * @param <T> Type of the sub-space. 30 * @since 3.3 31 */ 32 class BoundaryProjector<S extends Space, T extends Space> implements BSPTreeVisitor<S> { 33 34 /** Original point. */ 35 private final Point<S> original; 36 37 /** Current best projected point. */ 38 private Point<S> projected; 39 40 /** Leaf node closest to the test point. */ 41 private BSPTree<S> leaf; 42 43 /** Current offset. */ 44 private double offset; 45 46 /** Simple constructor. 47 * @param original original point 48 */ BoundaryProjector(final Point<S> original)49 BoundaryProjector(final Point<S> original) { 50 this.original = original; 51 this.projected = null; 52 this.leaf = null; 53 this.offset = Double.POSITIVE_INFINITY; 54 } 55 56 /** {@inheritDoc} */ visitOrder(final BSPTree<S> node)57 public Order visitOrder(final BSPTree<S> node) { 58 // we want to visit the tree so that the first encountered 59 // leaf is the one closest to the test point 60 if (node.getCut().getHyperplane().getOffset(original) <= 0) { 61 return Order.MINUS_SUB_PLUS; 62 } else { 63 return Order.PLUS_SUB_MINUS; 64 } 65 } 66 67 /** {@inheritDoc} */ visitInternalNode(final BSPTree<S> node)68 public void visitInternalNode(final BSPTree<S> node) { 69 70 // project the point on the cut sub-hyperplane 71 final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); 72 final double signedOffset = hyperplane.getOffset(original); 73 if (FastMath.abs(signedOffset) < offset) { 74 75 // project point 76 final Point<S> regular = hyperplane.project(original); 77 78 // get boundary parts 79 final List<Region<T>> boundaryParts = boundaryRegions(node); 80 81 // check if regular projection really belongs to the boundary 82 boolean regularFound = false; 83 for (final Region<T> part : boundaryParts) { 84 if (!regularFound && belongsToPart(regular, hyperplane, part)) { 85 // the projected point lies in the boundary 86 projected = regular; 87 offset = FastMath.abs(signedOffset); 88 regularFound = true; 89 } 90 } 91 92 if (!regularFound) { 93 // the regular projected point is not on boundary, 94 // so we have to check further if a singular point 95 // (i.e. a vertex in 2D case) is a possible projection 96 for (final Region<T> part : boundaryParts) { 97 final Point<S> spI = singularProjection(regular, hyperplane, part); 98 if (spI != null) { 99 final double distance = original.distance(spI); 100 if (distance < offset) { 101 projected = spI; 102 offset = distance; 103 } 104 } 105 } 106 107 } 108 109 } 110 111 } 112 113 /** {@inheritDoc} */ visitLeafNode(final BSPTree<S> node)114 public void visitLeafNode(final BSPTree<S> node) { 115 if (leaf == null) { 116 // this is the first leaf we visit, 117 // it is the closest one to the original point 118 leaf = node; 119 } 120 } 121 122 /** Get the projection. 123 * @return projection 124 */ getProjection()125 public BoundaryProjection<S> getProjection() { 126 127 // fix offset sign 128 offset = FastMath.copySign(offset, (Boolean) leaf.getAttribute() ? -1 : +1); 129 130 return new BoundaryProjection<S>(original, projected, offset); 131 132 } 133 134 /** Extract the regions of the boundary on an internal node. 135 * @param node internal node 136 * @return regions in the node sub-hyperplane 137 */ boundaryRegions(final BSPTree<S> node)138 private List<Region<T>> boundaryRegions(final BSPTree<S> node) { 139 140 final List<Region<T>> regions = new ArrayList<Region<T>>(2); 141 142 @SuppressWarnings("unchecked") 143 final BoundaryAttribute<S> ba = (BoundaryAttribute<S>) node.getAttribute(); 144 addRegion(ba.getPlusInside(), regions); 145 addRegion(ba.getPlusOutside(), regions); 146 147 return regions; 148 149 } 150 151 /** Add a boundary region to a list. 152 * @param sub sub-hyperplane defining the region 153 * @param list to fill up 154 */ addRegion(final SubHyperplane<S> sub, final List<Region<T>> list)155 private void addRegion(final SubHyperplane<S> sub, final List<Region<T>> list) { 156 if (sub != null) { 157 @SuppressWarnings("unchecked") 158 final Region<T> region = ((AbstractSubHyperplane<S, T>) sub).getRemainingRegion(); 159 if (region != null) { 160 list.add(region); 161 } 162 } 163 } 164 165 /** Check if a projected point lies on a boundary part. 166 * @param point projected point to check 167 * @param hyperplane hyperplane into which the point was projected 168 * @param part boundary part 169 * @return true if point lies on the boundary part 170 */ belongsToPart(final Point<S> point, final Hyperplane<S> hyperplane, final Region<T> part)171 private boolean belongsToPart(final Point<S> point, final Hyperplane<S> hyperplane, 172 final Region<T> part) { 173 174 // there is a non-null sub-space, we can dive into smaller dimensions 175 @SuppressWarnings("unchecked") 176 final Embedding<S, T> embedding = (Embedding<S, T>) hyperplane; 177 return part.checkPoint(embedding.toSubSpace(point)) != Location.OUTSIDE; 178 179 } 180 181 /** Get the projection to the closest boundary singular point. 182 * @param point projected point to check 183 * @param hyperplane hyperplane into which the point was projected 184 * @param part boundary part 185 * @return projection to a singular point of boundary part (may be null) 186 */ singularProjection(final Point<S> point, final Hyperplane<S> hyperplane, final Region<T> part)187 private Point<S> singularProjection(final Point<S> point, final Hyperplane<S> hyperplane, 188 final Region<T> part) { 189 190 // there is a non-null sub-space, we can dive into smaller dimensions 191 @SuppressWarnings("unchecked") 192 final Embedding<S, T> embedding = (Embedding<S, T>) hyperplane; 193 final BoundaryProjection<T> bp = part.projectToBoundary(embedding.toSubSpace(point)); 194 195 // back to initial dimension 196 return (bp.getProjected() == null) ? null : embedding.toSpace(bp.getProjected()); 197 198 } 199 200 } 201