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