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 / SplitStrategy.java @ 42023
History | View | Annotate | Download (19.2 KB)
1 | 40557 | jjdelcerro | /**
|
---|---|---|---|
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 | 40435 | jjdelcerro | |
25 | |||
26 | package org.gvsig.editing.gui.cad.tools.split; |
||
27 | |||
28 | 42023 | jjdelcerro | /*
|
29 | * Based on portions of code from UDIG project.
|
||
30 | *
|
||
31 | * This class is based in the AXIOS team work for UDIG project.
|
||
32 | *
|
||
33 | * Adapted it slightly for the gvsig project
|
||
34 | * (exchange the I18 system, etc)
|
||
35 | */
|
||
36 | |||
37 | 40435 | jjdelcerro | import java.util.ArrayList; |
38 | import java.util.Collections; |
||
39 | import java.util.HashMap; |
||
40 | import java.util.Iterator; |
||
41 | import java.util.List; |
||
42 | import java.util.Map; |
||
43 | |||
44 | import com.vividsolutions.jts.algorithm.CGAlgorithms; |
||
45 | import com.vividsolutions.jts.geom.Coordinate; |
||
46 | import com.vividsolutions.jts.geom.CoordinateArrays; |
||
47 | import com.vividsolutions.jts.geom.Geometry; |
||
48 | import com.vividsolutions.jts.geom.GeometryCollection; |
||
49 | import com.vividsolutions.jts.geom.GeometryFactory; |
||
50 | import com.vividsolutions.jts.geom.LineString; |
||
51 | import com.vividsolutions.jts.geom.LinearRing; |
||
52 | import com.vividsolutions.jts.geom.Location; |
||
53 | import com.vividsolutions.jts.geom.MultiLineString; |
||
54 | import com.vividsolutions.jts.geom.MultiPolygon; |
||
55 | import com.vividsolutions.jts.geom.Polygon; |
||
56 | import com.vividsolutions.jts.geomgraph.DirectedEdge; |
||
57 | import com.vividsolutions.jts.geomgraph.Node; |
||
58 | |||
59 | |||
60 | |||
61 | /*
|
||
62 | * Performs a split of a LineString, MultiLineString, Polygon or MultiPolygon using a provided
|
||
63 | * LineString as cutting edge.
|
||
64 | */
|
||
65 | public class SplitStrategy { |
||
66 | |||
67 | private final LineString splittingLine; |
||
68 | |||
69 | private static final Map /* <Class, Class<? extends SpecificSplitOp> */strategies; |
||
70 | static {
|
||
71 | Map knownStrategies = new HashMap(); |
||
72 | knownStrategies.put(LineString.class, LineStringSplitter.class); |
||
73 | knownStrategies.put(MultiLineString.class, MultiLineStringSplitter.class); |
||
74 | knownStrategies.put(Polygon.class, PolygonSplitter.class);
|
||
75 | knownStrategies.put(MultiPolygon.class, MultiPolygonSplitter.class); |
||
76 | |||
77 | strategies = Collections.unmodifiableMap(knownStrategies);
|
||
78 | } |
||
79 | |||
80 | public SplitStrategy( final LineString splittingLine ) { |
||
81 | if (splittingLine == null) { |
||
82 | throw new NullPointerException(); |
||
83 | } |
||
84 | this.splittingLine = splittingLine;
|
||
85 | } |
||
86 | |||
87 | |||
88 | public static Geometry splitOp( Geometry geom, LineString splitLine ) { |
||
89 | SplitStrategy op = new SplitStrategy(splitLine);
|
||
90 | Geometry splittedGeometries = op.split(geom); |
||
91 | return splittedGeometries;
|
||
92 | } |
||
93 | |||
94 | |||
95 | /**
|
||
96 | * @param splitee
|
||
97 | * @return a <code>Geometry</code> containing all the splitted parts as aggregates. Use
|
||
98 | * {@link Geometry#getGeometryN(int) getGeometryN(int)} to get each part.
|
||
99 | * @throws NullPointerException if geom is null
|
||
100 | * @throws IllegalArgumentException if geom is not of an acceptable geometry type to be splitted
|
||
101 | * (i.e. not a linestring, multilinestring, polygon or multipolygon)
|
||
102 | */
|
||
103 | public Geometry split( final Geometry splitee ) { |
||
104 | if (splitee == null) { |
||
105 | throw new NullPointerException(); |
||
106 | } |
||
107 | |||
108 | Class spliteeClass = splitee.getClass();
|
||
109 | SpecificSplitOp splitOp = findSplitOp(spliteeClass); |
||
110 | |||
111 | Geometry splitResult; |
||
112 | |||
113 | splitOp.setSplitter(splittingLine); |
||
114 | splitResult = splitOp.split(splitee); |
||
115 | |||
116 | return splitResult;
|
||
117 | } |
||
118 | |||
119 | |||
120 | private SpecificSplitOp findSplitOp( Class spliteeClass ) { |
||
121 | if (!strategies.containsKey(spliteeClass)) {
|
||
122 | throw new IllegalArgumentException("La geometria especificada no soporta la operacion 'split'"); |
||
123 | } |
||
124 | |||
125 | final Class splitOpClass = (Class) strategies.get(spliteeClass); |
||
126 | SpecificSplitOp splitOp; |
||
127 | try {
|
||
128 | |||
129 | splitOp = (SpecificSplitOp) splitOpClass.newInstance(); |
||
130 | |||
131 | } catch (InstantiationException e) { |
||
132 | throw new RuntimeException("Cannot instantiate " + splitOpClass.getName(), e); |
||
133 | } catch (IllegalAccessException e) { |
||
134 | throw (RuntimeException) new RuntimeException("Illegal access exception for " |
||
135 | + splitOpClass.getName()).initCause(e); |
||
136 | } |
||
137 | return splitOp;
|
||
138 | } |
||
139 | |||
140 | private static interface SpecificSplitOp { |
||
141 | public void setSplitter( LineString splitter ); |
||
142 | public Geometry split( Geometry splitee );
|
||
143 | } |
||
144 | |||
145 | private static abstract class AbstractSplitter implements SpecificSplitOp { |
||
146 | |||
147 | protected LineString splitter;
|
||
148 | |||
149 | public void setSplitter( LineString splitter ) { |
||
150 | this.splitter = splitter;
|
||
151 | } |
||
152 | } |
||
153 | |||
154 | private static class LineStringSplitter extends AbstractSplitter { |
||
155 | /**
|
||
156 | * No-op default constructor required to reflectively instantiate the class
|
||
157 | */
|
||
158 | public LineStringSplitter() {
|
||
159 | // no-op
|
||
160 | } |
||
161 | /**
|
||
162 | * @param splitee the {@link LineString} to be splitted
|
||
163 | */
|
||
164 | public Geometry split( Geometry splitee ) {
|
||
165 | Geometry splitted = ((LineString) splitee).difference(splitter); |
||
166 | return splitted;
|
||
167 | } |
||
168 | |||
169 | } |
||
170 | |||
171 | private static abstract class AbstractGeometryCollectionSplitter implements SpecificSplitOp { |
||
172 | |||
173 | private SpecificSplitOp singlePartSplitter;
|
||
174 | |||
175 | private AbstractGeometryCollectionSplitter( SpecificSplitOp singlePartSplitter ) {
|
||
176 | this.singlePartSplitter = singlePartSplitter;
|
||
177 | } |
||
178 | |||
179 | public final void setSplitter( LineString splitter ) { |
||
180 | singlePartSplitter.setSplitter(splitter); |
||
181 | } |
||
182 | |||
183 | public final Geometry split( final Geometry splitee ) { |
||
184 | final GeometryCollection coll = (GeometryCollection) splitee;
|
||
185 | final int numParts = coll.getNumGeometries(); |
||
186 | |||
187 | List splittedParts = new ArrayList(); |
||
188 | |||
189 | for( int partN = 0; partN < numParts; partN++ ) { |
||
190 | Geometry simplePartN = coll.getGeometryN(partN); |
||
191 | Geometry splittedPart = singlePartSplitter.split(simplePartN); |
||
192 | final int splittedPartsCount = splittedPart.getNumGeometries(); |
||
193 | for( int splittedPartN = 0; splittedPartN < splittedPartsCount; splittedPartN++ ) { |
||
194 | Geometry simpleSplittedPart = splittedPart.getGeometryN(splittedPartN); |
||
195 | splittedParts.add(simpleSplittedPart); |
||
196 | } |
||
197 | } |
||
198 | |||
199 | GeometryFactory gf = splitee.getFactory(); |
||
200 | GeometryCollection splittedCollection = buildFromParts(gf, splittedParts); |
||
201 | return splittedCollection;
|
||
202 | } |
||
203 | |||
204 | protected abstract GeometryCollection buildFromParts( GeometryFactory gf, List parts ); |
||
205 | |||
206 | } |
||
207 | |||
208 | private static class MultiLineStringSplitter extends AbstractGeometryCollectionSplitter { |
||
209 | |||
210 | public MultiLineStringSplitter() {
|
||
211 | super(new LineStringSplitter()); |
||
212 | } |
||
213 | |||
214 | @Override
|
||
215 | protected GeometryCollection buildFromParts( GeometryFactory gf, List parts ) { |
||
216 | LineString[] lines = (LineString[]) parts.toArray(new LineString[parts.size()]); |
||
217 | MultiLineString result = gf.createMultiLineString(lines); |
||
218 | return result;
|
||
219 | } |
||
220 | } |
||
221 | |||
222 | private static class MultiPolygonSplitter extends AbstractGeometryCollectionSplitter { |
||
223 | |||
224 | public MultiPolygonSplitter() {
|
||
225 | super(new PolygonSplitter()); |
||
226 | } |
||
227 | |||
228 | @Override
|
||
229 | protected GeometryCollection buildFromParts( GeometryFactory gf, List parts ) { |
||
230 | Polygon[] polygons = (Polygon[]) parts.toArray(new Polygon[parts.size()]); |
||
231 | MultiPolygon result = gf.createMultiPolygon(polygons); |
||
232 | return result;
|
||
233 | } |
||
234 | } |
||
235 | |||
236 | /**
|
||
237 | * Estrategia:
|
||
238 | * <ul>
|
||
239 | * <li> Construir un grafo con todos los edges y nodes de la intersección del polÃgono con la
|
||
240 | * lÃnea
|
||
241 | * <li> Ponderar los nodos según la cantidad de edges incidentes. Nodos son solo las
|
||
242 | * intersecciones del boundary del poligono con el linestring y el punto inicial de cada parte
|
||
243 | * del boundary.
|
||
244 | * <li> Ponderar los edges según son shared (todos los del linestring) o non shared (todos los
|
||
245 | * del boundary del poligono). Almacenar la lista de coordenadas del edge en el edge.
|
||
246 | * <li> Comenzar a recorrer el grafo por un nodo cualquiera, empezando por su primer edge
|
||
247 | * <li> Recorrer siempre hacia el nodo siguiente, seleccionando el edge cuyo primer segmento de
|
||
248 | * su linestring presenta un menor angulo a la izquiera (CCW) con el ultimo segmento del
|
||
249 | * linestring del edge en curso.
|
||
250 | * <li> Eliminar del grafo los edges non-shared que se utilizaron
|
||
251 | * <li> Disminuir en 1 la ponderación de los nodos que se utilizaron
|
||
252 | * <li> Marcar los edges restantes que tengan algun nodo con ponderación < 3 como non-shared
|
||
253 | * <li> Eliminar del grafo los nodos con ponderación 1
|
||
254 | * </ul>
|
||
255 | */
|
||
256 | private static class PolygonSplitter extends AbstractSplitter { |
||
257 | |||
258 | /**
|
||
259 | * No-op default constructor required to reflectively instantiate the class
|
||
260 | */
|
||
261 | public PolygonSplitter() {
|
||
262 | // no-op
|
||
263 | } |
||
264 | |||
265 | /**
|
||
266 | *
|
||
267 | */
|
||
268 | public Geometry split( Geometry splitee ) {
|
||
269 | assert splitee instanceof Polygon;; |
||
270 | |||
271 | final Polygon polygon = (Polygon) splitee; |
||
272 | final Geometry splitted = splitPolygon(polygon);
|
||
273 | |||
274 | return splitted;
|
||
275 | } |
||
276 | |||
277 | /**
|
||
278 | *
|
||
279 | */
|
||
280 | private Geometry splitPolygon( final Polygon geom ) { |
||
281 | SplitGraph graph = new SplitGraph(geom, splitter);
|
||
282 | |||
283 | final GeometryFactory gf = geom.getFactory();
|
||
284 | |||
285 | // sotore unsplitted holes for later addition
|
||
286 | List<LinearRing> unsplittedHoles = findUnsplittedHoles(graph, gf);
|
||
287 | |||
288 | List<List<SplitEdge>> allRings = findRings(graph); |
||
289 | |||
290 | List<Polygon> resultingPolygons = buildSimplePolygons(allRings, unsplittedHoles, gf); |
||
291 | |||
292 | Geometry result; |
||
293 | if (resultingPolygons.size() == 1) { |
||
294 | result = resultingPolygons.get(0);
|
||
295 | } else {
|
||
296 | Polygon[] array = resultingPolygons.toArray(new Polygon[resultingPolygons.size()]); |
||
297 | result = gf.createMultiPolygon(array); |
||
298 | } |
||
299 | return result;
|
||
300 | } |
||
301 | |||
302 | /**
|
||
303 | * Finds out and removes from the graph the edges that were originally holes in the polygon
|
||
304 | * and were not splitted by the splitting line.
|
||
305 | *
|
||
306 | * @param graph
|
||
307 | * @param gf
|
||
308 | * @return
|
||
309 | */
|
||
310 | @SuppressWarnings("unchecked") |
||
311 | private List<LinearRing> findUnsplittedHoles( SplitGraph graph, GeometryFactory gf ) { |
||
312 | final List<LinearRing> unsplittedHoles = new ArrayList<LinearRing>(2); |
||
313 | |||
314 | final List<SplitEdge> edges = new ArrayList<SplitEdge>(); |
||
315 | for( Iterator it = graph.getEdgeIterator(); it.hasNext(); ) { |
||
316 | SplitEdge edge = (SplitEdge) it.next(); |
||
317 | edges.add(edge); |
||
318 | } |
||
319 | |||
320 | for( Iterator it = edges.iterator(); it.hasNext(); ) { |
||
321 | SplitEdge edge = (SplitEdge) it.next(); |
||
322 | if (edge.isHoleEdge()) {
|
||
323 | Coordinate[] coordinates = edge.getCoordinates();
|
||
324 | Coordinate start = coordinates[0];
|
||
325 | Coordinate end = coordinates[coordinates.length - 1];
|
||
326 | boolean isLinearRing = start.equals2D(end);
|
||
327 | if (isLinearRing) {
|
||
328 | graph.remove(edge); |
||
329 | LinearRing ring = gf.createLinearRing(coordinates); |
||
330 | unsplittedHoles.add(ring); |
||
331 | } |
||
332 | } |
||
333 | } |
||
334 | return unsplittedHoles;
|
||
335 | } |
||
336 | |||
337 | private List<Polygon> buildSimplePolygons( List<List<SplitEdge>> allRings, |
||
338 | List<LinearRing> unsplittedHoles,
|
||
339 | GeometryFactory gf ) { |
||
340 | |||
341 | List<Polygon> polygons = new ArrayList<Polygon>(allRings.size()); |
||
342 | |||
343 | for( List<SplitEdge> edgeList : allRings ) { |
||
344 | Polygon poly = buildPolygon(edgeList, gf);
|
||
345 | List<LinearRing> thisPolyHoles = new ArrayList<LinearRing>(unsplittedHoles.size()); |
||
346 | for( LinearRing holeRing : unsplittedHoles ) {
|
||
347 | if (poly.covers(holeRing)) {
|
||
348 | thisPolyHoles.add(holeRing); |
||
349 | } |
||
350 | } |
||
351 | unsplittedHoles.removeAll(thisPolyHoles); |
||
352 | |||
353 | int numHoles = thisPolyHoles.size();
|
||
354 | if (numHoles > 0) { |
||
355 | LinearRing[] holes = thisPolyHoles.toArray(new LinearRing[numHoles]); |
||
356 | LinearRing shell = gf.createLinearRing(poly.getExteriorRing().getCoordinates()); |
||
357 | poly = gf.createPolygon(shell, holes); |
||
358 | } |
||
359 | |||
360 | polygons.add(poly); |
||
361 | } |
||
362 | |||
363 | return polygons;
|
||
364 | } |
||
365 | |||
366 | private Polygon buildPolygon( List<SplitEdge> edgeList, GeometryFactory gf ) { |
||
367 | List<Coordinate> coords = new ArrayList<Coordinate>(); |
||
368 | Coordinate[] lastCoordinates = null; |
||
369 | for( SplitEdge edge : edgeList ) {
|
||
370 | Coordinate[] coordinates = edge.getCoordinates();
|
||
371 | if (lastCoordinates != null) { |
||
372 | Coordinate endPoint = lastCoordinates[lastCoordinates.length - 1];
|
||
373 | Coordinate startPoint = coordinates[0];
|
||
374 | if (!endPoint.equals2D(startPoint)) {
|
||
375 | coordinates = CoordinateArrays.copyDeep(coordinates); |
||
376 | CoordinateArrays.reverse(coordinates); |
||
377 | } |
||
378 | } |
||
379 | lastCoordinates = coordinates; |
||
380 | for( int i = 0; i < coordinates.length; i++ ) { |
||
381 | Coordinate coord = coordinates[i]; |
||
382 | coords.add(coord); |
||
383 | } |
||
384 | } |
||
385 | Coordinate[] shellCoords = new Coordinate[coords.size()]; |
||
386 | coords.toArray(shellCoords); |
||
387 | shellCoords = CoordinateArrays.removeRepeatedPoints(shellCoords); |
||
388 | LinearRing shell = gf.createLinearRing(shellCoords); |
||
389 | Polygon poly = gf.createPolygon(shell, (LinearRing[]) null); |
||
390 | return poly;
|
||
391 | } |
||
392 | |||
393 | /**
|
||
394 | * Builds a list of rings from the graph's edges
|
||
395 | *
|
||
396 | * @param graph
|
||
397 | * @return
|
||
398 | */
|
||
399 | @SuppressWarnings("unchecked") |
||
400 | private List<List<SplitEdge>> findRings( SplitGraph graph ) { |
||
401 | final List<List<SplitEdge>> rings = new ArrayList<List<SplitEdge>>(); |
||
402 | |||
403 | DirectedEdge startEdge; |
||
404 | // build each ring starting with the first edge belonging to the
|
||
405 | // shell found
|
||
406 | while( (startEdge = findShellEdge(graph)) != null ) { |
||
407 | List<SplitEdge> ring = buildRing(graph, startEdge);
|
||
408 | rings.add(ring); |
||
409 | } |
||
410 | return rings;
|
||
411 | } |
||
412 | |||
413 | private List<SplitEdge> buildRing( final SplitGraph graph, final DirectedEdge startEdge ) { |
||
414 | // System.out.println("building ring edge list...");
|
||
415 | final List<SplitEdge> ring = new ArrayList<SplitEdge>(); |
||
416 | |||
417 | // follow this tessellation direction while possible,
|
||
418 | // switch to the opposite when not, and continue with
|
||
419 | // the same direction while possible.
|
||
420 | // Start travelling clockwise, as we start with a shell edge,
|
||
421 | // which is in clockwise order
|
||
422 | final int direction = CGAlgorithms.COUNTERCLOCKWISE; |
||
423 | |||
424 | DirectedEdge currentDirectedEdge = startEdge; |
||
425 | DirectedEdge nextDirectedEdge = null;
|
||
426 | |||
427 | while( nextDirectedEdge != startEdge ) {
|
||
428 | SplitEdge edge = (SplitEdge) currentDirectedEdge.getEdge(); |
||
429 | // System.out.println("adding " + edge);
|
||
430 | if (ring.contains(edge)) {
|
||
431 | throw new IllegalStateException("trying to add edge twice: " + edge); |
||
432 | } |
||
433 | ring.add(edge); |
||
434 | |||
435 | DirectedEdge sym = currentDirectedEdge.getSym(); |
||
436 | SplitGraphNode endNode = (SplitGraphNode) sym.getNode(); |
||
437 | SplitEdgeStar nodeEdges = (SplitEdgeStar) endNode.getEdges(); |
||
438 | nextDirectedEdge = nodeEdges.findClosestEdgeInDirection(sym, direction); |
||
439 | |||
440 | assert nextDirectedEdge != null; |
||
441 | |||
442 | currentDirectedEdge = nextDirectedEdge; |
||
443 | } |
||
444 | |||
445 | removeUnneededEdges(graph, ring); |
||
446 | return ring;
|
||
447 | } |
||
448 | |||
449 | /**
|
||
450 | * Removes from <code>graph</code> the edges in <code>ring</code> that are no more
|
||
451 | * needed
|
||
452 | *
|
||
453 | * @param graph
|
||
454 | * @param ring
|
||
455 | */
|
||
456 | private void removeUnneededEdges( final SplitGraph graph, final List<SplitEdge> ring ) { |
||
457 | for( SplitEdge edge : ring ) {
|
||
458 | if (!edge.isInteriorEdge()) {
|
||
459 | graph.remove(edge); |
||
460 | } |
||
461 | } |
||
462 | |||
463 | for( SplitEdge edge : ring ) {
|
||
464 | if (edge.isInteriorEdge()) {
|
||
465 | Node node = graph.find(edge.getCoordinate()); |
||
466 | int degree = node.getEdges().getDegree();
|
||
467 | if (degree < 2) { |
||
468 | graph.remove(edge); |
||
469 | } |
||
470 | } |
||
471 | } |
||
472 | } |
||
473 | |||
474 | /**
|
||
475 | * Returns the first edge found that belongs to the shell (not an interior edge, not one of
|
||
476 | * a hole boundary)
|
||
477 | * <p>
|
||
478 | * This method relies on shell edges being labeled {@link Location#EXTERIOR exterior} to the
|
||
479 | * left and {@link Location#INTERIOR interior} to the right.
|
||
480 | * </p>
|
||
481 | *
|
||
482 | * @param graph
|
||
483 | * @return the first shell edge found, or <code>null</code> if there are no more shell
|
||
484 | * edges in <code>graph</code>
|
||
485 | */
|
||
486 | private DirectedEdge findShellEdge( SplitGraph graph ) {
|
||
487 | Iterator it = graph.getEdgeEnds().iterator();
|
||
488 | DirectedEdge firstShellEdge = null;
|
||
489 | while( it.hasNext() ) {
|
||
490 | DirectedEdge de = (DirectedEdge) it.next(); |
||
491 | SplitEdge edge = (SplitEdge) de.getEdge(); |
||
492 | if (edge.isShellEdge()) {
|
||
493 | firstShellEdge = de; |
||
494 | break;
|
||
495 | } |
||
496 | } |
||
497 | return firstShellEdge;
|
||
498 | } |
||
499 | } |
||
500 | } |