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