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.math3.geometry.spherical.twod; 018 019import java.util.List; 020 021import org.apache.commons.math3.geometry.euclidean.threed.Vector3D; 022import org.apache.commons.math3.geometry.spherical.oned.Arc; 023import org.apache.commons.math3.util.FastMath; 024import org.apache.commons.math3.util.MathUtils; 025 026/** Spherical polygons boundary edge. 027 * @see SphericalPolygonsSet#getBoundaryLoops() 028 * @see Vertex 029 * @since 3.3 030 */ 031public class Edge { 032 033 /** Start vertex. */ 034 private final Vertex start; 035 036 /** End vertex. */ 037 private Vertex end; 038 039 /** Length of the arc. */ 040 private final double length; 041 042 /** Circle supporting the edge. */ 043 private final Circle circle; 044 045 /** Build an edge not contained in any node yet. 046 * @param start start vertex 047 * @param end end vertex 048 * @param length length of the arc (it can be greater than \( \pi \)) 049 * @param circle circle supporting the edge 050 */ 051 Edge(final Vertex start, final Vertex end, final double length, final Circle circle) { 052 053 this.start = start; 054 this.end = end; 055 this.length = length; 056 this.circle = circle; 057 058 // connect the vertices back to the edge 059 start.setOutgoing(this); 060 end.setIncoming(this); 061 062 } 063 064 /** Get start vertex. 065 * @return start vertex 066 */ 067 public Vertex getStart() { 068 return start; 069 } 070 071 /** Get end vertex. 072 * @return end vertex 073 */ 074 public Vertex getEnd() { 075 return end; 076 } 077 078 /** Get the length of the arc. 079 * @return length of the arc (can be greater than \( \pi \)) 080 */ 081 public double getLength() { 082 return length; 083 } 084 085 /** Get the circle supporting this edge. 086 * @return circle supporting this edge 087 */ 088 public Circle getCircle() { 089 return circle; 090 } 091 092 /** Get an intermediate point. 093 * <p> 094 * The angle along the edge should normally be between 0 and {@link #getLength()} 095 * in order to remain within edge limits. However, there are no checks on the 096 * value of the angle, so user can rebuild the full circle on which an edge is 097 * defined if they want. 098 * </p> 099 * @param alpha angle along the edge, counted from {@link #getStart()} 100 * @return an intermediate point 101 */ 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 */ 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 */ 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 */ 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}