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}