View Javadoc

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.euclidean.twod;
18  
19  import java.util.ArrayList;
20  import java.util.Iterator;
21  
22  import org.apache.commons.math3.exception.MathIllegalArgumentException;
23  import org.apache.commons.math3.exception.util.LocalizedFormats;
24  import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
25  import org.apache.commons.math3.geometry.partitioning.Region;
26  import org.apache.commons.math3.geometry.partitioning.RegionFactory;
27  import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
28  
29  /** This class represent a tree of nested 2D boundary loops.
30  
31   * <p>This class is used for piecewise polygons construction.
32   * Polygons are built using the outline edges as
33   * representative of boundaries, the orientation of these lines are
34   * meaningful. However, we want to allow the user to specify its
35   * outline loops without having to take care of this orientation. This
36   * class is devoted to correct mis-oriented loops.<p>
37  
38   * <p>Orientation is computed assuming the piecewise polygon is finite,
39   * i.e. the outermost loops have their exterior side facing points at
40   * infinity, and hence are oriented counter-clockwise. The orientation of
41   * internal loops is computed as the reverse of the orientation of
42   * their immediate surrounding loop.</p>
43  
44   * @version $Id: NestedLoops.java 1416643 2012-12-03 19:37:14Z tn $
45   * @since 3.0
46   */
47  class NestedLoops {
48  
49      /** Boundary loop. */
50      private Vector2D[] loop;
51  
52      /** Surrounded loops. */
53      private ArrayList<NestedLoops> surrounded;
54  
55      /** Polygon enclosing a finite region. */
56      private Region<Euclidean2D> polygon;
57  
58      /** Indicator for original loop orientation. */
59      private boolean originalIsClockwise;
60  
61      /** Simple Constructor.
62       * <p>Build an empty tree of nested loops. This instance will become
63       * the root node of a complete tree, it is not associated with any
64       * loop by itself, the outermost loops are in the root tree child
65       * nodes.</p>
66       */
67      public NestedLoops() {
68          surrounded = new ArrayList<NestedLoops>();
69      }
70  
71      /** Constructor.
72       * <p>Build a tree node with neither parent nor children</p>
73       * @param loop boundary loop (will be reversed in place if needed)
74       * @exception MathIllegalArgumentException if an outline has an open boundary loop
75       */
76      private NestedLoops(final Vector2D[] loop) throws MathIllegalArgumentException {
77  
78          if (loop[0] == null) {
79              throw new MathIllegalArgumentException(LocalizedFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
80          }
81  
82          this.loop = loop;
83          surrounded = new ArrayList<NestedLoops>();
84  
85          // build the polygon defined by the loop
86          final ArrayList<SubHyperplane<Euclidean2D>> edges = new ArrayList<SubHyperplane<Euclidean2D>>();
87          Vector2D current = loop[loop.length - 1];
88          for (int i = 0; i < loop.length; ++i) {
89              final Vector2D previous = current;
90              current = loop[i];
91              final Line   line   = new Line(previous, current);
92              final IntervalsSet region =
93                  new IntervalsSet(line.toSubSpace(previous).getX(), line.toSubSpace(current).getX());
94              edges.add(new SubLine(line, region));
95          }
96          polygon = new PolygonsSet(edges);
97  
98          // ensure the polygon encloses a finite region of the plane
99          if (Double.isInfinite(polygon.getSize())) {
100             polygon = new RegionFactory<Euclidean2D>().getComplement(polygon);
101             originalIsClockwise = false;
102         } else {
103             originalIsClockwise = true;
104         }
105 
106     }
107 
108     /** Add a loop in a tree.
109      * @param bLoop boundary loop (will be reversed in place if needed)
110      * @exception MathIllegalArgumentException if an outline has crossing
111      * boundary loops or open boundary loops
112      */
113     public void add(final Vector2D[] bLoop) throws MathIllegalArgumentException {
114         add(new NestedLoops(bLoop));
115     }
116 
117     /** Add a loop in a tree.
118      * @param node boundary loop (will be reversed in place if needed)
119      * @exception MathIllegalArgumentException if an outline has boundary
120      * loops that cross each other
121      */
122     private void add(final NestedLoops node) throws MathIllegalArgumentException {
123 
124         // check if we can go deeper in the tree
125         for (final NestedLoops child : surrounded) {
126             if (child.polygon.contains(node.polygon)) {
127                 child.add(node);
128                 return;
129             }
130         }
131 
132         // check if we can absorb some of the instance children
133         for (final Iterator<NestedLoops> iterator = surrounded.iterator(); iterator.hasNext();) {
134             final NestedLoops child = iterator.next();
135             if (node.polygon.contains(child.polygon)) {
136                 node.surrounded.add(child);
137                 iterator.remove();
138             }
139         }
140 
141         // we should be separate from the remaining children
142         RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>();
143         for (final NestedLoops child : surrounded) {
144             if (!factory.intersection(node.polygon, child.polygon).isEmpty()) {
145                 throw new MathIllegalArgumentException(LocalizedFormats.CROSSING_BOUNDARY_LOOPS);
146             }
147         }
148 
149         surrounded.add(node);
150 
151     }
152 
153     /** Correct the orientation of the loops contained in the tree.
154      * <p>This is this method that really inverts the loops that where
155      * provided through the {@link #add(Vector2D[]) add} method if
156      * they are mis-oriented</p>
157      */
158     public void correctOrientation() {
159         for (NestedLoops child : surrounded) {
160             child.setClockWise(true);
161         }
162     }
163 
164     /** Set the loop orientation.
165      * @param clockwise if true, the loop should be set to clockwise
166      * orientation
167      */
168     private void setClockWise(final boolean clockwise) {
169 
170         if (originalIsClockwise ^ clockwise) {
171             // we need to inverse the original loop
172             int min = -1;
173             int max = loop.length;
174             while (++min < --max) {
175                 final Vector2D tmp = loop[min];
176                 loop[min] = loop[max];
177                 loop[max] = tmp;
178             }
179         }
180 
181         // go deeper in the tree
182         for (final NestedLoops child : surrounded) {
183             child.setClockWise(!clockwise);
184         }
185 
186     }
187 
188 }