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 org.apache.commons.geometry.core.Point;
020
021/** Interface for visiting the nodes in a {@link BSPTree} or {@link BSPSubtree}.
022 * @param <P> Point implementation type
023 * @param <N> BSP tree node implementation type
024 */
025@FunctionalInterface
026public interface BSPTreeVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>> {
027
028    /** Enum used to specify the order in which visitors should visit the nodes
029     * in the tree.
030     */
031    enum Order {
032
033        /** Indicates that the visitor should first visit the plus sub-tree, then
034         * the minus sub-tree and then the current node.
035         */
036        PLUS_MINUS_NODE,
037
038        /** Indicates that the visitor should first visit the plus sub-tree, then
039         * the current node, and then the minus sub-tree.
040         */
041        PLUS_NODE_MINUS,
042
043        /** Indicates that the visitor should first visit the minus sub-tree, then
044         * the plus sub-tree, and then the current node.
045         */
046        MINUS_PLUS_NODE,
047
048        /** Indicates that the visitor should first visit the minus sub-tree, then the
049         * current node, and then the plus sub-tree.
050         */
051        MINUS_NODE_PLUS,
052
053        /** Indicates that the visitor should first visit the current node, then the
054         * plus sub-tree, and then the minus sub-tree.
055         */
056        NODE_PLUS_MINUS,
057
058        /** Indicates that the visitor should first visit the current node, then the
059         * minus sub-tree, and then the plus sub-tree.
060         */
061        NODE_MINUS_PLUS,
062
063        /** Indicates that the visitor should not visit any of the nodes in this subtree. */
064        NONE
065    }
066
067    /** Enum representing the result of a BSP tree node visit operation.
068     */
069    enum Result {
070
071        /** Indicates that the visit operation should continue with the remaining nodes in
072         * the BSP tree.
073         */
074        CONTINUE,
075
076        /** Indicates that the visit operation should terminate and not visit any further
077         * nodes in the tree.
078         */
079        TERMINATE
080    }
081
082    /** Visit a node in a BSP tree. This method is called for both internal nodes and
083     * leaf nodes.
084     * @param node the node being visited
085     * @return the result of the visit operation
086     */
087    Result visit(N node);
088
089    /** Determine the visit order for the given internal node. This is called for each
090     * internal node before {@link #visit(BSPTree.Node)} is called. Returning null
091     * or {@link Order#NONE}from this method skips the subtree rooted at the given node.
092     * This method is not called on leaf nodes.
093     * @param internalNode the internal node to determine the visit order for
094     * @return the order that the subtree rooted at the given node should be visited
095     */
096    default Order visitOrder(final N internalNode) {
097        return Order.NODE_MINUS_PLUS;
098    }
099
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}