root / trunk / extensions / extGeoProcessing / src / com / iver / cit / gvsig / geoprocess / spatialjoin / fmap / NearestHeuristicSpatialJoinVisitor.java @ 5628
History | View | Annotate | Download (9.83 KB)
1 | 5412 | azabala | /*
|
---|---|---|---|
2 | * Created on 25-abr-2006
|
||
3 | *
|
||
4 | * gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana
|
||
5 | *
|
||
6 | * Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.
|
||
7 | *
|
||
8 | * This program is free software; you can redistribute it and/or
|
||
9 | * modify it under the terms of the GNU General Public License
|
||
10 | * as published by the Free Software Foundation; either version 2
|
||
11 | * of the License, or (at your option) any later version.
|
||
12 | *
|
||
13 | * This program is distributed in the hope that it will be useful,
|
||
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
16 | * GNU General Public License for more details.
|
||
17 | *
|
||
18 | * You should have received a copy of the GNU General Public License
|
||
19 | * along with this program; if not, write to the Free Software
|
||
20 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
||
21 | *
|
||
22 | * For more information, contact:
|
||
23 | *
|
||
24 | * Generalitat Valenciana
|
||
25 | * Conselleria d'Infraestructures i Transport
|
||
26 | * Av. Blasco Ib??ez, 50
|
||
27 | * 46010 VALENCIA
|
||
28 | * SPAIN
|
||
29 | *
|
||
30 | * +34 963862235
|
||
31 | * gvsig@gva.es
|
||
32 | * www.gvsig.gva.es
|
||
33 | *
|
||
34 | * or
|
||
35 | *
|
||
36 | * IVER T.I. S.A
|
||
37 | * Salamanca 50
|
||
38 | * 46005 Valencia
|
||
39 | * Spain
|
||
40 | *
|
||
41 | * +34 963163400
|
||
42 | * dac@iver.es
|
||
43 | */
|
||
44 | /* CVS MESSAGES:
|
||
45 | *
|
||
46 | * $Id$
|
||
47 | * $Log$
|
||
48 | 5628 | azabala | * Revision 1.2 2006-06-02 18:21:28 azabala
|
49 | * *** empty log message ***
|
||
50 | *
|
||
51 | * Revision 1.1 2006/05/24 21:09:47 azabala
|
||
52 | 5412 | azabala | * primera version en cvs despues de refactoring orientado a crear un framework extensible de geoprocessing
|
53 | *
|
||
54 | * Revision 1.1 2006/05/01 19:09:09 azabala
|
||
55 | * Intento de optimizar el spatial join por vecino mas proximo (no funciona)
|
||
56 | *
|
||
57 | *
|
||
58 | */
|
||
59 | package com.iver.cit.gvsig.geoprocess.spatialjoin.fmap; |
||
60 | |||
61 | import java.awt.geom.Rectangle2D; |
||
62 | import java.util.Stack; |
||
63 | |||
64 | import com.iver.cit.gvsig.fmap.DriverException; |
||
65 | import com.iver.cit.gvsig.fmap.core.IFeature; |
||
66 | import com.iver.cit.gvsig.fmap.core.IGeometry; |
||
67 | import com.iver.cit.gvsig.fmap.layers.FBitSet; |
||
68 | import com.iver.cit.gvsig.fmap.layers.FLayer; |
||
69 | import com.iver.cit.gvsig.fmap.layers.FLyrVect; |
||
70 | import com.iver.cit.gvsig.fmap.operations.strategies.FeatureVisitor; |
||
71 | import com.iver.cit.gvsig.fmap.operations.strategies.VisitException; |
||
72 | import com.iver.cit.gvsig.geoprocess.core.fmap.FeatureProcessor; |
||
73 | import com.vividsolutions.jts.geom.Envelope; |
||
74 | import com.vividsolutions.jts.geom.Geometry; |
||
75 | import com.vividsolutions.jts.geom.GeometryFactory; |
||
76 | import com.vividsolutions.jts.operation.distance.DistanceOp; |
||
77 | /**
|
||
78 | * This visitor does nearest feature spatial join by applying an heuristic
|
||
79 | * strategy (in constract with NearestSpatialJoinVisitor, that does a
|
||
80 | * secuential scanning).
|
||
81 | * <br>
|
||
82 | * Which heuristic does this visitor apply?
|
||
83 | * It obtains second layer (target layer in spatial join) full extent,
|
||
84 | * and subdivide it in 4 envelopes. After that, it computes the distance
|
||
85 | * of the geometry we want to join with second layer, and computes
|
||
86 | * 4 distances with each one of the envelopes. Then, it recursively subdivide
|
||
87 | * the Envelope at the shortest distance.
|
||
88 | * <br>
|
||
89 | * This process is repeated recursively until we obtain a nearest envelope
|
||
90 | * of a parametrized dimension. After that, it makes a spatial query with
|
||
91 | * this envelope on the layer B. If this query doesnt return, repeat the
|
||
92 | * spatial query with the envelope that originated this envelope (we take
|
||
93 | * the parent node in the quad-tree structure).
|
||
94 | * <br>
|
||
95 | * A critical aspect is optimization of the number of levels of quad-tree.
|
||
96 | *
|
||
97 | * If we take very few levels, the spatial query will return a lot of
|
||
98 | * candidates to nearest, so we wont get advantage of this stuff.
|
||
99 | *
|
||
100 | * If we take a lot of levels, we wont get result in the spatial queries,
|
||
101 | * and we'll have to do a lot of querys.
|
||
102 | *
|
||
103 | * @author azabala
|
||
104 | *
|
||
105 | * FIXME EL ALGORITMO FALLA!!!!!!!! EL QUADTREE ES UNA ESTRUCTURA
|
||
106 | * BUENA PARA RECTANGULOS, PERO PARA PUNTOS CREO QUE NO FUNCIONA.
|
||
107 | * NO TIENE EN CUENTA LOS EXTREMOS DE LOS RECTANGULOS
|
||
108 | *
|
||
109 | */
|
||
110 | public class NearestHeuristicSpatialJoinVisitor extends NearestSpatialJoinVisitor { |
||
111 | |||
112 | private QuadTreeUtil quadTree = new QuadTreeUtil(); |
||
113 | /**
|
||
114 | * Full extent of the layer where we are looking for
|
||
115 | * features to join by spatial criteria
|
||
116 | */
|
||
117 | private Envelope targetLayerEnv = null; |
||
118 | /**
|
||
119 | *
|
||
120 | * @param sourceLayer
|
||
121 | * @param targetLayer
|
||
122 | * @param processor
|
||
123 | * @throws DriverException
|
||
124 | */
|
||
125 | public NearestHeuristicSpatialJoinVisitor(FLyrVect sourceLayer,
|
||
126 | FLyrVect targetLayer, |
||
127 | FeatureProcessor processor) throws DriverException {
|
||
128 | super(sourceLayer, targetLayer, processor);
|
||
129 | |||
130 | Rectangle2D rect = targetLayer.getFullExtent();
|
||
131 | targetLayerEnv = new Envelope(rect.getMinX(),
|
||
132 | rect.getMaxX(), |
||
133 | rect.getMinY(), |
||
134 | rect.getMaxY()); |
||
135 | |||
136 | } |
||
137 | // TODO If we need a class to look for nearest feature to a given
|
||
138 | //feature, move to a public class
|
||
139 | class LookForNearest implements FeatureVisitor{ |
||
140 | /**
|
||
141 | * Index of the nearest processed feature to the given geometry
|
||
142 | */
|
||
143 | int nearestFeatureIndex = -1; |
||
144 | /**
|
||
145 | * min distance of the features processed in the search of
|
||
146 | * nearest feature
|
||
147 | */
|
||
148 | double minDistance = Double.MAX_VALUE; |
||
149 | /**
|
||
150 | * Geometry whose nearest feature we want to locate
|
||
151 | */
|
||
152 | Geometry firstG; |
||
153 | /**
|
||
154 | * It this selectin is != null, in our search we will only
|
||
155 | * consideer features selected.
|
||
156 | */
|
||
157 | FBitSet selection; |
||
158 | |||
159 | public boolean hasFoundShortest(){ |
||
160 | return nearestFeatureIndex != -1; |
||
161 | } |
||
162 | |||
163 | public int getNearestFeatureIndex(){ |
||
164 | return nearestFeatureIndex;
|
||
165 | } |
||
166 | |||
167 | public void setSelection(FBitSet bitSet){ |
||
168 | this.selection = bitSet;
|
||
169 | } |
||
170 | |||
171 | public void setGeometry(Geometry firstG){ |
||
172 | this.firstG = firstG;
|
||
173 | } |
||
174 | |||
175 | public void visit(IGeometry g, int index) throws VisitException { |
||
176 | if(selection != null){ |
||
177 | if(! selection.get(index)){
|
||
178 | return;
|
||
179 | } |
||
180 | } |
||
181 | double dist = firstG.distance(g.toJTSGeometry());
|
||
182 | if(dist < minDistance){
|
||
183 | minDistance = dist; |
||
184 | nearestFeatureIndex = index; |
||
185 | }//if
|
||
186 | } |
||
187 | public String getProcessDescription() { |
||
188 | return ""; |
||
189 | } |
||
190 | public void stop(FLayer layer) { |
||
191 | } |
||
192 | public boolean start(FLayer layer) { |
||
193 | return true; |
||
194 | } |
||
195 | }; |
||
196 | /**
|
||
197 | * Processes a Feature of source layer, looking for its nearest feature of
|
||
198 | * target layer and taking attributes from it
|
||
199 | */
|
||
200 | public void visit(IGeometry g, int sourceIndex) throws VisitException { |
||
201 | 5628 | azabala | if(g == null) |
202 | return;
|
||
203 | 5412 | azabala | final Geometry geometry = g.toJTSGeometry();
|
204 | Stack stackOfEnvelopes = quadTree.getNearestEnvelopeOfIdealDimension(geometry,
|
||
205 | targetLayerEnv); |
||
206 | LookForNearest visitor = new LookForNearest();
|
||
207 | visitor.setGeometry(geometry); |
||
208 | while((stackOfEnvelopes.size() > 0) ) { |
||
209 | Envelope envelope = (Envelope) stackOfEnvelopes.pop(); |
||
210 | Rectangle2D.Double rect = new Rectangle2D.Double(envelope.getMinX(), |
||
211 | envelope.getMinY(), |
||
212 | envelope.getWidth(), |
||
213 | envelope.getHeight()); |
||
214 | try {
|
||
215 | if(onlySecondLayerSelection){
|
||
216 | visitor.setSelection(targetRecordset.getSelection()); |
||
217 | } |
||
218 | strategy.process(visitor, rect); |
||
219 | if(visitor.hasFoundShortest()){
|
||
220 | int targetIndex = visitor.getNearestFeatureIndex();
|
||
221 | IFeature joinedFeature = createFeature(g, |
||
222 | sourceIndex, |
||
223 | targetIndex); |
||
224 | this.featureProcessor.processFeature(joinedFeature);
|
||
225 | return;
|
||
226 | } |
||
227 | } catch (DriverException e) {
|
||
228 | throw new VisitException("Error accediendo a los datos buscando el feature mas proximo", e); |
||
229 | } catch (com.hardcode.gdbms.engine.data.driver.DriverException e) {
|
||
230 | throw new VisitException("Error accediendo a los datos buscando el feature mas proximo", e); |
||
231 | } |
||
232 | }//while
|
||
233 | |||
234 | } |
||
235 | |||
236 | /**
|
||
237 | * FIXME Refinar muy mucho, pero de momento me vale para hacer la busqueda
|
||
238 | * de la geometria mas proxima a una dada mediante subdivisi?n del espacio.
|
||
239 | *
|
||
240 | * @author azabala
|
||
241 | *
|
||
242 | */
|
||
243 | class QuadTreeUtil{ |
||
244 | double DEFAULT_IDEAL_DIMENSION = 500d; |
||
245 | |||
246 | double idealDimension = DEFAULT_IDEAL_DIMENSION;
|
||
247 | |||
248 | public void setIdealDimension(double idealDimension){ |
||
249 | this.idealDimension = idealDimension;
|
||
250 | } |
||
251 | |||
252 | public double distance(Geometry geo, Envelope rect){ |
||
253 | GeometryFactory geoFact = new GeometryFactory();
|
||
254 | Geometry poly = geoFact.toGeometry(rect); |
||
255 | return DistanceOp.distance(geo, poly);
|
||
256 | } |
||
257 | |||
258 | public double getMaxDimension(Envelope env){ |
||
259 | double w = env.getWidth();
|
||
260 | double h = env.getHeight();
|
||
261 | return (w > h ? w : h);
|
||
262 | } |
||
263 | |||
264 | |||
265 | public Stack getNearestEnvelopeOfIdealDimension(Geometry nearest, |
||
266 | Envelope originalEnvelope){ |
||
267 | //stack with all the hierarchical envelopes of the solution quad
|
||
268 | Stack solution = new Stack(); |
||
269 | Envelope firstsolution = originalEnvelope; |
||
270 | //the last try will be the full extent
|
||
271 | solution.push(firstsolution); |
||
272 | double maxDimension = getMaxDimension(originalEnvelope);
|
||
273 | while(maxDimension > idealDimension){
|
||
274 | Envelope[] quads = getNextQtreeLevel(firstsolution);
|
||
275 | double d0 = distance(nearest, quads[0]); |
||
276 | double d1 = distance(nearest, quads[1]); |
||
277 | double d2 = distance(nearest, quads[2]); |
||
278 | double d3 = distance(nearest, quads[3]); |
||
279 | if(d0 <= d1 && d0 <= d2 && d0 <= d3 )
|
||
280 | firstsolution = quads[0];
|
||
281 | else if(d1 <= d0 && d1 <= d2 && d1 <= d3) |
||
282 | firstsolution = quads[1];
|
||
283 | else if(d2 <= d0 && d2 <= d1 && d2 <= d3) |
||
284 | firstsolution = quads[2];
|
||
285 | else
|
||
286 | firstsolution = quads[3];
|
||
287 | solution.push(firstsolution); |
||
288 | maxDimension = getMaxDimension(firstsolution); |
||
289 | } |
||
290 | return solution;
|
||
291 | |||
292 | } |
||
293 | |||
294 | public Envelope[] getNextQtreeLevel(Envelope rect){ |
||
295 | Envelope[] solution = new Envelope[4]; |
||
296 | int SW = 0; |
||
297 | int SE = 1; |
||
298 | int NW = 2; |
||
299 | int NE = 3; |
||
300 | double xMin = rect.getMinX();
|
||
301 | double xMax = rect.getMaxX();
|
||
302 | double yMin = rect.getMinY();
|
||
303 | double yMax = rect.getMaxY();
|
||
304 | double xCenter = (xMin + xMax) / 2d; |
||
305 | double yCenter = (yMin + yMax) / 2d; |
||
306 | Envelope r1 = new Envelope(xMin, xCenter, yMin, yCenter);
|
||
307 | Envelope r2 = new Envelope(xCenter, xMax, yMin, yCenter);
|
||
308 | Envelope r3 = new Envelope(xMin, xCenter, yCenter, yMax);
|
||
309 | Envelope r4 = new Envelope(xCenter, xMax, yCenter, yMax);
|
||
310 | solution[SW] = r1; |
||
311 | solution[SE] = r2; |
||
312 | solution[NW] = r3; |
||
313 | solution[NE] = r4; |
||
314 | return solution;
|
||
315 | } |
||
316 | } |
||
317 | |||
318 | } |