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 public 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 public 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.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 public 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.0) { 173 return Order.PLUS_NODE_MINUS; 174 } 175 return Order.MINUS_NODE_PLUS; 176 } 177 } 178}