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    *      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 org.apache.commons.geometry.core.Point;
20  
21  /** Interface for visiting the nodes in a {@link BSPTree} or {@link BSPSubtree}.
22   * @param <P> Point implementation type
23   * @param <N> BSP tree node implementation type
24   */
25  @FunctionalInterface
26  public interface BSPTreeVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>> {
27  
28      /** Enum used to specify the order in which visitors should visit the nodes
29       * in the tree.
30       */
31      enum Order {
32  
33          /** Indicates that the visitor should first visit the plus sub-tree, then
34           * the minus sub-tree and then the current node.
35           */
36          PLUS_MINUS_NODE,
37  
38          /** Indicates that the visitor should first visit the plus sub-tree, then
39           * the current node, and then the minus sub-tree.
40           */
41          PLUS_NODE_MINUS,
42  
43          /** Indicates that the visitor should first visit the minus sub-tree, then
44           * the plus sub-tree, and then the current node.
45           */
46          MINUS_PLUS_NODE,
47  
48          /** Indicates that the visitor should first visit the minus sub-tree, then the
49           * current node, and then the plus sub-tree.
50           */
51          MINUS_NODE_PLUS,
52  
53          /** Indicates that the visitor should first visit the current node, then the
54           * plus sub-tree, and then the minus sub-tree.
55           */
56          NODE_PLUS_MINUS,
57  
58          /** Indicates that the visitor should first visit the current node, then the
59           * minus sub-tree, and then the plus sub-tree.
60           */
61          NODE_MINUS_PLUS,
62  
63          /** Indicates that the visitor should not visit any of the nodes in this subtree. */
64          NONE
65      }
66  
67      /** Enum representing the result of a BSP tree node visit operation.
68       */
69      enum Result {
70  
71          /** Indicates that the visit operation should continue with the remaining nodes in
72           * the BSP tree.
73           */
74          CONTINUE,
75  
76          /** Indicates that the visit operation should terminate and not visit any further
77           * nodes in the tree.
78           */
79          TERMINATE
80      }
81  
82      /** Visit a node in a BSP tree. This method is called for both internal nodes and
83       * leaf nodes.
84       * @param node the node being visited
85       * @return the result of the visit operation
86       */
87      Result visit(N node);
88  
89      /** Determine the visit order for the given internal node. This is called for each
90       * internal node before {@link #visit(BSPTree.Node)} is called. Returning null
91       * or {@link Order#NONE}from this method skips the subtree rooted at the given node.
92       * This method is not called on leaf nodes.
93       * @param internalNode the internal node to determine the visit order for
94       * @return the order that the subtree rooted at the given node should be visited
95       */
96      default Order visitOrder(final N internalNode) {
97          return Order.NODE_MINUS_PLUS;
98      }
99  
100     /** Abstract class for {@link BSPTreeVisitor} implementations that base their visit
101      * ordering on a target point.
102      * @param <P> Point implementation type
103      * @param <N> BSP tree node implementation type
104      */
105     abstract class TargetPointVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
106         implements BSPTreeVisitor<P, N> {
107         /** Point serving as the target of the traversal. */
108         private final P target;
109 
110         /** Simple constructor.
111          * @param target the point serving as the target for the tree traversal
112          */
113         protected TargetPointVisitor(final P target) {
114             this.target = target;
115         }
116 
117         /** Get the target point for the tree traversal.
118          * @return the target point for the tree traversal
119          */
120         public P getTarget() {
121             return target;
122         }
123     }
124 
125     /** {@link BSPTreeVisitor} base class that orders tree nodes so that nodes closest to the target point are
126      * visited first. This is done by choosing {@link Order#MINUS_NODE_PLUS}
127      * when the target point lies on the minus side of the node's cut hyperplane and {@link Order#PLUS_NODE_MINUS}
128      * when it lies on the plus side. The order {@link Order#MINUS_NODE_PLUS} order is used when
129      * the target point lies directly on the node's cut hyerplane and no child node is closer than the other.
130      * @param <P> Point implementation type
131      * @param <N> BSP tree node implementation type
132      */
133     abstract class ClosestFirstVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
134         extends TargetPointVisitor<P, N> {
135         /** Simple constructor.
136          * @param target the point serving as the target for the traversal
137          */
138         protected ClosestFirstVisitor(final P target) {
139             super(target);
140         }
141 
142         /** {@inheritDoc} */
143         @Override
144         public Order visitOrder(final N node) {
145             if (node.getCutHyperplane().offset(getTarget()) > 0) {
146                 return Order.PLUS_NODE_MINUS;
147             }
148             return Order.MINUS_NODE_PLUS;
149         }
150     }
151 
152     /** {@link BSPTreeVisitor} base class that orders tree nodes so that nodes farthest from the target point
153      * are traversed first. This is done by choosing {@link Order#PLUS_NODE_MINUS}
154      * when the target point lies on the minus side of the node's cut hyperplane and {@link Order#MINUS_NODE_PLUS}
155      * when it lies on the plus side. The order {@link Order#MINUS_NODE_PLUS} order is used when
156      * the target point lies directly on the node's cut hyerplane and no child node is closer than the other.
157      * @param <P> Point implementation type
158      * @param <N> BSP tree node implementation type
159      */
160     abstract class FarthestFirstVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
161         extends TargetPointVisitor<P, N> {
162         /** Simple constructor.
163          * @param target the point serving as the target for the traversal
164          */
165         protected FarthestFirstVisitor(final P target) {
166             super(target);
167         }
168 
169         /** {@inheritDoc} */
170         @Override
171         public Order visitOrder(final N node) {
172             if (node.getCutHyperplane().offset(getTarget()) < 0) {
173                 return Order.PLUS_NODE_MINUS;
174             }
175             return Order.MINUS_NODE_PLUS;
176         }
177     }
178 }