svn-gvsig-desktop / trunk / org.gvsig.desktop / org.gvsig.desktop.plugin / org.gvsig.editing.app / org.gvsig.editing.app.mainplugin / src / main / java / org / gvsig / editing / gui / cad / tools / split / SplitGraph.java @ 40557
History | View | Annotate | Download (10.7 KB)
1 |
/**
|
---|---|
2 |
* gvSIG. Desktop Geographic Information System.
|
3 |
*
|
4 |
* Copyright (C) 2007-2013 gvSIG Association.
|
5 |
*
|
6 |
* This program is free software; you can redistribute it and/or
|
7 |
* modify it under the terms of the GNU General Public License
|
8 |
* as published by the Free Software Foundation; either version 3
|
9 |
* of the License, or (at your option) any later version.
|
10 |
*
|
11 |
* This program is distributed in the hope that it will be useful,
|
12 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
13 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
14 |
* GNU General Public License for more details.
|
15 |
*
|
16 |
* You should have received a copy of the GNU General Public License
|
17 |
* along with this program; if not, write to the Free Software
|
18 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
|
19 |
* MA 02110-1301, USA.
|
20 |
*
|
21 |
* For any additional information, do not hesitate to contact us
|
22 |
* at info AT gvsig.com, or visit our website www.gvsig.com.
|
23 |
*/
|
24 |
/* Spatial Operations & Editing Tools for uDig
|
25 |
*
|
26 |
* Axios Engineering under a funding contract with:
|
27 |
* Diputación Foral de Gipuzkoa, Ordenación Territorial
|
28 |
*
|
29 |
* http://b5m.gipuzkoa.net
|
30 |
* http://www.axios.es
|
31 |
*
|
32 |
* (C) 2006, Diputación Foral de Gipuzkoa, Ordenación Territorial (DFG-OT).
|
33 |
* DFG-OT agrees to licence under Lesser General Public License (LGPL).
|
34 |
*
|
35 |
* You can redistribute it and/or modify it under the terms of the
|
36 |
* GNU Lesser General Public License as published by the Free Software
|
37 |
* Foundation; version 2.1 of the License.
|
38 |
*
|
39 |
* This library is distributed in the hope that it will be useful,
|
40 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
41 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
42 |
* Lesser General Public License for more details.
|
43 |
*/
|
44 |
package org.gvsig.editing.gui.cad.tools.split; |
45 |
|
46 |
import java.util.ArrayList; |
47 |
import java.util.List; |
48 |
|
49 |
import org.slf4j.LoggerFactory; |
50 |
|
51 |
import com.vividsolutions.jts.geom.Coordinate; |
52 |
import com.vividsolutions.jts.geom.CoordinateArrays; |
53 |
import com.vividsolutions.jts.geom.Geometry; |
54 |
import com.vividsolutions.jts.geom.GeometryFactory; |
55 |
import com.vividsolutions.jts.geom.LineString; |
56 |
import com.vividsolutions.jts.geom.Location; |
57 |
import com.vividsolutions.jts.geom.Point; |
58 |
import com.vividsolutions.jts.geom.Polygon; |
59 |
import com.vividsolutions.jts.geomgraph.DirectedEdge; |
60 |
import com.vividsolutions.jts.geomgraph.Edge; |
61 |
import com.vividsolutions.jts.geomgraph.Label; |
62 |
import com.vividsolutions.jts.geomgraph.NodeFactory; |
63 |
import com.vividsolutions.jts.geomgraph.PlanarGraph; |
64 |
import com.vividsolutions.jts.geomgraph.Position; |
65 |
import com.vividsolutions.jts.geomgraph.Quadrant; |
66 |
|
67 |
/**
|
68 |
* A {@link PlanarGraph} that builds itself from a {@link Polygon} and a
|
69 |
* {@link LineString splitting line}.
|
70 |
* <p>
|
71 |
* The resulting graph will have the following characteristics:
|
72 |
* <ul>
|
73 |
* <li>It will contain as many edges as linestrings in the boundary of the intersection geometry
|
74 |
* between the polygon and the splitting line string.
|
75 |
* <li>All edges will be labelled {@link Location#BOUNDARY} at {@link Position#ON}</li>
|
76 |
* <li>The edges from the polygon's exterior ring will be labelled {@link Location#EXTERIOR} at the
|
77 |
* {@link Position#LEFT}, {@link Location#INTERIOR} at {@link Position#RIGHT}</li>
|
78 |
* <li>The edges from the polygon's holes will be labelled {@link Location#INTERIOR} at the
|
79 |
* {@link Position#LEFT}, {@link Location#EXTERIOR} at {@link Position#RIGHT}</li>
|
80 |
* </ul>
|
81 |
* <p>
|
82 |
* Note the provided polygon may result modified as the result of {@link Polygon#normalize()},
|
83 |
* which is called in order to ensure propper orientation of the shell and holes.
|
84 |
* </p>
|
85 |
* </p>
|
86 |
*
|
87 |
* @author Gabriel Roldán, Axios Engineering
|
88 |
* @author Mauricio Pazos, Axios Engineering
|
89 |
* @since 1.1.0
|
90 |
*/
|
91 |
class SplitGraph extends PlanarGraph { |
92 |
|
93 |
private static final NodeFactory NODE_FACTORY = new SplitGraphNodeFactory(); |
94 |
|
95 |
private final Polygon polygon; |
96 |
|
97 |
private final LineString splitter; |
98 |
|
99 |
public SplitGraph( Polygon polygon, LineString splitter ) { |
100 |
super(NODE_FACTORY);
|
101 |
this.polygon = polygon;
|
102 |
// after normalize() we know the shell is oriented CW and the holes CCW
|
103 |
this.polygon.normalize();
|
104 |
|
105 |
this.splitter = normalizeSplitter(splitter);
|
106 |
buildGraph(); |
107 |
} |
108 |
|
109 |
private LineString normalizeSplitter( final LineString original ) { |
110 |
// ensure the splitter has no endpoints lying inside the polygon
|
111 |
LineString splitter = removeInteriorEndPoints(polygon, original); |
112 |
// endure the splitter is directed clockwise, as its going
|
113 |
// to become part of the shell boundary when the tesselation
|
114 |
// process eliminates other shell edges from the graph
|
115 |
Coordinate[] splitterCoords = splitter.getCoordinates();
|
116 |
Coordinate coord0 = splitterCoords[0];
|
117 |
Coordinate coord1 = splitterCoords[1];
|
118 |
|
119 |
// determine the orientation of the coordinate sequence given the
|
120 |
// quadrant of its first vector
|
121 |
// 1 | 0
|
122 |
// --+--
|
123 |
// 2 | 3
|
124 |
final int quadrant = Quadrant.quadrant(coord0, coord1); |
125 |
boolean isCounterClockWise = 1 == quadrant || 2 == quadrant; |
126 |
if (isCounterClockWise) {
|
127 |
CoordinateArrays.reverse(splitterCoords); |
128 |
GeometryFactory gf = original.getFactory(); |
129 |
splitter = gf.createLineString(splitterCoords); |
130 |
} |
131 |
return splitter;
|
132 |
} |
133 |
|
134 |
/**
|
135 |
* Removes the given edge and its related {@link DirectedEdge}'s from this graph
|
136 |
*
|
137 |
* @param edge the edge to remove
|
138 |
* @throws IllegalArgumentException if no enclosing DirectedEdge is found for <code>edge</code>
|
139 |
* @see #remove(DirectedEdge)
|
140 |
*/
|
141 |
public void remove( final SplitEdge edge ) { |
142 |
DirectedEdge edgeEnd = (DirectedEdge) findEdgeEnd(edge); |
143 |
if (edgeEnd == null) { |
144 |
throw new IllegalArgumentException("No enclosing edge end found for " + edge); |
145 |
} |
146 |
remove(edgeEnd); |
147 |
} |
148 |
|
149 |
/**
|
150 |
* Removes a DirectedEdge, its sym and its {@link SplitEdge} from this graph. May lead to the
|
151 |
* graph containing dangling nodes.
|
152 |
*
|
153 |
* @param edgeEnd
|
154 |
*/
|
155 |
public void remove( final DirectedEdge edgeEnd ) { |
156 |
if (edgeEnd == null) { |
157 |
throw new NullPointerException(); |
158 |
} |
159 |
if (edgeEndList.remove(edgeEnd)) {
|
160 |
DirectedEdge sym = edgeEnd.getSym(); |
161 |
edgeEndList.remove(sym); |
162 |
|
163 |
// shared edge between both ends
|
164 |
Edge edge = edgeEnd.getEdge(); |
165 |
edges.remove(edge); |
166 |
|
167 |
// node of directed edge end
|
168 |
SplitGraphNode node = (SplitGraphNode) edgeEnd.getNode(); |
169 |
// node of symetric directed edge end
|
170 |
SplitGraphNode endNode = (SplitGraphNode) sym.getNode(); |
171 |
node.remove(edgeEnd); |
172 |
endNode.remove(sym); |
173 |
} |
174 |
} |
175 |
|
176 |
/**
|
177 |
* Builds a linestrnig from splitter such that it contains no endpoints lying inside the polygon
|
178 |
*
|
179 |
* @param polygon
|
180 |
* @param splitter
|
181 |
* @return
|
182 |
*/
|
183 |
private LineString removeInteriorEndPoints( Polygon polygon, LineString splitter ) { |
184 |
final Coordinate[] coords = splitter.getCoordinates(); |
185 |
final GeometryFactory gf = splitter.getFactory();
|
186 |
int useFrom;
|
187 |
int useTo;
|
188 |
|
189 |
for( useFrom = 0; useFrom < coords.length; useFrom++ ) { |
190 |
Point p = gf.createPoint(coords[useFrom]);
|
191 |
if (!polygon.contains(p)) {
|
192 |
break;
|
193 |
} |
194 |
} |
195 |
for( useTo = coords.length - 1; useTo >= useFrom; useTo-- ) { |
196 |
Point p = gf.createPoint(coords[useTo]);
|
197 |
if (!polygon.contains(p)) {
|
198 |
break;
|
199 |
} |
200 |
} |
201 |
|
202 |
if (useFrom == useTo) {
|
203 |
throw new IllegalArgumentException("Line lies completely inside polygon"); |
204 |
} |
205 |
|
206 |
int length = 1 + (useTo - useFrom); |
207 |
Coordinate[] crossingLineCoords = new Coordinate[length]; |
208 |
System.arraycopy(coords, useFrom, crossingLineCoords, 0, length); |
209 |
LineString surelyCrossingLine = gf.createLineString(crossingLineCoords); |
210 |
return surelyCrossingLine;
|
211 |
} |
212 |
|
213 |
/**
|
214 |
* <pre>
|
215 |
* <code>
|
216 |
*
|
217 |
* +----------o-----------+
|
218 |
* | | |
|
219 |
* | | |
|
220 |
* | +-----------+ |
|
221 |
* | | | | |
|
222 |
* | | | | |
|
223 |
* | | | | |
|
224 |
* | o__\__o_____| |
|
225 |
* | / | |
|
226 |
* /|\ /|\ |
|
227 |
* o__________o___________|
|
228 |
*
|
229 |
*
|
230 |
* </code>
|
231 |
* </pre>
|
232 |
*
|
233 |
* @throws Exception
|
234 |
*/
|
235 |
private void buildGraph() { |
236 |
Geometry intersectingLineStrings = polygon.intersection(splitter); |
237 |
Geometry nodedShell = polygon.getExteriorRing().difference(splitter); |
238 |
|
239 |
LineString[] interiorRings = new LineString[polygon.getNumInteriorRing()]; |
240 |
for( int i = 0; i < polygon.getNumInteriorRing(); i++ ) { |
241 |
LineString interiorRingN = polygon.getInteriorRingN(i); |
242 |
interiorRings[i] = interiorRingN; |
243 |
} |
244 |
GeometryFactory factory = polygon.getFactory(); |
245 |
Geometry interiorRingCollection = factory.createMultiLineString(interiorRings); |
246 |
Geometry nodedHoles = interiorRingCollection.difference(splitter); |
247 |
|
248 |
// shell segments oriented CW means exterior at the left, interior at
|
249 |
// the right
|
250 |
addEdges(nodedShell, Location.BOUNDARY, Location.EXTERIOR, Location.INTERIOR); |
251 |
// hole segments oriented CCW means interior at the left, exterior at
|
252 |
// the right
|
253 |
addEdges(nodedHoles, Location.BOUNDARY, Location.INTERIOR, Location.EXTERIOR); |
254 |
// splitter intersection segments have interior location at both left
|
255 |
// and right
|
256 |
addEdges(intersectingLineStrings, Location.BOUNDARY, Location.INTERIOR, Location.INTERIOR); |
257 |
} |
258 |
|
259 |
private void addEdges( Geometry linearGeom, int onLoc, int leftLoc, int rightLoc ) { |
260 |
final int nParts = linearGeom.getNumGeometries(); |
261 |
Geometry currGeom; |
262 |
Coordinate[] coords;
|
263 |
List edges = new ArrayList(); |
264 |
for( int i = 0; i < nParts; i++ ) { |
265 |
currGeom = linearGeom.getGeometryN(i); |
266 |
coords = currGeom.getCoordinates(); |
267 |
if (coords.length<2) |
268 |
continue;
|
269 |
Label label = new Label(onLoc, leftLoc, rightLoc); |
270 |
Edge edge = new SplitEdge(coords, label);
|
271 |
edges.add(edge); |
272 |
} |
273 |
// for each edge in the list, adds two DirectedEdge, one reflecting
|
274 |
// the given edge and other the opposite
|
275 |
try{
|
276 |
super.addEdges(edges);
|
277 |
}catch (Exception e) { |
278 |
LoggerFactory.getLogger(this.getClass()).error(e.getLocalizedMessage(),e);
|
279 |
} |
280 |
} |
281 |
|
282 |
} |