svn-gvsig-desktop / branches / v10 / extensions / extGraph_predes / src / com / vividsolutions / jts / geomgraph / SnappingNodeMap.java @ 8766
History | View | Annotate | Download (15.2 KB)
1 |
/*
|
---|---|
2 |
* Created on 11-sep-2006 by azabala
|
3 |
*
|
4 |
*/
|
5 |
package com.vividsolutions.jts.geomgraph; |
6 |
|
7 |
import java.util.ArrayList; |
8 |
import java.util.Collection; |
9 |
import java.util.Collections; |
10 |
import java.util.Comparator; |
11 |
import java.util.HashMap; |
12 |
import java.util.Iterator; |
13 |
import java.util.List; |
14 |
|
15 |
import com.vividsolutions.jts.algorithms.SnapSimplePointInAreaLocator; |
16 |
import com.vividsolutions.jts.geom.Coordinate; |
17 |
import com.vividsolutions.jts.geom.Envelope; |
18 |
import com.vividsolutions.jts.geom.Location; |
19 |
import com.vividsolutions.jts.geom.TopologyException; |
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.EdgeEnd; |
24 |
import com.vividsolutions.jts.geomgraph.EdgeEndStar; |
25 |
import com.vividsolutions.jts.geomgraph.GeometryGraph; |
26 |
import com.vividsolutions.jts.geomgraph.Label; |
27 |
import com.vividsolutions.jts.geomgraph.Node; |
28 |
import com.vividsolutions.jts.geomgraph.NodeFactory; |
29 |
import com.vividsolutions.jts.geomgraph.NodeMap; |
30 |
import com.vividsolutions.jts.geomgraph.Position; |
31 |
import com.vividsolutions.jts.util.Assert; |
32 |
|
33 |
/**
|
34 |
* Repository of nodes of a PlanarGraph that applies a snap tolerance.
|
35 |
*
|
36 |
* If we ask for a node, and it founds a node in the tolerance distance it
|
37 |
* returns the found node.
|
38 |
*
|
39 |
*
|
40 |
*
|
41 |
* @author alzabord
|
42 |
*/
|
43 |
public class SnappingNodeMap extends NodeMap { |
44 |
|
45 |
|
46 |
|
47 |
// Esto va a ir muy lento
|
48 |
// buscar otros mecanismos (indice espacial, o hashmap)
|
49 |
protected HashMap nodeMap; |
50 |
|
51 |
private class SnapDirectedEdgeStar extends DirectedEdgeStar { |
52 |
|
53 |
/**
|
54 |
* The location of the point for this star in Geometry i Areas
|
55 |
*/
|
56 |
private int[] ptInAreaLocation = { Location.NONE, Location.NONE }; |
57 |
|
58 |
private Label label; |
59 |
|
60 |
List resultAreaEdgeList = null; |
61 |
|
62 |
List getResultAreaEdges() {
|
63 |
if (resultAreaEdgeList != null) |
64 |
return resultAreaEdgeList;
|
65 |
resultAreaEdgeList = new ArrayList(); |
66 |
for (Iterator it = iterator(); it.hasNext();) { |
67 |
DirectedEdge de = (DirectedEdge) it.next(); |
68 |
if (de.isInResult() || de.getSym().isInResult())
|
69 |
resultAreaEdgeList.add(de); |
70 |
} |
71 |
return resultAreaEdgeList;
|
72 |
} |
73 |
|
74 |
private final int SCANNING_FOR_INCOMING = 1; |
75 |
|
76 |
private final int LINKING_TO_OUTGOING = 2; |
77 |
|
78 |
private SnapDirectedEdgeStar() {
|
79 |
super();
|
80 |
|
81 |
edgeList = new ArrayList(); |
82 |
|
83 |
} |
84 |
|
85 |
/**
|
86 |
* Traverse the star of DirectedEdges, linking the included edges
|
87 |
* together. To link two dirEdges, the <next> pointer for an incoming
|
88 |
* dirEdge is set to the next outgoing edge.
|
89 |
* <p>
|
90 |
* DirEdges are only linked if:
|
91 |
* <ul>
|
92 |
* <li>they belong to an area (i.e. they have sides)
|
93 |
* <li>they are marked as being in the result
|
94 |
* </ul>
|
95 |
* <p>
|
96 |
* Edges are linked in CCW order (the order they are stored). This means
|
97 |
* that rings have their face on the Right (in other words, the
|
98 |
* topological location of the face is given by the RHS label of the
|
99 |
* DirectedEdge)
|
100 |
* <p>
|
101 |
* PRECONDITION: No pair of dirEdges are both marked as being in the
|
102 |
* result
|
103 |
*/
|
104 |
public void linkResultDirectedEdges() { |
105 |
// make sure edges are copied to resultAreaEdges list
|
106 |
List resultEdges = getResultAreaEdges();
|
107 |
// find first area edge (if any) to start linking at
|
108 |
DirectedEdge firstOut = null;
|
109 |
DirectedEdge incoming = null;
|
110 |
int state = SCANNING_FOR_INCOMING;
|
111 |
// link edges in CCW order
|
112 |
for (int i = 0; i < resultAreaEdgeList.size(); i++) { |
113 |
DirectedEdge nextOut = (DirectedEdge) resultEdges.get(i); |
114 |
DirectedEdge nextIn = nextOut.getSym(); |
115 |
|
116 |
// skip de's that we're not interested in
|
117 |
if (!nextOut.getLabel().isArea())
|
118 |
continue;
|
119 |
|
120 |
// record first outgoing edge, in order to link the last
|
121 |
// incoming edge
|
122 |
if (firstOut == null && nextOut.isInResult()) |
123 |
firstOut = nextOut; |
124 |
// assert: sym.isInResult() == false, since pairs of dirEdges
|
125 |
// should have been removed already
|
126 |
|
127 |
switch (state) {
|
128 |
case SCANNING_FOR_INCOMING:
|
129 |
if (!nextIn.isInResult())
|
130 |
continue;
|
131 |
incoming = nextIn; |
132 |
state = LINKING_TO_OUTGOING; |
133 |
break;
|
134 |
case LINKING_TO_OUTGOING:
|
135 |
if (!nextOut.isInResult())
|
136 |
continue;
|
137 |
incoming.setNext(nextOut); |
138 |
state = SCANNING_FOR_INCOMING; |
139 |
break;
|
140 |
} |
141 |
}// for
|
142 |
if (state == LINKING_TO_OUTGOING) {
|
143 |
// Debug.print(firstOut == null, this);
|
144 |
if (firstOut == null) |
145 |
throw new TopologyException("no outgoing dirEdge found", |
146 |
getCoordinate()); |
147 |
// Assert.isTrue(firstOut != null, "no outgoing dirEdge found
|
148 |
// (at " + getCoordinate() );
|
149 |
Assert.isTrue(firstOut.isInResult(), |
150 |
"unable to link last incoming dirEdge");
|
151 |
incoming.setNext(firstOut); |
152 |
} |
153 |
} |
154 |
|
155 |
/**
|
156 |
* Insert an EdgeEnd into the map, and clear the edgeList cache, since
|
157 |
* the list of edges has now changed
|
158 |
*/
|
159 |
protected void insertEdgeEnd(EdgeEnd e, Object obj) { |
160 |
edgeMap.put(e, obj); |
161 |
if (edgeList == null) |
162 |
edgeList = new ArrayList(); |
163 |
edgeList.add(e); |
164 |
|
165 |
// Necesitamos que la "estrella" de Ejes asociada a un Nodo conserve
|
166 |
// siempre un orden antihorario. Por eso, cada vez que se a?ada un
|
167 |
// nuevo
|
168 |
// eje solo se inserta en el Map (que mantiene el orden)
|
169 |
// y la cache se pone a null
|
170 |
|
171 |
// edgeList = null;
|
172 |
} |
173 |
|
174 |
public Iterator iterator() { |
175 |
return getEdges().iterator();
|
176 |
} |
177 |
|
178 |
public List getEdges() { |
179 |
Collections.sort(edgeList, new Comparator() { |
180 |
public int compare(Object arg0, Object arg1) { |
181 |
EdgeEnd e0 = (EdgeEnd) arg0; |
182 |
EdgeEnd e1 = (EdgeEnd) arg1; |
183 |
return e0.compareTo(e1);
|
184 |
} |
185 |
}); |
186 |
// if (edgeList == null) {
|
187 |
// edgeList = new ArrayList(edgeMap.values());
|
188 |
// }
|
189 |
return edgeList;
|
190 |
} |
191 |
|
192 |
public Label getLabel() { |
193 |
return label;
|
194 |
} |
195 |
|
196 |
void computeEdgeEndLabels() {
|
197 |
// Compute edge label for each EdgeEnd
|
198 |
for (Iterator it = iterator(); it.hasNext();) { |
199 |
EdgeEnd ee = (EdgeEnd) it.next(); |
200 |
ee.computeLabel(); |
201 |
} |
202 |
} |
203 |
|
204 |
void propagateSideLabels(int geomIndex) { |
205 |
// Since edges are stored in CCW order around the node,
|
206 |
// As we move around the ring we move from the right to the left
|
207 |
// side of the edge
|
208 |
int startLoc = Location.NONE;
|
209 |
// initialize loc to location of last L side (if any)
|
210 |
// System.out.println("finding start location");
|
211 |
for (Iterator it = iterator(); it.hasNext();) { |
212 |
EdgeEnd e = (EdgeEnd) it.next(); |
213 |
Label label = e.getLabel();
|
214 |
if (label.isArea(geomIndex)
|
215 |
&& label.getLocation(geomIndex, Position.LEFT) != Location.NONE)
|
216 |
startLoc = label.getLocation(geomIndex, Position.LEFT);
|
217 |
} |
218 |
// no labelled sides found, so no labels to propagate
|
219 |
if (startLoc == Location.NONE)
|
220 |
return;
|
221 |
|
222 |
int currLoc = startLoc;
|
223 |
for (Iterator it = iterator(); it.hasNext();) { |
224 |
EdgeEnd e = (EdgeEnd) it.next(); |
225 |
Label label = e.getLabel();
|
226 |
// set null ON values to be in current location
|
227 |
if (label.getLocation(geomIndex, Position.ON) == Location.NONE) |
228 |
label.setLocation(geomIndex, Position.ON, currLoc);
|
229 |
// set side labels (if any)
|
230 |
// if (label.isArea()) { //ORIGINAL
|
231 |
if (label.isArea(geomIndex)) {
|
232 |
int leftLoc = label.getLocation(geomIndex, Position.LEFT); |
233 |
int rightLoc = label.getLocation(geomIndex, Position.RIGHT); |
234 |
// if there is a right location, that is the next location
|
235 |
// to propagate
|
236 |
if (rightLoc != Location.NONE) {
|
237 |
// Debug.print(rightLoc != currLoc, this);
|
238 |
if (rightLoc != currLoc)
|
239 |
throw new TopologyException( |
240 |
"side location conflict", e.getCoordinate());
|
241 |
if (leftLoc == Location.NONE) {
|
242 |
Assert |
243 |
.shouldNeverReachHere("found single null side (at "
|
244 |
+ e.getCoordinate() + ")");
|
245 |
} |
246 |
currLoc = leftLoc; |
247 |
} else {
|
248 |
/**
|
249 |
* RHS is null - LHS must be null too. This must be an
|
250 |
* edge from the other geometry, which has no location
|
251 |
* labelling for this geometry. This edge must lie
|
252 |
* wholly inside or outside the other geometry (which is
|
253 |
* determined by the current location). Assign both
|
254 |
* sides to be the current location.
|
255 |
*/
|
256 |
Assert.isTrue(label.getLocation(geomIndex, |
257 |
Position.LEFT) == Location.NONE,
|
258 |
"found single null side");
|
259 |
label.setLocation(geomIndex, Position.RIGHT, currLoc);
|
260 |
label.setLocation(geomIndex, Position.LEFT, currLoc);
|
261 |
} |
262 |
} |
263 |
} |
264 |
} |
265 |
|
266 |
int getLocation(int geomIndex, Coordinate p, GeometryGraph[] geom) { |
267 |
// compute location only on demand
|
268 |
if (ptInAreaLocation[geomIndex] == Location.NONE) {
|
269 |
ptInAreaLocation[geomIndex] = SnapSimplePointInAreaLocator |
270 |
.locate(p, geom[geomIndex].getGeometry(), snapTolerance); |
271 |
} |
272 |
return ptInAreaLocation[geomIndex];
|
273 |
} |
274 |
|
275 |
public void mergeSymLabels() { |
276 |
for (Iterator it = iterator(); it.hasNext();) { |
277 |
DirectedEdge de = (DirectedEdge) it.next(); |
278 |
Label label = de.getLabel();
|
279 |
Label symLabel = de.getSym().getLabel();
|
280 |
label.merge(symLabel); |
281 |
} |
282 |
} |
283 |
|
284 |
/**
|
285 |
* Update incomplete dirEdge labels from the labelling for the node
|
286 |
*/
|
287 |
public void updateLabelling(Label nodeLabel) { |
288 |
for (Iterator it = iterator(); it.hasNext();) { |
289 |
DirectedEdge de = (DirectedEdge) it.next(); |
290 |
Label label = de.getLabel();
|
291 |
label.setAllLocationsIfNull(0, nodeLabel.getLocation(0)); |
292 |
label.setAllLocationsIfNull(1, nodeLabel.getLocation(1)); |
293 |
} |
294 |
} |
295 |
|
296 |
public void computeLabelling(GeometryGraph[] geom) { |
297 |
computeEdgeEndLabels(); |
298 |
propagateSideLabels(0);
|
299 |
propagateSideLabels(1);
|
300 |
boolean[] hasDimensionalCollapseEdge = { false, false }; |
301 |
for (Iterator it = iterator(); it.hasNext();) { |
302 |
EdgeEnd e = (EdgeEnd) it.next(); |
303 |
Label label = e.getLabel();
|
304 |
for (int geomi = 0; geomi < 2; geomi++) { |
305 |
if (label.isLine(geomi)
|
306 |
&& label.getLocation(geomi) == Location.BOUNDARY) |
307 |
hasDimensionalCollapseEdge[geomi] = true;
|
308 |
} |
309 |
} |
310 |
for (Iterator it = iterator(); it.hasNext();) { |
311 |
EdgeEnd e = (EdgeEnd) it.next(); |
312 |
Label label = e.getLabel();
|
313 |
for (int geomi = 0; geomi < 2; geomi++) { |
314 |
if (label.isAnyNull(geomi)) {
|
315 |
int loc = Location.NONE;
|
316 |
if (hasDimensionalCollapseEdge[geomi]) {
|
317 |
loc = Location.EXTERIOR; |
318 |
} else {
|
319 |
Coordinate p = e.getCoordinate(); |
320 |
loc = getLocation(geomi, p, geom); |
321 |
} |
322 |
label.setAllLocationsIfNull(geomi, loc); |
323 |
}// if
|
324 |
}// for
|
325 |
}// for
|
326 |
|
327 |
// determine the overall labelling for this DirectedEdgeStar
|
328 |
// (i.e. for the node it is based at)
|
329 |
label = new Label(Location.NONE); |
330 |
for (Iterator it = iterator(); it.hasNext();) { |
331 |
EdgeEnd ee = (EdgeEnd) it.next(); |
332 |
Edge e = ee.getEdge(); |
333 |
Label eLabel = e.getLabel();
|
334 |
for (int i = 0; i < 2; i++) { |
335 |
int eLoc = eLabel.getLocation(i);
|
336 |
if (eLoc == Location.INTERIOR || eLoc == Location.BOUNDARY)
|
337 |
label.setLocation(i, Location.INTERIOR); |
338 |
} |
339 |
} |
340 |
} |
341 |
} |
342 |
|
343 |
class SnapNode extends Node { |
344 |
|
345 |
public SnapNode(Coordinate arg0, EdgeEndStar arg1) {
|
346 |
super(arg0, arg1);
|
347 |
} |
348 |
|
349 |
public boolean equals(Object obj) { |
350 |
SnapNode other = (SnapNode) obj; |
351 |
return other.coord.distance(this.coord) <= snapTolerance; |
352 |
} |
353 |
|
354 |
public int hashCode() { |
355 |
return 1; // esto no es eficiente |
356 |
} |
357 |
} |
358 |
|
359 |
private double snapTolerance; |
360 |
|
361 |
public SnappingNodeMap(NodeFactory nodeFactory, double snapTolerance) { |
362 |
super(nodeFactory);
|
363 |
this.snapTolerance = snapTolerance;
|
364 |
// spatialIndex = new Quadtree();
|
365 |
nodeMap = new HashMap(); |
366 |
} |
367 |
|
368 |
class MinDistCoordComparator implements Comparator { |
369 |
Coordinate coord; |
370 |
|
371 |
MinDistCoordComparator(Coordinate coord) { |
372 |
this.coord = coord;
|
373 |
} |
374 |
|
375 |
public int compare(Object arg0, Object arg1) { |
376 |
Coordinate c1 = ((Node) arg0).getCoordinate(); |
377 |
Coordinate c2 = ((Node) arg1).getCoordinate(); |
378 |
|
379 |
double d1 = c1.distance(coord);
|
380 |
double d2 = c2.distance(coord);
|
381 |
|
382 |
if (d1 < d2)
|
383 |
return 1; |
384 |
if (d1 > d2)
|
385 |
return -1; |
386 |
else
|
387 |
return 0; |
388 |
} |
389 |
} |
390 |
|
391 |
private Envelope getQueryRect(Coordinate coord) {
|
392 |
double xmin = coord.x - snapTolerance;
|
393 |
double ymin = coord.y - snapTolerance;
|
394 |
double xmax = coord.x + snapTolerance;
|
395 |
double ymax = coord.y + snapTolerance;
|
396 |
Envelope queryRect = new Envelope(xmin, xmax, ymin, ymax);
|
397 |
return queryRect;
|
398 |
} |
399 |
|
400 |
public Node addNode(final Coordinate coord) { |
401 |
SnapNode candidate = null;
|
402 |
DirectedEdgeStar edgeStar = new SnapDirectedEdgeStar();
|
403 |
candidate = new SnapNode(coord, edgeStar);
|
404 |
|
405 |
/*
|
406 |
* PRUEBA PARA VER POR QU? DA ERRORES CON POLIGONOS
|
407 |
*
|
408 |
*
|
409 |
*
|
410 |
*/
|
411 |
|
412 |
Node stored = (Node) nodeMap.get(candidate); |
413 |
if (stored != null) |
414 |
return stored;
|
415 |
else {
|
416 |
nodeMap.put(candidate, candidate); |
417 |
return candidate;
|
418 |
} |
419 |
// Envelope queryRect = getQueryRect(coord);
|
420 |
// List nodes = spatialIndex.query(queryRect);
|
421 |
// Spatial Index est? devolviendo candidatos fuera del rectangulo
|
422 |
// ser? problema del quadtree
|
423 |
// if(nodes.size() != 0){
|
424 |
// Collections.sort(nodes, new MinDistCoordComparator(coord));
|
425 |
// Node candidate = (Node) nodes.get(0);
|
426 |
// if(candidate.getCoordinate().distance(coord) < snapTolerance )
|
427 |
// return candidate;
|
428 |
// }else{
|
429 |
// System.out.println("El nodo "+coord.x+","+coord.y+" no tiene entradas
|
430 |
// analogas en el quadtree");
|
431 |
// List all = this.spatialIndex.queryAll();
|
432 |
// System.out.println("en el quadtree "+all.size());
|
433 |
// for(int i = 0; i < all.size(); i++){
|
434 |
// Node node = (Node) all.get(i);
|
435 |
// Coordinate coord2 = node.getCoordinate();
|
436 |
// System.out.println(coord2.x + "," + coord2.y);
|
437 |
// }
|
438 |
// }
|
439 |
// Node solution = nodeFactory.createNode(coord);
|
440 |
// spatialIndex.insert(queryRect, solution);
|
441 |
// return solution;
|
442 |
} |
443 |
|
444 |
// FIXME: REVISAR SI HABR?A QUE HACER UN MERGE LABEL ARRIBA O AQU?
|
445 |
public Node addNode(Node n) {
|
446 |
|
447 |
Node node = addNode(n.getCoordinate()); |
448 |
node.mergeLabel(n); |
449 |
return node;
|
450 |
} |
451 |
|
452 |
/**
|
453 |
* Adds a node for the start point of this EdgeEnd (if one does not already
|
454 |
* exist in this map). Adds the EdgeEnd to the (possibly new) node.
|
455 |
*/
|
456 |
public void add(EdgeEnd e) { |
457 |
Coordinate p = e.getCoordinate(); |
458 |
Node n = addNode(p); |
459 |
n.add(e);// Si el nodo ya existe, se le a?ade una arista
|
460 |
} |
461 |
|
462 |
/**
|
463 |
* @return the node if found; null otherwise
|
464 |
*/
|
465 |
public Node find(Coordinate coord) {
|
466 |
// Envelope queryRect = getQueryRect(coord);
|
467 |
// List nodes = spatialIndex.query(getQueryRect(coord));
|
468 |
// Collections.sort(nodes, new MinDistCoordComparator(coord));
|
469 |
// Node candidate = (Node) nodes.get(0);
|
470 |
return (Node) nodeMap.get(new SnapNode(coord, null)); |
471 |
// return candidate;
|
472 |
} |
473 |
|
474 |
public Iterator iterator() { |
475 |
return nodeMap.values().iterator();
|
476 |
// return spatialIndex.queryAll().iterator();
|
477 |
} |
478 |
|
479 |
public Collection values() { |
480 |
return nodeMap.values();
|
481 |
// return spatialIndex.queryAll();
|
482 |
} |
483 |
|
484 |
public Collection getBoundaryNodes(int geomIndex) { |
485 |
Collection bdyNodes = new ArrayList(); |
486 |
for (Iterator i = iterator(); i.hasNext();) { |
487 |
Node node = (Node) i.next(); |
488 |
if (node.getLabel().getLocation(geomIndex) == Location.BOUNDARY)
|
489 |
bdyNodes.add(node); |
490 |
} |
491 |
return bdyNodes;
|
492 |
} |
493 |
|
494 |
public void dump() { |
495 |
System.out.println(this.toString()); |
496 |
Iterator it = iterator();
|
497 |
while (it.hasNext()) {
|
498 |
Node node = (Node) it.next(); |
499 |
Coordinate coord = node.getCoordinate(); |
500 |
System.out.println("x= " + coord.x + ", y= " + coord.y); |
501 |
} |
502 |
} |
503 |
|
504 |
public static void main(String[] args) { |
505 |
SnappingNodeMap nodeMap = new SnappingNodeMap(new NodeFactory(), 0.01); |
506 |
nodeMap.addNode(new Coordinate(0.001, 0.001)); |
507 |
nodeMap.addNode(new Coordinate(0.002, 0.002)); |
508 |
Iterator it = nodeMap.iterator();
|
509 |
while (it.hasNext()) {
|
510 |
Node node = (Node) it.next(); |
511 |
Coordinate coord = node.getCoordinate(); |
512 |
System.out.println("x= " + coord.x + ", y= " + coord.y); |
513 |
} |
514 |
} |
515 |
} |