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