gvsig-vectorediting / org.gvsig.vectorediting / trunk / org.gvsig.vectorediting / org.gvsig.vectorediting.lib / org.gvsig.vectorediting.lib.prov / org.gvsig.vectorediting.lib.prov.split / src / main / java / org / gvsig / vectorediting / lib / prov / split / operation / splitsurface / SurfaceSplitOperation.java @ 575
History | View | Annotate | Download (14.6 KB)
1 |
/**
|
---|---|
2 |
* gvSIG. Desktop Geographic Information System.
|
3 |
*
|
4 |
* Copyright ? 2007-2014 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 2
|
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 |
|
25 |
package org.gvsig.vectorediting.lib.prov.split.operation.splitsurface; |
26 |
|
27 |
import java.util.ArrayList; |
28 |
import java.util.Iterator; |
29 |
import java.util.List; |
30 |
|
31 |
import com.vividsolutions.jts.algorithm.CGAlgorithms; |
32 |
import com.vividsolutions.jts.geom.Coordinate; |
33 |
import com.vividsolutions.jts.geom.CoordinateArrays; |
34 |
import com.vividsolutions.jts.geom.GeometryFactory; |
35 |
import com.vividsolutions.jts.geom.LineString; |
36 |
import com.vividsolutions.jts.geom.LinearRing; |
37 |
import com.vividsolutions.jts.geom.Location; |
38 |
import com.vividsolutions.jts.geom.MultiLineString; |
39 |
import com.vividsolutions.jts.geom.MultiPolygon; |
40 |
import com.vividsolutions.jts.geom.Polygon; |
41 |
import com.vividsolutions.jts.geomgraph.DirectedEdge; |
42 |
import com.vividsolutions.jts.geomgraph.Node; |
43 |
|
44 |
import org.gvsig.fmap.geom.Geometry; |
45 |
import org.gvsig.fmap.geom.GeometryLocator; |
46 |
import org.gvsig.fmap.geom.GeometryManager; |
47 |
import org.gvsig.fmap.geom.operation.GeometryOperationContext; |
48 |
import org.gvsig.fmap.geom.operation.GeometryOperationException; |
49 |
import org.gvsig.fmap.geom.operation.GeometryOperationNotSupportedException; |
50 |
import org.gvsig.vectorediting.lib.prov.split.operation.SplitOperation; |
51 |
|
52 |
/**
|
53 |
* This class is based in the AXIOS team work for UDIG project.
|
54 |
*
|
55 |
* @author llmarques
|
56 |
*
|
57 |
*/
|
58 |
|
59 |
/*
|
60 |
* Performs a split of a LineString, MultiLineString, Polygon or MultiPolygon
|
61 |
* using a provided
|
62 |
* LineString as cutting edge.
|
63 |
*
|
64 |
* @author Gabriel Rold?n, Axios Engineering
|
65 |
*
|
66 |
* @author Mauricio Pazos, Axios Engineering
|
67 |
*
|
68 |
* @since 1.1.0
|
69 |
*/
|
70 |
public class SurfaceSplitOperation implements SplitOperation { |
71 |
|
72 |
/**
|
73 |
* Strategy:
|
74 |
* <ul>
|
75 |
* <li>Build a graph with all edges and intersection nodes between polygon
|
76 |
* and linestring.
|
77 |
* <li>Weigth the amount of nodes according to the number of incident edges.
|
78 |
* Nodes are only the intersection beetween polygon bondary and linestring
|
79 |
* and initial points of each part of boundary.
|
80 |
* <li>Weigth edges according to shared (linestring node) or non shared
|
81 |
* (boundary of polygon). Store edge cordinates at edge.
|
82 |
* <li>Iterate over node graph. Start at any node, starting at its first
|
83 |
* segment.
|
84 |
* <li>Iterate always to next node, choosing the edge that its first
|
85 |
* linestring segment that has less left angle (CCW) with the last segment
|
86 |
* of edge linestring.
|
87 |
* <li>Delete non shared used edges that was used
|
88 |
* <li>Decrease weight at 1 of used nodes
|
89 |
* <li>Delete of graph nodes with weight 1
|
90 |
* </ul>
|
91 |
*
|
92 |
* @author Gabriel Rold?n, Axios Engineering
|
93 |
* @author Mauricio Pazos, Axios Engineering
|
94 |
* @since 1.1.0
|
95 |
*/
|
96 |
public Geometry split(Geometry geometryToBeSplitted, Geometry splitter)
|
97 |
throws GeometryOperationNotSupportedException,
|
98 |
GeometryOperationException { |
99 |
|
100 |
com.vividsolutions.jts.geom.Geometry jtsGeom = |
101 |
(com.vividsolutions.jts.geom.Geometry) geometryToBeSplitted |
102 |
.invokeOperation("toJTS", null); |
103 |
|
104 |
com.vividsolutions.jts.geom.Geometry jtsSplitter = |
105 |
(com.vividsolutions.jts.geom.Geometry) splitter.invokeOperation( |
106 |
"toJTS", null); |
107 |
|
108 |
if(jtsSplitter instanceof MultiLineString && jtsSplitter.getNumGeometries() == 1){ |
109 |
jtsSplitter = jtsSplitter.getGeometryN(0);
|
110 |
} |
111 |
|
112 |
com.vividsolutions.jts.geom.Geometry result = null;
|
113 |
if (jtsSplitter instanceof LineString) { |
114 |
if (jtsGeom instanceof Polygon) { |
115 |
result = splitPolygon(jtsGeom, jtsSplitter); |
116 |
} else if (jtsGeom instanceof MultiPolygon) { |
117 |
result = splitMultiPolygon((MultiPolygon)jtsGeom, jtsSplitter); |
118 |
} |
119 |
|
120 |
} |
121 |
|
122 |
if(result !=null){ |
123 |
GeometryManager manager = GeometryLocator.getGeometryManager(); |
124 |
GeometryOperationContext params = new GeometryOperationContext();
|
125 |
params.setAttribute("JTSGeometry", result);
|
126 |
return (Geometry) manager.invokeOperation("fromJTS", params); |
127 |
} |
128 |
return null; |
129 |
} |
130 |
private com.vividsolutions.jts.geom.Geometry splitMultiPolygon(
|
131 |
MultiPolygon jtsMultiPoligon, |
132 |
com.vividsolutions.jts.geom.Geometry jtsSplitter) { |
133 |
|
134 |
final GeometryFactory gf = jtsMultiPoligon.getFactory();
|
135 |
com.vividsolutions.jts.geom.Geometry result; |
136 |
List<com.vividsolutions.jts.geom.Geometry> splittedGeometries = new ArrayList<com.vividsolutions.jts.geom.Geometry>(); |
137 |
for (int i = 0; i < jtsMultiPoligon.getNumGeometries(); i++) { |
138 |
com.vividsolutions.jts.geom.Geometry jtsGeom = jtsMultiPoligon.getGeometryN(i); |
139 |
com.vividsolutions.jts.geom.Geometry splittedGeometry; |
140 |
if (jtsGeom instanceof MultiPolygon) { |
141 |
splittedGeometry = splitMultiPolygon((MultiPolygon)jtsGeom, jtsSplitter); |
142 |
} else {
|
143 |
splittedGeometry = splitPolygon(jtsGeom, jtsSplitter); |
144 |
} |
145 |
|
146 |
if (splittedGeometry instanceof MultiPolygon) { |
147 |
for (int j = 0; j < ((MultiPolygon)splittedGeometry).getNumGeometries(); j++) { |
148 |
splittedGeometries.add(((MultiPolygon)splittedGeometry).getGeometryN(j)); |
149 |
} |
150 |
} else {
|
151 |
splittedGeometries.add(splittedGeometry); |
152 |
} |
153 |
} |
154 |
if (splittedGeometries.size() == 1) { |
155 |
result = splittedGeometries.get(0);
|
156 |
} else {
|
157 |
Polygon[] array = |
158 |
splittedGeometries.toArray(new Polygon[splittedGeometries |
159 |
.size()]); |
160 |
result = gf.createMultiPolygon(array); |
161 |
} |
162 |
return result;
|
163 |
} |
164 |
|
165 |
private com.vividsolutions.jts.geom.Geometry splitPolygon(
|
166 |
com.vividsolutions.jts.geom.Geometry jtsGeom, |
167 |
com.vividsolutions.jts.geom.Geometry jtsSplitter) { |
168 |
com.vividsolutions.jts.geom.Geometry result; |
169 |
SplitGraph graph = |
170 |
new SplitGraph((Polygon) jtsGeom, (LineString) jtsSplitter); |
171 |
final GeometryFactory gf = jtsGeom.getFactory();
|
172 |
|
173 |
// store unsplitted holes for later addition
|
174 |
List<LinearRing> unsplittedHoles = findUnsplittedHoles(graph, gf);
|
175 |
|
176 |
List<List<SplitEdge>> allRings = findRings(graph); |
177 |
|
178 |
List<Polygon> resultingPolygons = |
179 |
buildSimplePolygons(allRings, unsplittedHoles, gf); |
180 |
|
181 |
if (resultingPolygons.size() == 1) { |
182 |
result = resultingPolygons.get(0);
|
183 |
} else {
|
184 |
Polygon[] array = |
185 |
resultingPolygons.toArray(new Polygon[resultingPolygons |
186 |
.size()]); |
187 |
result = gf.createMultiPolygon(array); |
188 |
} |
189 |
return result;
|
190 |
} |
191 |
|
192 |
/**
|
193 |
* Finds out and removes from the graph the edges that were originally holes
|
194 |
* in the polygon and were not splitted by the splitting line.
|
195 |
*
|
196 |
* @param graph
|
197 |
* @param gf
|
198 |
* @return
|
199 |
*/
|
200 |
private List<LinearRing> findUnsplittedHoles(SplitGraph graph, |
201 |
GeometryFactory gf) { |
202 |
final List<LinearRing> unsplittedHoles = new ArrayList<LinearRing>(2); |
203 |
|
204 |
final List<SplitEdge> edges = new ArrayList<SplitEdge>(); |
205 |
for (Iterator it = graph.getEdgeIterator(); it.hasNext();) { |
206 |
SplitEdge edge = (SplitEdge) it.next(); |
207 |
edges.add(edge); |
208 |
} |
209 |
|
210 |
for (Iterator it = edges.iterator(); it.hasNext();) { |
211 |
SplitEdge edge = (SplitEdge) it.next(); |
212 |
if (edge.isHoleEdge()) {
|
213 |
Coordinate[] coordinates = edge.getCoordinates();
|
214 |
Coordinate start = coordinates[0];
|
215 |
Coordinate end = coordinates[coordinates.length - 1];
|
216 |
boolean isLinearRing = start.equals2D(end);
|
217 |
if (isLinearRing) {
|
218 |
graph.remove(edge); |
219 |
LinearRing ring = gf.createLinearRing(coordinates); |
220 |
unsplittedHoles.add(ring); |
221 |
} |
222 |
} |
223 |
} |
224 |
return unsplittedHoles;
|
225 |
} |
226 |
|
227 |
/**
|
228 |
* Builds a list of rings from the graph's edges
|
229 |
*
|
230 |
* @param graph
|
231 |
* @return
|
232 |
*/
|
233 |
private List<List<SplitEdge>> findRings(SplitGraph graph) { |
234 |
final List<List<SplitEdge>> rings = new ArrayList<List<SplitEdge>>(); |
235 |
|
236 |
DirectedEdge startEdge; |
237 |
// build each ring starting with the first edge belonging to the
|
238 |
// shell found
|
239 |
while ((startEdge = findShellEdge(graph)) != null) { |
240 |
List<SplitEdge> ring = buildRing(graph, startEdge);
|
241 |
rings.add(ring); |
242 |
} |
243 |
return rings;
|
244 |
} |
245 |
|
246 |
/**
|
247 |
* Returns the first edge found that belongs to the shell (not an interior
|
248 |
* edge, not one of a hole boundary)
|
249 |
* <p>
|
250 |
* This method relies on shell edges being labeled {@link Location#EXTERIOR
|
251 |
* exterior} to the left and {@link Location#INTERIOR interior} to the
|
252 |
* right.
|
253 |
* </p>
|
254 |
*
|
255 |
* @param graph
|
256 |
* @return the first shell edge found, or <code>null</code> if there are no
|
257 |
* more shell edges in <code>graph</code>
|
258 |
*/
|
259 |
private DirectedEdge findShellEdge(SplitGraph graph) {
|
260 |
Iterator it = graph.getEdgeEnds().iterator();
|
261 |
DirectedEdge firstShellEdge = null;
|
262 |
while (it.hasNext()) {
|
263 |
DirectedEdge de = (DirectedEdge) it.next(); |
264 |
SplitEdge edge = (SplitEdge) de.getEdge(); |
265 |
if (edge.isShellEdge()) {
|
266 |
firstShellEdge = de; |
267 |
break;
|
268 |
} |
269 |
} |
270 |
return firstShellEdge;
|
271 |
} |
272 |
|
273 |
private List<SplitEdge> buildRing(final SplitGraph graph, |
274 |
final DirectedEdge startEdge) {
|
275 |
final List<SplitEdge> ring = new ArrayList<SplitEdge>(); |
276 |
|
277 |
// follow this tessellation direction while possible,
|
278 |
// switch to the opposite when not, and continue with
|
279 |
// the same direction while possible.
|
280 |
// Start travelling clockwise, as we start with a shell edge,
|
281 |
// which is in clockwise order
|
282 |
final int direction = CGAlgorithms.COUNTERCLOCKWISE; |
283 |
|
284 |
DirectedEdge currentDirectedEdge = startEdge; |
285 |
DirectedEdge nextDirectedEdge = null;
|
286 |
|
287 |
while (nextDirectedEdge != startEdge) {
|
288 |
SplitEdge edge = (SplitEdge) currentDirectedEdge.getEdge(); |
289 |
if (ring.contains(edge)) {
|
290 |
throw new IllegalStateException("trying to add edge twice: " |
291 |
+ edge); |
292 |
} |
293 |
ring.add(edge); |
294 |
|
295 |
DirectedEdge sym = currentDirectedEdge.getSym(); |
296 |
SplitGraphNode endNode = (SplitGraphNode) sym.getNode(); |
297 |
SplitEdgeStar nodeEdges = (SplitEdgeStar) endNode.getEdges(); |
298 |
nextDirectedEdge = |
299 |
nodeEdges.findClosestEdgeInDirection(sym, direction); |
300 |
|
301 |
assert nextDirectedEdge != null; |
302 |
|
303 |
currentDirectedEdge = nextDirectedEdge; |
304 |
} |
305 |
|
306 |
removeUnneededEdges(graph, ring); |
307 |
return ring;
|
308 |
} |
309 |
|
310 |
/**
|
311 |
* Removes from <code>graph</code> the edges in <code>ring</code> that are
|
312 |
* no more needed
|
313 |
*
|
314 |
* @param graph
|
315 |
* @param ring
|
316 |
*/
|
317 |
private void removeUnneededEdges(final SplitGraph graph, |
318 |
final List<SplitEdge> ring) { |
319 |
for (SplitEdge edge : ring) {
|
320 |
if (!edge.isInteriorEdge()) {
|
321 |
graph.remove(edge); |
322 |
} |
323 |
} |
324 |
|
325 |
for (SplitEdge edge : ring) {
|
326 |
if (edge.isInteriorEdge()) {
|
327 |
Node node = graph.find(edge.getCoordinate()); |
328 |
int degree = node.getEdges().getDegree();
|
329 |
if (degree < 2) { |
330 |
graph.remove(edge); |
331 |
} |
332 |
} |
333 |
} |
334 |
} |
335 |
|
336 |
private List<Polygon> buildSimplePolygons(List<List<SplitEdge>> allRings, |
337 |
List<LinearRing> unsplittedHoles, GeometryFactory gf) {
|
338 |
|
339 |
List<Polygon> polygons = new ArrayList<Polygon>(allRings.size()); |
340 |
|
341 |
for (List<SplitEdge> edgeList : allRings) { |
342 |
Polygon poly = buildPolygon(edgeList, gf);
|
343 |
List<LinearRing> thisPolyHoles =
|
344 |
new ArrayList<LinearRing>(unsplittedHoles.size()); |
345 |
for (LinearRing holeRing : unsplittedHoles) {
|
346 |
if (poly.covers(holeRing)) {
|
347 |
thisPolyHoles.add(holeRing); |
348 |
} |
349 |
} |
350 |
unsplittedHoles.removeAll(thisPolyHoles); |
351 |
|
352 |
int numHoles = thisPolyHoles.size();
|
353 |
if (numHoles > 0) { |
354 |
LinearRing[] holes =
|
355 |
thisPolyHoles.toArray(new LinearRing[numHoles]);
|
356 |
LinearRing shell = |
357 |
gf.createLinearRing(poly.getExteriorRing().getCoordinates()); |
358 |
poly = gf.createPolygon(shell, holes); |
359 |
} |
360 |
|
361 |
polygons.add(poly); |
362 |
} |
363 |
|
364 |
return polygons;
|
365 |
} |
366 |
|
367 |
private Polygon buildPolygon(List<SplitEdge> edgeList, GeometryFactory gf) { |
368 |
List<Coordinate> coords = new ArrayList<Coordinate>(); |
369 |
Coordinate[] lastCoordinates = null; |
370 |
for (SplitEdge edge : edgeList) {
|
371 |
Coordinate[] coordinates = edge.getCoordinates();
|
372 |
if (lastCoordinates != null) { |
373 |
Coordinate endPoint = |
374 |
lastCoordinates[lastCoordinates.length - 1];
|
375 |
Coordinate startPoint = coordinates[0];
|
376 |
if (!endPoint.equals2D(startPoint)) {
|
377 |
coordinates = CoordinateArrays.copyDeep(coordinates); |
378 |
CoordinateArrays.reverse(coordinates); |
379 |
} |
380 |
} |
381 |
lastCoordinates = coordinates; |
382 |
for (int i = 0; i < coordinates.length; i++) { |
383 |
Coordinate coord = coordinates[i]; |
384 |
coords.add(coord); |
385 |
} |
386 |
} |
387 |
Coordinate[] shellCoords = new Coordinate[coords.size()]; |
388 |
coords.toArray(shellCoords); |
389 |
shellCoords = CoordinateArrays.removeRepeatedPoints(shellCoords); |
390 |
LinearRing shell = gf.createLinearRing(shellCoords); |
391 |
Polygon poly = gf.createPolygon(shell, (LinearRing[]) null); |
392 |
return poly;
|
393 |
} |
394 |
|
395 |
} |