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.math.geometry.euclidean.twod;
18
19 import java.util.ArrayList;
20 import java.util.Iterator;
21
22 import org.apache.commons.math.exception.MathIllegalArgumentException;
23 import org.apache.commons.math.exception.util.LocalizedFormats;
24 import org.apache.commons.math.geometry.euclidean.oned.IntervalsSet;
25 import org.apache.commons.math.geometry.partitioning.Region;
26 import org.apache.commons.math.geometry.partitioning.RegionFactory;
27 import org.apache.commons.math.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 1131153 2011-06-03 19:23:56Z luc $
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 }