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