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.List; 20 21 import org.apache.commons.math3.geometry.euclidean.threed.Vector3D; 22 import org.apache.commons.math3.geometry.spherical.oned.Arc; 23 import org.apache.commons.math3.util.FastMath; 24 import org.apache.commons.math3.util.MathUtils; 25 26 /** Spherical polygons boundary edge. 27 * @see SphericalPolygonsSet#getBoundaryLoops() 28 * @see Vertex 29 * @since 3.3 30 */ 31 public class Edge { 32 33 /** Start vertex. */ 34 private final Vertex start; 35 36 /** End vertex. */ 37 private Vertex end; 38 39 /** Length of the arc. */ 40 private final double length; 41 42 /** Circle supporting the edge. */ 43 private final Circle circle; 44 45 /** Build an edge not contained in any node yet. 46 * @param start start vertex 47 * @param end end vertex 48 * @param length length of the arc (it can be greater than \( \pi \)) 49 * @param circle circle supporting the edge 50 */ Edge(final Vertex start, final Vertex end, final double length, final Circle circle)51 Edge(final Vertex start, final Vertex end, final double length, final Circle circle) { 52 53 this.start = start; 54 this.end = end; 55 this.length = length; 56 this.circle = circle; 57 58 // connect the vertices back to the edge 59 start.setOutgoing(this); 60 end.setIncoming(this); 61 62 } 63 64 /** Get start vertex. 65 * @return start vertex 66 */ getStart()67 public Vertex getStart() { 68 return start; 69 } 70 71 /** Get end vertex. 72 * @return end vertex 73 */ getEnd()74 public Vertex getEnd() { 75 return end; 76 } 77 78 /** Get the length of the arc. 79 * @return length of the arc (can be greater than \( \pi \)) 80 */ getLength()81 public double getLength() { 82 return length; 83 } 84 85 /** Get the circle supporting this edge. 86 * @return circle supporting this edge 87 */ getCircle()88 public Circle getCircle() { 89 return circle; 90 } 91 92 /** Get an intermediate point. 93 * <p> 94 * The angle along the edge should normally be between 0 and {@link #getLength()} 95 * in order to remain within edge limits. However, there are no checks on the 96 * value of the angle, so user can rebuild the full circle on which an edge is 97 * defined if they want. 98 * </p> 99 * @param alpha angle along the edge, counted from {@link #getStart()} 100 * @return an intermediate point 101 */ getPointAt(final double alpha)102 public Vector3D getPointAt(final double alpha) { 103 return circle.getPointAt(alpha + circle.getPhase(start.getLocation().getVector())); 104 } 105 106 /** Connect the instance with a following edge. 107 * @param next edge following the instance 108 */ setNextEdge(final Edge next)109 void setNextEdge(final Edge next) { 110 end = next.getStart(); 111 end.setIncoming(this); 112 end.bindWith(getCircle()); 113 } 114 115 /** Split the edge. 116 * <p> 117 * Once split, this edge is not referenced anymore by the vertices, 118 * it is replaced by the two or three sub-edges and intermediate splitting 119 * vertices are introduced to connect these sub-edges together. 120 * </p> 121 * @param splitCircle circle splitting the edge in several parts 122 * @param outsideList list where to put parts that are outside of the split circle 123 * @param insideList list where to put parts that are inside the split circle 124 */ split(final Circle splitCircle, final List<Edge> outsideList, final List<Edge> insideList)125 void split(final Circle splitCircle, 126 final List<Edge> outsideList, final List<Edge> insideList) { 127 128 // get the inside arc, synchronizing its phase with the edge itself 129 final double edgeStart = circle.getPhase(start.getLocation().getVector()); 130 final Arc arc = circle.getInsideArc(splitCircle); 131 final double arcRelativeStart = MathUtils.normalizeAngle(arc.getInf(), edgeStart + FastMath.PI) - edgeStart; 132 final double arcRelativeEnd = arcRelativeStart + arc.getSize(); 133 final double unwrappedEnd = arcRelativeEnd - MathUtils.TWO_PI; 134 135 // build the sub-edges 136 final double tolerance = circle.getTolerance(); 137 Vertex previousVertex = start; 138 if (unwrappedEnd >= length - tolerance) { 139 140 // the edge is entirely contained inside the circle 141 // we don't split anything 142 insideList.add(this); 143 144 } else { 145 146 // there are at least some parts of the edge that should be outside 147 // (even is they are later be filtered out as being too small) 148 double alreadyManagedLength = 0; 149 if (unwrappedEnd >= 0) { 150 // the start of the edge is inside the circle 151 previousVertex = addSubEdge(previousVertex, 152 new Vertex(new S2Point(circle.getPointAt(edgeStart + unwrappedEnd))), 153 unwrappedEnd, insideList, splitCircle); 154 alreadyManagedLength = unwrappedEnd; 155 } 156 157 if (arcRelativeStart >= length - tolerance) { 158 // the edge ends while still outside of the circle 159 if (unwrappedEnd >= 0) { 160 previousVertex = addSubEdge(previousVertex, end, 161 length - alreadyManagedLength, outsideList, splitCircle); 162 } else { 163 // the edge is entirely outside of the circle 164 // we don't split anything 165 outsideList.add(this); 166 } 167 } else { 168 // the edge is long enough to enter inside the circle 169 previousVertex = addSubEdge(previousVertex, 170 new Vertex(new S2Point(circle.getPointAt(edgeStart + arcRelativeStart))), 171 arcRelativeStart - alreadyManagedLength, outsideList, splitCircle); 172 alreadyManagedLength = arcRelativeStart; 173 174 if (arcRelativeEnd >= length - tolerance) { 175 // the edge ends while still inside of the circle 176 previousVertex = addSubEdge(previousVertex, end, 177 length - alreadyManagedLength, insideList, splitCircle); 178 } else { 179 // the edge is long enough to exit outside of the circle 180 previousVertex = addSubEdge(previousVertex, 181 new Vertex(new S2Point(circle.getPointAt(edgeStart + arcRelativeStart))), 182 arcRelativeStart - alreadyManagedLength, insideList, splitCircle); 183 alreadyManagedLength = arcRelativeStart; 184 previousVertex = addSubEdge(previousVertex, end, 185 length - alreadyManagedLength, outsideList, splitCircle); 186 } 187 } 188 189 } 190 191 } 192 193 /** Add a sub-edge to a list if long enough. 194 * <p> 195 * If the length of the sub-edge to add is smaller than the {@link Circle#getTolerance()} 196 * tolerance of the support circle, it will be ignored. 197 * </p> 198 * @param subStart start of the sub-edge 199 * @param subEnd end of the sub-edge 200 * @param subLength length of the sub-edge 201 * @param splitCircle circle splitting the edge in several parts 202 * @param list list where to put the sub-edge 203 * @return end vertex of the edge ({@code subEnd} if the edge was long enough and really 204 * added, {@code subStart} if the edge was too small and therefore ignored) 205 */ addSubEdge(final Vertex subStart, final Vertex subEnd, final double subLength, final List<Edge> list, final Circle splitCircle)206 private Vertex addSubEdge(final Vertex subStart, final Vertex subEnd, final double subLength, 207 final List<Edge> list, final Circle splitCircle) { 208 209 if (subLength <= circle.getTolerance()) { 210 // the edge is too short, we ignore it 211 return subStart; 212 } 213 214 // really add the edge 215 subEnd.bindWith(splitCircle); 216 final Edge edge = new Edge(subStart, subEnd, subLength, circle); 217 list.add(edge); 218 return subEnd; 219 220 } 221 222 } 223