svn-gvsig-desktop / trunk / libraries / libFMap / src / com / vividsolutions / jts / operation / overlay / SnappingOverlayOperation.java @ 9178
History | View | Annotate | Download (25.4 KB)
1 |
/*
|
---|---|
2 |
* Created on 12-sep-2006 by azabala
|
3 |
*
|
4 |
*/
|
5 |
package com.vividsolutions.jts.operation.overlay; |
6 |
|
7 |
import java.util.ArrayList; |
8 |
import java.util.Iterator; |
9 |
import java.util.List; |
10 |
|
11 |
import com.vividsolutions.jts.algorithm.CGAlgorithms; |
12 |
import com.vividsolutions.jts.algorithm.LineIntersector; |
13 |
import com.vividsolutions.jts.algorithm.PointLocator; |
14 |
import com.vividsolutions.jts.algorithms.SnapPointLocator; |
15 |
import com.vividsolutions.jts.geom.Coordinate; |
16 |
import com.vividsolutions.jts.geom.Geometry; |
17 |
import com.vividsolutions.jts.geom.GeometryFactory; |
18 |
import com.vividsolutions.jts.geom.Location; |
19 |
import com.vividsolutions.jts.geom.Point; |
20 |
import com.vividsolutions.jts.geomgraph.Depth; |
21 |
import com.vividsolutions.jts.geomgraph.DirectedEdge; |
22 |
import com.vividsolutions.jts.geomgraph.DirectedEdgeStar; |
23 |
import com.vividsolutions.jts.geomgraph.Edge; |
24 |
import com.vividsolutions.jts.geomgraph.EdgeList; |
25 |
import com.vividsolutions.jts.geomgraph.Label; |
26 |
import com.vividsolutions.jts.geomgraph.Node; |
27 |
import com.vividsolutions.jts.geomgraph.PlanarGraph; |
28 |
import com.vividsolutions.jts.geomgraph.Position; |
29 |
import com.vividsolutions.jts.geomgraph.SnapEdgeList; |
30 |
import com.vividsolutions.jts.geomgraph.SnappingGeometryGraph; |
31 |
import com.vividsolutions.jts.geomgraph.SnappingPlanarGraph; |
32 |
import com.vividsolutions.jts.io.ParseException; |
33 |
import com.vividsolutions.jts.operation.overlay.LineBuilder; |
34 |
import com.vividsolutions.jts.operation.overlay.OverlayNodeFactory; |
35 |
import com.vividsolutions.jts.operation.overlay.OverlayOp; |
36 |
import com.vividsolutions.jts.operation.overlay.PointBuilder; |
37 |
import com.vividsolutions.jts.operation.overlay.PolygonBuilder; |
38 |
import com.vividsolutions.jts.util.Assert; |
39 |
|
40 |
/**
|
41 |
* TODO
|
42 |
* El codigo esta lleno de coordinateA.distance(coordinateB)
|
43 |
* <= snapTolerance;
|
44 |
*
|
45 |
* CAMBIAR POR SnapCoordinate, de forma que equals haga
|
46 |
* esta comprobacin
|
47 |
*
|
48 |
*
|
49 |
*/
|
50 |
public class SnappingOverlayOperation extends OverlayOp { |
51 |
|
52 |
protected final SnapPointLocator ptLocator = new SnapPointLocator(); |
53 |
protected GeometryFactory geomFact;
|
54 |
protected Geometry resultGeom;
|
55 |
|
56 |
protected LineIntersector li;
|
57 |
|
58 |
protected double snapTolerance; |
59 |
|
60 |
|
61 |
/*Planar graph of the overlay operation*/
|
62 |
protected SnappingPlanarGraph graph;
|
63 |
|
64 |
/*Geometry graph of each individual geometry*/
|
65 |
protected SnappingGeometryGraph[] arg; |
66 |
|
67 |
|
68 |
/*It saves all the new edges resulting from intersections of
|
69 |
* edges of geometries A and B. It is a temporal repository, before
|
70 |
* to save them in SnappingPlanarGraph*/
|
71 |
protected SnapEdgeList edgeList = null; |
72 |
|
73 |
|
74 |
/*
|
75 |
* El resultado de una operacion de overlay puede contener
|
76 |
* puntos, lineas y poligonos.
|
77 |
* */
|
78 |
protected List resultPolyList = new ArrayList(); |
79 |
|
80 |
protected List resultLineList = new ArrayList(); |
81 |
|
82 |
protected List resultPointList = new ArrayList(); |
83 |
|
84 |
|
85 |
|
86 |
public static Geometry overlayOp(Geometry geom0, Geometry geom1, |
87 |
int opCode, double tolerance) { |
88 |
SnappingOverlayOperation gov = new SnappingOverlayOperation(geom0,
|
89 |
geom1, tolerance); |
90 |
Geometry geomOv = gov.getResultGeometry(opCode); |
91 |
return geomOv;
|
92 |
} |
93 |
|
94 |
|
95 |
|
96 |
public SnappingOverlayOperation(Geometry g0, Geometry g1, double tolerance) { |
97 |
super(g0, g1);
|
98 |
graph = new SnappingPlanarGraph(new OverlayNodeFactory(), tolerance); |
99 |
arg = new SnappingGeometryGraph[2]; |
100 |
arg[0] = new SnappingGeometryGraph(tolerance, 0, g0); |
101 |
arg[1] = new SnappingGeometryGraph(tolerance, 1, g1); |
102 |
geomFact = g0.getFactory(); |
103 |
li = new SnapLineIntersector(tolerance);
|
104 |
edgeList = new SnapEdgeList(tolerance);
|
105 |
this.snapTolerance = tolerance;
|
106 |
} |
107 |
|
108 |
public Geometry getResultGeometry(int funcCode) { |
109 |
computeOverlay(funcCode); |
110 |
return resultGeom;
|
111 |
} |
112 |
|
113 |
|
114 |
public PlanarGraph getGraph() {
|
115 |
return graph;
|
116 |
} |
117 |
|
118 |
|
119 |
private boolean isReused = false; |
120 |
/**
|
121 |
* Metodo de utilidad cuando vayamos a intersectar la geometria
|
122 |
* g1 con varias geometrias (g2, g3, g4, .... , etc.)
|
123 |
*
|
124 |
* Los calculos basicos no se repiten para g1
|
125 |
*
|
126 |
* */
|
127 |
|
128 |
|
129 |
public void setSecondGeometry(Geometry geometry){ |
130 |
Geometry g0 = arg[0].getGeometry();
|
131 |
if (g0.getPrecisionModel().compareTo(geometry.getPrecisionModel()) >= 0) |
132 |
setComputationPrecision(g0.getPrecisionModel()); |
133 |
else
|
134 |
setComputationPrecision(geometry.getPrecisionModel()); |
135 |
graph = new SnappingPlanarGraph(new OverlayNodeFactory(), snapTolerance); |
136 |
|
137 |
|
138 |
/*
|
139 |
*TODO
|
140 |
*Deberiamos borrar todos los nodos del GeometryGraph,
|
141 |
*o solo las intersecciones?????
|
142 |
*De todos modos, aunque borrasemos los nodos, getBoundaryNodes
|
143 |
*devolveria nodos cacheados
|
144 |
*
|
145 |
* TODO REVISAR
|
146 |
* */
|
147 |
arg[0].clearIntersections();
|
148 |
|
149 |
|
150 |
|
151 |
arg[1] = new SnappingGeometryGraph(snapTolerance, 1, geometry); |
152 |
geomFact = g0.getFactory(); |
153 |
edgeList = new SnapEdgeList(snapTolerance);
|
154 |
|
155 |
resultPolyList.clear(); |
156 |
resultLineList.clear(); |
157 |
resultPointList.clear(); |
158 |
|
159 |
resultGeom = null;
|
160 |
|
161 |
isReused = true;
|
162 |
} |
163 |
|
164 |
|
165 |
/*
|
166 |
* ************************************************************
|
167 |
* METODO PRINCIPAL
|
168 |
* ************************************************************
|
169 |
* */
|
170 |
private void computeOverlay(int opCode) { |
171 |
|
172 |
/*
|
173 |
* Se copian los NODOS de las dos geometrias.
|
174 |
* ESTO ES IMPORTANTE, PUES:
|
175 |
* a) un punto origina un nodo.
|
176 |
* b) una linea origina dos nodos
|
177 |
* c) un poligono origina un nodo.
|
178 |
*
|
179 |
* */
|
180 |
copyPoints(0);
|
181 |
copyPoints(1);
|
182 |
if(! isReused) //esto solo se hace si no se ha calculado ya |
183 |
arg[0].computeSelfNodes(li, false); |
184 |
arg[1].computeSelfNodes(li, false); |
185 |
|
186 |
|
187 |
/*
|
188 |
* Calcula las intersecciones.
|
189 |
* Se supone que daran lugar a Nodes, ?NO?
|
190 |
* Como resultado, cada Edge guardar? en sus EdgeIntersectionList
|
191 |
* las intersecciones que hay en sus segmentos (EdgeIntersection).
|
192 |
*
|
193 |
* Estas intersecciones se representan por:
|
194 |
* -segmento del edge en que ocurren.
|
195 |
* -coordenada
|
196 |
* -distancia al primer vertice del segmento
|
197 |
*
|
198 |
* ?OJO? COMO RESULTADO DE ESTO NO SE GENERAN EJES NUEVOS.
|
199 |
* PARA HACER SNAP EN LAS INTERSECCIONES TENDRIAMOS QUE RETOCAR LA
|
200 |
* CLASE EDGEINTERSECTIONLIST
|
201 |
*
|
202 |
* */
|
203 |
arg[0].computeEdgeIntersections(arg[1], li, true); |
204 |
/*
|
205 |
* Ahora lo que se hace es: para cada Edge del grafo,
|
206 |
* se parte (en funci?n de sus intersecciones) y se a?aden
|
207 |
* los Edges fragmentados a la colecci?n baseSplitEdges
|
208 |
*
|
209 |
* */
|
210 |
|
211 |
List baseSplitEdges = new ArrayList(); |
212 |
arg[0].computeSplitEdges(baseSplitEdges);
|
213 |
//TODO Quizas la clave est? tambien en la 2? geometria
|
214 |
arg[1].computeSplitEdges(baseSplitEdges);
|
215 |
|
216 |
|
217 |
/*
|
218 |
* Edges resulting of A intersection B, that are in baseSplitEdges
|
219 |
* Collection, are saved in EdgeList.
|
220 |
* ?OJO? Si aparecen ejes repetidos, no se duplican (pero si
|
221 |
* que se cambia su etiqueta)
|
222 |
* */
|
223 |
//Se copian los nuevos Edges generados en EdgeList
|
224 |
insertUniqueEdges(baseSplitEdges); |
225 |
|
226 |
|
227 |
/*Se etiquetan*/
|
228 |
computeLabelsFromDepths(); |
229 |
|
230 |
/*
|
231 |
* Quita los Edges que hayan sufrido colapso dimensional
|
232 |
* (en la documentac?on de JTS viene algo de esto)
|
233 |
* */
|
234 |
replaceCollapsedEdges(); |
235 |
|
236 |
|
237 |
/*
|
238 |
* Finalmente, se a?ade al SnappingPlanarGraph resultado los Edges
|
239 |
* calculados como fruto de las intersecciones (contenidos en EdgeList).
|
240 |
*
|
241 |
* Aqu? se hace algo muy importante tambi?n: se a?aden nuevos nodos
|
242 |
* al grafo (correspondientes con los extremos de los nuevos Edge
|
243 |
* que no estuvieran ya en el grafo)
|
244 |
*
|
245 |
* */
|
246 |
graph.addEdges(edgeList.getEdges()); |
247 |
|
248 |
|
249 |
computeLabelling(); |
250 |
labelIncompleteNodes(); |
251 |
|
252 |
/**
|
253 |
* The ordering of building the result Geometries is important. Areas
|
254 |
* must be built before lines, which must be built before points. This
|
255 |
* is so that lines which are covered by areas are not included
|
256 |
* explicitly, and similarly for points.
|
257 |
*/
|
258 |
findResultAreaEdges(opCode); |
259 |
cancelDuplicateResultEdges(); |
260 |
|
261 |
|
262 |
//TODO Todos los builders deber?n usar los metodos snap de locator
|
263 |
SnapPolygonBuilder polyBuilder = new SnapPolygonBuilder(geomFact, cga);
|
264 |
polyBuilder.add(graph); |
265 |
resultPolyList = polyBuilder.getPolygons(); |
266 |
|
267 |
LineBuilder lineBuilder = new LineBuilder(this, geomFact, ptLocator); |
268 |
resultLineList = lineBuilder.build(opCode); |
269 |
|
270 |
PointBuilder pointBuilder = new PointBuilder(this, geomFact, ptLocator){ |
271 |
public List build(int opCode) |
272 |
{ |
273 |
for (Iterator nodeit = getGraph().getNodes().iterator(); nodeit.hasNext(); ) { |
274 |
Node n = (Node) nodeit.next(); |
275 |
|
276 |
// filter out nodes which are known to be in the result
|
277 |
if (n.isInResult())
|
278 |
continue;
|
279 |
// if an incident edge is in the result, then the node coordinate is included already
|
280 |
if (n.isIncidentEdgeInResult())
|
281 |
continue;
|
282 |
if (n.getEdges().getDegree() == 0 || opCode == OverlayOp.INTERSECTION) { |
283 |
|
284 |
/**
|
285 |
* For nodes on edges, only INTERSECTION can result in edge nodes being included even
|
286 |
* if none of their incident edges are included
|
287 |
*/
|
288 |
Label label = n.getLabel();
|
289 |
if (SnappingOverlayOperation.checkLabelLocation(label.getLocation(0), |
290 |
label.getLocation(1), opCode)) {
|
291 |
filterCoveredNodeToPoint(n); |
292 |
} |
293 |
} |
294 |
} |
295 |
return resultPointList;
|
296 |
} |
297 |
|
298 |
|
299 |
|
300 |
private void filterCoveredNodeToPoint(Node n) |
301 |
{ |
302 |
Coordinate coord = n.getCoordinate(); |
303 |
if (! isCoveredByLA(coord)) {
|
304 |
Point pt = geomFact.createPoint(coord);
|
305 |
resultPointList.add(pt); |
306 |
} |
307 |
} |
308 |
}; |
309 |
resultPointList = pointBuilder.build(opCode); |
310 |
|
311 |
// gather the results from all calculations into a single Geometry for
|
312 |
// the result set
|
313 |
resultGeom = computeGeometry(resultPointList, resultLineList, |
314 |
resultPolyList); |
315 |
} |
316 |
|
317 |
|
318 |
/**
|
319 |
* This method will handle arguments of Location.NONE correctly
|
320 |
*
|
321 |
* @return true if the locations correspond to the opCode
|
322 |
*/
|
323 |
public static boolean isResultOfOp(int loc0, int loc1, int opCode) |
324 |
{ |
325 |
if (loc0 == Location.BOUNDARY) loc0 = Location.INTERIOR;
|
326 |
if (loc1 == Location.BOUNDARY) loc1 = Location.INTERIOR;
|
327 |
switch (opCode) {
|
328 |
case INTERSECTION:
|
329 |
return loc0 == Location.INTERIOR
|
330 |
&& loc1 == Location.INTERIOR; |
331 |
case UNION:
|
332 |
return loc0 == Location.INTERIOR
|
333 |
|| loc1 == Location.INTERIOR; |
334 |
case DIFFERENCE:
|
335 |
return loc0 == Location.INTERIOR
|
336 |
&& loc1 != Location.INTERIOR; |
337 |
case SYMDIFFERENCE:
|
338 |
return ( loc0 == Location.INTERIOR && loc1 != Location.INTERIOR)
|
339 |
|| ( loc0 != Location.INTERIOR && loc1 == Location.INTERIOR); |
340 |
} |
341 |
return false; |
342 |
} |
343 |
|
344 |
public static boolean isResultOfOp(Label label, int opCode) |
345 |
{ |
346 |
int loc0 = label.getLocation(0); |
347 |
int loc1 = label.getLocation(1); |
348 |
return isResultOfOp(loc0, loc1, opCode);
|
349 |
} |
350 |
|
351 |
|
352 |
//TODO Quitar esto de aqui
|
353 |
|
354 |
public static boolean checkLabelLocation(int loc0, int loc1, int opCode) |
355 |
{ |
356 |
if (loc0 == Location.BOUNDARY) loc0 = Location.INTERIOR;
|
357 |
if (loc1 == Location.BOUNDARY) loc1 = Location.INTERIOR;
|
358 |
switch (opCode) {
|
359 |
case INTERSECTION:
|
360 |
return loc0 == Location.INTERIOR
|
361 |
&& loc1 == Location.INTERIOR; |
362 |
case UNION:
|
363 |
return loc0 == Location.INTERIOR
|
364 |
|| loc1 == Location.INTERIOR; |
365 |
case DIFFERENCE:
|
366 |
return loc0 == Location.INTERIOR
|
367 |
&& loc1 != Location.INTERIOR; |
368 |
case SYMDIFFERENCE:
|
369 |
return ( loc0 == Location.INTERIOR && loc1 != Location.INTERIOR)
|
370 |
|| ( loc0 != Location.INTERIOR && loc1 == Location.INTERIOR); |
371 |
} |
372 |
return false; |
373 |
} |
374 |
|
375 |
private void insertUniqueEdges(List edges) { |
376 |
for (Iterator i = edges.iterator(); i.hasNext();) { |
377 |
Edge e = (Edge) i.next(); |
378 |
insertUniqueEdge(e); |
379 |
} |
380 |
} |
381 |
|
382 |
/**
|
383 |
* Insert an edge from one of the noded input graphs. Checks edges that are
|
384 |
* inserted to see if an identical edge already exists. If so, the edge is
|
385 |
* not inserted, but its label is merged with the existing edge.
|
386 |
*/
|
387 |
protected void insertUniqueEdge(Edge e) { |
388 |
|
389 |
//TODO Crear una clase SnapEdge y SnapEdgeList puede ser necesario???
|
390 |
//creo que si pq SnapEdgeList mantiene una cache que no considera snap
|
391 |
Edge existingEdge = edgeList.findEqualEdge(e); |
392 |
// If an identical edge already exists, simply update its label
|
393 |
if (existingEdge != null) { |
394 |
Label existingLabel = existingEdge.getLabel();
|
395 |
Label labelToMerge = e.getLabel();
|
396 |
|
397 |
// check if new edge is in reverse direction to existing edge
|
398 |
// if so, must flip the label before merging it
|
399 |
if (!existingEdge.isPointwiseEqual(e)) {
|
400 |
labelToMerge = new Label(e.getLabel()); |
401 |
labelToMerge.flip(); |
402 |
} |
403 |
Depth depth = existingEdge.getDepth(); |
404 |
// if this is the first duplicate found for this edge, initialize
|
405 |
// the depths
|
406 |
if (depth.isNull()) {
|
407 |
depth.add(existingLabel); |
408 |
} |
409 |
depth.add(labelToMerge); |
410 |
existingLabel.merge(labelToMerge); |
411 |
} else { // no matching existing edge was found |
412 |
// add this new edge to the list of edges in this graph
|
413 |
edgeList.add(e); |
414 |
} |
415 |
} |
416 |
|
417 |
|
418 |
/**
|
419 |
* Update the labels for edges according to their depths. For each edge, the
|
420 |
* depths are first normalized. Then, if the depths for the edge are equal,
|
421 |
* this edge must have collapsed into a line edge. If the depths are not
|
422 |
* equal, update the label with the locations corresponding to the depths
|
423 |
* (i.e. a depth of 0 corresponds to a Location of EXTERIOR, a depth of 1
|
424 |
* corresponds to INTERIOR)
|
425 |
*/
|
426 |
private void computeLabelsFromDepths() { |
427 |
for (Iterator it = edgeList.iterator(); it.hasNext();) { |
428 |
Edge e = (Edge) it.next(); |
429 |
Label lbl = e.getLabel();
|
430 |
Depth depth = e.getDepth(); |
431 |
/*
|
432 |
* Only check edges for which there were duplicates, since these are
|
433 |
* the only ones which might be the result of dimensional collapses.
|
434 |
*/
|
435 |
if (!depth.isNull()) {
|
436 |
depth.normalize(); |
437 |
for (int i = 0; i < 2; i++) { |
438 |
if (!lbl.isNull(i) && lbl.isArea() && !depth.isNull(i)) {
|
439 |
/**
|
440 |
* if the depths are equal, this edge is the result of
|
441 |
* the dimensional collapse of two or more edges. It has
|
442 |
* the same location on both sides of the edge, so it
|
443 |
* has collapsed to a line.
|
444 |
*/
|
445 |
if (depth.getDelta(i) == 0) { |
446 |
lbl.toLine(i); |
447 |
} else {
|
448 |
/**
|
449 |
* This edge may be the result of a dimensional
|
450 |
* collapse, but it still has different locations on
|
451 |
* both sides. The label of the edge must be updated
|
452 |
* to reflect the resultant side locations indicated
|
453 |
* by the depth values.
|
454 |
*/
|
455 |
Assert |
456 |
.isTrue(!depth.isNull(i, Position.LEFT),
|
457 |
"depth of LEFT side has not been initialized");
|
458 |
lbl.setLocation(i, Position.LEFT, depth
|
459 |
.getLocation(i, Position.LEFT));
|
460 |
Assert |
461 |
.isTrue(!depth.isNull(i, Position.RIGHT),
|
462 |
"depth of RIGHT side has not been initialized");
|
463 |
lbl.setLocation(i, Position.RIGHT, depth
|
464 |
.getLocation(i, Position.RIGHT));
|
465 |
} |
466 |
} |
467 |
} |
468 |
} |
469 |
} |
470 |
} |
471 |
|
472 |
/**
|
473 |
* If edges which have undergone dimensional collapse are found, replace
|
474 |
* them with a new edge which is a L edge
|
475 |
*/
|
476 |
private void replaceCollapsedEdges() { |
477 |
List newEdges = new ArrayList(); |
478 |
for (Iterator it = edgeList.iterator(); it.hasNext();) { |
479 |
Edge e = (Edge) it.next(); |
480 |
if (e.isCollapsed()) {
|
481 |
// Debug.print(e);
|
482 |
it.remove(); |
483 |
newEdges.add(e.getCollapsedEdge()); |
484 |
} |
485 |
} |
486 |
edgeList.addAll(newEdges); |
487 |
} |
488 |
|
489 |
/**
|
490 |
* Copy all nodes from an arg geometry into this graph. The node label in
|
491 |
* the arg geometry overrides any previously computed label for that
|
492 |
* argIndex. (E.g. a node may be an intersection node with a previously
|
493 |
* computed label of BOUNDARY, but in the original arg Geometry it is
|
494 |
* actually in the interior due to the Boundary Determination Rule)
|
495 |
*/
|
496 |
private void copyPoints(int argIndex) { |
497 |
for (Iterator i = arg[argIndex].getNodeIterator(); i.hasNext();) { |
498 |
Node graphNode = (Node) i.next(); |
499 |
Node newNode = graph.addNode(graphNode.getCoordinate()); |
500 |
newNode.setLabel(argIndex, graphNode.getLabel().getLocation( |
501 |
argIndex)); |
502 |
} |
503 |
} |
504 |
|
505 |
/**
|
506 |
* Compute initial labelling for all DirectedEdges at each node. In this
|
507 |
* step, DirectedEdges will acquire a complete labelling (i.e. one with
|
508 |
* labels for both Geometries) only if they are incident on a node which has
|
509 |
* edges for both Geometries
|
510 |
*/
|
511 |
private void computeLabelling() { |
512 |
for (Iterator nodeit = graph.getNodes().iterator(); nodeit.hasNext();) { |
513 |
Node node = (Node) nodeit.next(); |
514 |
node.getEdges().computeLabelling(arg); |
515 |
} |
516 |
mergeSymLabels(); |
517 |
updateNodeLabelling(); |
518 |
|
519 |
} |
520 |
|
521 |
/**
|
522 |
* For nodes which have edges from only one Geometry incident on them, the
|
523 |
* previous step will have left their dirEdges with no labelling for the
|
524 |
* other Geometry. However, the sym dirEdge may have a labelling for the
|
525 |
* other Geometry, so merge the two labels.
|
526 |
*/
|
527 |
private void mergeSymLabels() { |
528 |
for (Iterator nodeit = graph.getNodes().iterator(); nodeit.hasNext();) { |
529 |
Node node = (Node) nodeit.next(); |
530 |
((DirectedEdgeStar) node.getEdges()).mergeSymLabels(); |
531 |
} |
532 |
} |
533 |
|
534 |
private void updateNodeLabelling() { |
535 |
// update the labels for nodes
|
536 |
// The label for a node is updated from the edges incident on it
|
537 |
// (Note that a node may have already been labelled
|
538 |
// because it is a point in one of the input geometries)
|
539 |
for (Iterator nodeit = graph.getNodes().iterator(); nodeit.hasNext();) { |
540 |
Node node = (Node) nodeit.next(); |
541 |
Label lbl = ((DirectedEdgeStar) node.getEdges()).getLabel();
|
542 |
Label otherLbl = node.getLabel();
|
543 |
otherLbl.merge(lbl); |
544 |
} |
545 |
} |
546 |
|
547 |
/**
|
548 |
* Incomplete nodes are nodes whose labels are incomplete. (e.g. the
|
549 |
* location for one Geometry is null). These are either isolated nodes, or
|
550 |
* nodes which have edges from only a single Geometry incident on them.
|
551 |
*
|
552 |
* Isolated nodes are found because nodes in one graph which don't intersect
|
553 |
* nodes in the other are not completely labelled by the initial process of
|
554 |
* adding nodes to the nodeList. To complete the labelling we need to check
|
555 |
* for nodes that lie in the interior of edges, and in the interior of
|
556 |
* areas.
|
557 |
* <p>
|
558 |
* When each node labelling is completed, the labelling of the incident
|
559 |
* edges is updated, to complete their labelling as well.
|
560 |
*/
|
561 |
private void labelIncompleteNodes() { |
562 |
for (Iterator ni = graph.getNodes().iterator(); ni.hasNext();) { |
563 |
Node n = (Node) ni.next(); |
564 |
Label label = n.getLabel();
|
565 |
if (n.isIsolated()) {
|
566 |
if (label.isNull(0)) |
567 |
labelIncompleteNode(n, 0);
|
568 |
else
|
569 |
labelIncompleteNode(n, 1);
|
570 |
} |
571 |
// now update the labelling for the DirectedEdges incident on this
|
572 |
// node
|
573 |
((DirectedEdgeStar) n.getEdges()).updateLabelling(label); |
574 |
} |
575 |
} |
576 |
|
577 |
/**
|
578 |
* Label an isolated node with its relationship to the target geometry.
|
579 |
*/
|
580 |
private void labelIncompleteNode(Node n, int targetIndex) { |
581 |
//TODO Ver si el pointLocator deberia snapear
|
582 |
Coordinate coord = n.getCoordinate(); |
583 |
Geometry geom = arg[targetIndex].getGeometry(); |
584 |
int loc = ptLocator.locate(coord, geom, snapTolerance);
|
585 |
n.getLabel().setLocation(targetIndex, loc); |
586 |
} |
587 |
|
588 |
/**
|
589 |
* Find all edges whose label indicates that they are in the result area(s),
|
590 |
* according to the operation being performed. Since we want polygon shells
|
591 |
* to be oriented CW, choose dirEdges with the interior of the result on the
|
592 |
* RHS. Mark them as being in the result. Interior Area edges are the result
|
593 |
* of dimensional collapses. They do not form part of the result area
|
594 |
* boundary.
|
595 |
*/
|
596 |
private void findResultAreaEdges(int opCode) { |
597 |
for (Iterator it = graph.getEdgeEnds().iterator(); it.hasNext();) { |
598 |
DirectedEdge de = (DirectedEdge) it.next(); |
599 |
// mark all dirEdges with the appropriate label
|
600 |
Label label = de.getLabel();
|
601 |
if (label.isArea()
|
602 |
&& !de.isInteriorAreaEdge() |
603 |
&& isResultOfOp(label.getLocation(0, Position.RIGHT), label |
604 |
.getLocation(1, Position.RIGHT), opCode)) { |
605 |
de.setInResult(true);
|
606 |
// Debug.print("in result "); Debug.println(de);
|
607 |
} |
608 |
} |
609 |
} |
610 |
|
611 |
/**
|
612 |
* If both a dirEdge and its sym are marked as being in the result, cancel
|
613 |
* them out.
|
614 |
*/
|
615 |
private void cancelDuplicateResultEdges() { |
616 |
// remove any dirEdges whose sym is also included
|
617 |
// (they "cancel each other out")
|
618 |
for (Iterator it = graph.getEdgeEnds().iterator(); it.hasNext();) { |
619 |
DirectedEdge de = (DirectedEdge) it.next(); |
620 |
DirectedEdge sym = de.getSym(); |
621 |
if (de.isInResult() && sym.isInResult()) {
|
622 |
de.setInResult(false);
|
623 |
sym.setInResult(false);
|
624 |
// Debug.print("cancelled "); Debug.println(de);
|
625 |
// Debug.println(sym);
|
626 |
} |
627 |
} |
628 |
} |
629 |
|
630 |
/**
|
631 |
* This method is used to decide if a point node should be included in the
|
632 |
* result or not.
|
633 |
*
|
634 |
* @return true if the coord point is covered by a result Line or Area
|
635 |
* geometry
|
636 |
*/
|
637 |
public boolean isCoveredByLA(Coordinate coord) { |
638 |
if (isCovered(coord, resultLineList))
|
639 |
return true; |
640 |
if (isCovered(coord, resultPolyList))
|
641 |
return true; |
642 |
return false; |
643 |
} |
644 |
|
645 |
/**
|
646 |
* This method is used to decide if an L edge should be included in the
|
647 |
* result or not.
|
648 |
*
|
649 |
* @return true if the coord point is covered by a result Area geometry
|
650 |
*/
|
651 |
public boolean isCoveredByA(Coordinate coord) { |
652 |
if (isCovered(coord, resultPolyList))
|
653 |
return true; |
654 |
return false; |
655 |
} |
656 |
|
657 |
/**
|
658 |
* @return true if the coord is located in the interior or boundary of a
|
659 |
* geometry in the list.
|
660 |
*/
|
661 |
private boolean isCovered(Coordinate coord, List geomList) { |
662 |
for (Iterator it = geomList.iterator(); it.hasNext();) { |
663 |
Geometry geom = (Geometry) it.next(); |
664 |
int loc = ptLocator.locate(coord, geom, snapTolerance);
|
665 |
if (loc != Location.EXTERIOR)
|
666 |
return true; |
667 |
} |
668 |
return false; |
669 |
} |
670 |
|
671 |
private Geometry computeGeometry(List resultPointList, List resultLineList, |
672 |
List resultPolyList) {
|
673 |
List geomList = new ArrayList(); |
674 |
// element geometries of the result are always in the order P,L,A
|
675 |
geomList.addAll(resultPointList); |
676 |
geomList.addAll(resultLineList); |
677 |
geomList.addAll(resultPolyList); |
678 |
// build the most specific geometry possible
|
679 |
return geomFact.buildGeometry(geomList);
|
680 |
} |
681 |
|
682 |
|
683 |
public static void main(String[] args){ |
684 |
GeometryFactory factory = new GeometryFactory();
|
685 |
com.vividsolutions.jts.io.WKTReader reader = new com.vividsolutions.jts.io.WKTReader(factory);
|
686 |
Geometry a, b, c, d; |
687 |
try {
|
688 |
|
689 |
//Snap en un extremo y en un vertice intermedio
|
690 |
a = reader.read("LINESTRING(0.001 0.001, 5.001 5.001)");
|
691 |
b = reader.read("LINESTRING(2.1 -3, 0.0 -0.001, -2.22 4.88, 10.0 10.0, 5.002 5.002)");
|
692 |
System.out.println(SnappingOverlayOperation.overlayOp(a, b, OverlayOp.INTERSECTION, 0.01)); |
693 |
// //snap mediante l?neas paralelas
|
694 |
c = reader.read("LINESTRING(0 0, 5 0, 10 0.001)");
|
695 |
d = reader.read("LINESTRING(0.001 0.01, 5.001 0.002, 10.001 0.002)");
|
696 |
long t0 = System.currentTimeMillis(); |
697 |
System.out.println(SnappingOverlayOperation.overlayOp(c, d, OverlayOp.INTERSECTION, 0.1)); |
698 |
long t1 = System.currentTimeMillis(); |
699 |
System.out.println(OverlayOp.overlayOp(c, d, OverlayOp.INTERSECTION));
|
700 |
long t2 = System.currentTimeMillis(); |
701 |
System.out.println("Con snap: "+(t1-t0)+" ms"); |
702 |
System.out.println("Sin snap: "+(t2-t1)+" ms"); |
703 |
|
704 |
d = reader.read("LINESTRING(0 0, 5 0, 10 0.001)");
|
705 |
System.out.println(OverlayOp.overlayOp(c, d, OverlayOp.INTERSECTION));
|
706 |
|
707 |
//lineas paralelas a una distancia superior a la de snap
|
708 |
//(para comprobar el criterio de paralelismo en LineIntersector
|
709 |
c = reader.read("LINESTRING(0 0, 5 0, 10 0.001)");
|
710 |
d = reader.read("LINESTRING(0 0.11, 5 0.12, 10 0.14)");
|
711 |
System.out.println(SnappingOverlayOperation.overlayOp(c, d, OverlayOp.INTERSECTION, 0.001)); |
712 |
//
|
713 |
c = reader.read("LINESTRING(1 0, 3 2)");
|
714 |
d = reader.read("LINESTRING(3.05 2.01, 5 1.25, 0.25 1.75)");
|
715 |
System.out.println(OverlayOp.overlayOp(c, d, OverlayOp.INTERSECTION));
|
716 |
System.out.println((SnappingOverlayOperation.overlayOp(c, d, OverlayOp.INTERSECTION, 0.1))); |
717 |
//
|
718 |
//
|
719 |
d = reader.read("LINESTRING(3 2, 5 1.25, 0.25 1.75)");
|
720 |
System.out.println(OverlayOp.overlayOp(c, d, OverlayOp.INTERSECTION));
|
721 |
System.out.println((SnappingOverlayOperation.overlayOp(c, d, OverlayOp.INTERSECTION, 0.1))); |
722 |
|
723 |
//Que un pol?gono est? cerrado o no no es snap, sino regla topologica
|
724 |
|
725 |
//TODO CON POLIGONOS EST? DANDO PROBLEMAS. HABRA QUE REVISAR LINEAS Y POLIGONOS
|
726 |
// c = reader.read("POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))");
|
727 |
// d = reader.read("POLYGON((-0.01 0, 3 8, 6 6 , -0.01 0))");
|
728 |
|
729 |
c = reader.read("POLYGON((5 0, 5 5, 10 5, 10 0, 5 0))");
|
730 |
d = reader.read("POLYGON((4 3, 4.99 3.5, 10.01 3.5, 12 3, 4 3))");
|
731 |
|
732 |
|
733 |
|
734 |
//REVISI?N TOPOLOGICA
|
735 |
/*
|
736 |
* Un aspecto esencial de la topologia en JTS es el etiquetado.
|
737 |
* Todo Eje del grafo asociado a un pol?gono tiene una etiqueta o Label,
|
738 |
* con tres valores posibles para la izquierda, derecha y encima del poligono
|
739 |
* (EXTERIOR, BOUNDARY, INTERIOR)
|
740 |
*
|
741 |
* Por tanto, si la orientaci?n no es la correcta, todo se va al traste
|
742 |
* (pues las cosas se invierten especularmente)
|
743 |
* */
|
744 |
if(CGAlgorithms.isCCW(c.getCoordinates())){
|
745 |
System.out.println("Anillo exterior de poligono en orden incorrecto"); |
746 |
System.out.println(c.toText());
|
747 |
System.exit(-2); |
748 |
} |
749 |
if(CGAlgorithms.isCCW(d.getCoordinates())){
|
750 |
System.out.println("Anillo exterior de poligono en orden incorrecto"); |
751 |
System.out.println(d.toText());
|
752 |
System.exit(-2); |
753 |
} |
754 |
|
755 |
System.out.println((SnappingOverlayOperation.overlayOp(c, d, OverlayOp.INTERSECTION, 0.1))); |
756 |
|
757 |
Geometry pol1 = reader.read("POLYGON((0 0, -5 0, -10 5, 0 10, 10 5, 5 0, 0 0))");
|
758 |
Geometry pol2 = reader.read("POLYGON((10.01 0, 5 5, 5 10, 10 10, 10.01 0))");
|
759 |
|
760 |
System.out.println((SnappingOverlayOperation.overlayOp(pol1, pol2, OverlayOp.INTERSECTION, 0.1))); |
761 |
System.out.println((OverlayOp.overlayOp(pol1, pol2, OverlayOp.INTERSECTION)));
|
762 |
|
763 |
|
764 |
} catch (ParseException e) { |
765 |
e.printStackTrace(); |
766 |
} |
767 |
|
768 |
|
769 |
} |
770 |
|
771 |
} |