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.spherical.twod; 18 19 import java.util.ArrayList; 20 import java.util.IdentityHashMap; 21 import java.util.List; 22 import java.util.Map; 23 24 import org.apache.commons.math3.exception.MathIllegalStateException; 25 import org.apache.commons.math3.exception.util.LocalizedFormats; 26 import org.apache.commons.math3.geometry.euclidean.threed.Vector3D; 27 import org.apache.commons.math3.geometry.partitioning.BSPTree; 28 import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor; 29 import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute; 30 import org.apache.commons.math3.geometry.spherical.oned.Arc; 31 import org.apache.commons.math3.geometry.spherical.oned.ArcsSet; 32 import org.apache.commons.math3.geometry.spherical.oned.S1Point; 33 34 /** Visitor building edges. 35 * @since 3.3 36 */ 37 class EdgesBuilder implements BSPTreeVisitor<Sphere2D> { 38 39 /** Root of the tree. */ 40 private final BSPTree<Sphere2D> root; 41 42 /** Tolerance below which points are consider to be identical. */ 43 private final double tolerance; 44 45 /** Built edges and their associated nodes. */ 46 private final Map<Edge, BSPTree<Sphere2D>> edgeToNode; 47 48 /** Reversed map. */ 49 private final Map<BSPTree<Sphere2D>, List<Edge>> nodeToEdgesList; 50 51 /** Simple constructor. 52 * @param root tree root 53 * @param tolerance below which points are consider to be identical 54 */ EdgesBuilder(final BSPTree<Sphere2D> root, final double tolerance)55 EdgesBuilder(final BSPTree<Sphere2D> root, final double tolerance) { 56 this.root = root; 57 this.tolerance = tolerance; 58 this.edgeToNode = new IdentityHashMap<Edge, BSPTree<Sphere2D>>(); 59 this.nodeToEdgesList = new IdentityHashMap<BSPTree<Sphere2D>, List<Edge>>(); 60 } 61 62 /** {@inheritDoc} */ visitOrder(final BSPTree<Sphere2D> node)63 public Order visitOrder(final BSPTree<Sphere2D> node) { 64 return Order.MINUS_SUB_PLUS; 65 } 66 67 /** {@inheritDoc} */ visitInternalNode(final BSPTree<Sphere2D> node)68 public void visitInternalNode(final BSPTree<Sphere2D> node) { 69 nodeToEdgesList.put(node, new ArrayList<Edge>()); 70 @SuppressWarnings("unchecked") 71 final BoundaryAttribute<Sphere2D> attribute = (BoundaryAttribute<Sphere2D>) node.getAttribute(); 72 if (attribute.getPlusOutside() != null) { 73 addContribution((SubCircle) attribute.getPlusOutside(), false, node); 74 } 75 if (attribute.getPlusInside() != null) { 76 addContribution((SubCircle) attribute.getPlusInside(), true, node); 77 } 78 } 79 80 /** {@inheritDoc} */ visitLeafNode(final BSPTree<Sphere2D> node)81 public void visitLeafNode(final BSPTree<Sphere2D> node) { 82 } 83 84 /** Add the contribution of a boundary edge. 85 * @param sub boundary facet 86 * @param reversed if true, the facet has the inside on its plus side 87 * @param node node to which the edge belongs 88 */ addContribution(final SubCircle sub, final boolean reversed, final BSPTree<Sphere2D> node)89 private void addContribution(final SubCircle sub, final boolean reversed, 90 final BSPTree<Sphere2D> node) { 91 final Circle circle = (Circle) sub.getHyperplane(); 92 final List<Arc> arcs = ((ArcsSet) sub.getRemainingRegion()).asList(); 93 for (final Arc a : arcs) { 94 final Vertex start = new Vertex((S2Point) circle.toSpace(new S1Point(a.getInf()))); 95 final Vertex end = new Vertex((S2Point) circle.toSpace(new S1Point(a.getSup()))); 96 start.bindWith(circle); 97 end.bindWith(circle); 98 final Edge edge; 99 if (reversed) { 100 edge = new Edge(end, start, a.getSize(), circle.getReverse()); 101 } else { 102 edge = new Edge(start, end, a.getSize(), circle); 103 } 104 edgeToNode.put(edge, node); 105 nodeToEdgesList.get(node).add(edge); 106 } 107 } 108 109 /** Get the edge that should naturally follow another one. 110 * @param previous edge to be continued 111 * @return other edge, starting where the previous one ends (they 112 * have not been connected yet) 113 * @exception MathIllegalStateException if there is not a single other edge 114 */ getFollowingEdge(final Edge previous)115 private Edge getFollowingEdge(final Edge previous) 116 throws MathIllegalStateException { 117 118 // get the candidate nodes 119 final S2Point point = previous.getEnd().getLocation(); 120 final List<BSPTree<Sphere2D>> candidates = root.getCloseCuts(point, tolerance); 121 122 // the following edge we are looking for must start from one of the candidates nodes 123 double closest = tolerance; 124 Edge following = null; 125 for (final BSPTree<Sphere2D> node : candidates) { 126 for (final Edge edge : nodeToEdgesList.get(node)) { 127 if (edge != previous && edge.getStart().getIncoming() == null) { 128 final Vector3D edgeStart = edge.getStart().getLocation().getVector(); 129 final double gap = Vector3D.angle(point.getVector(), edgeStart); 130 if (gap <= closest) { 131 closest = gap; 132 following = edge; 133 } 134 } 135 } 136 } 137 138 if (following == null) { 139 final Vector3D previousStart = previous.getStart().getLocation().getVector(); 140 if (Vector3D.angle(point.getVector(), previousStart) <= tolerance) { 141 // the edge connects back to itself 142 return previous; 143 } 144 145 // this should never happen 146 throw new MathIllegalStateException(LocalizedFormats.OUTLINE_BOUNDARY_LOOP_OPEN); 147 148 } 149 150 return following; 151 152 } 153 154 /** Get the boundary edges. 155 * @return boundary edges 156 * @exception MathIllegalStateException if there is not a single other edge 157 */ getEdges()158 public List<Edge> getEdges() throws MathIllegalStateException { 159 160 // connect the edges 161 for (final Edge previous : edgeToNode.keySet()) { 162 previous.setNextEdge(getFollowingEdge(previous)); 163 } 164 165 return new ArrayList<Edge>(edgeToNode.keySet()); 166 167 } 168 169 } 170