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