svn-gvsig-desktop / tags / J2ME_compat_v1_2_Build_1209 / libraries / libFMap / src / com / vividsolutions / jts / operation / overlay / SnapPolygonBuilder.java @ 19509
History | View | Annotate | Download (11.1 KB)
1 | 19509 | jcarrasco | /*
|
---|---|---|---|
2 | * Created on 09-oct-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: SnapPolygonBuilder.java 10627 2007-03-06 17:10:21Z caballero $
|
||
47 | * $Log$
|
||
48 | * Revision 1.2 2007-03-06 17:08:59 caballero
|
||
49 | * Exceptions
|
||
50 | *
|
||
51 | * Revision 1.1 2006/12/04 19:30:23 azabala
|
||
52 | * *** empty log message ***
|
||
53 | *
|
||
54 | * Revision 1.2 2006/10/17 18:25:53 azabala
|
||
55 | * *** empty log message ***
|
||
56 | *
|
||
57 | * Revision 1.1 2006/10/09 19:10:56 azabala
|
||
58 | * First version in CVS
|
||
59 | *
|
||
60 | *
|
||
61 | */
|
||
62 | package com.vividsolutions.jts.operation.overlay; |
||
63 | |||
64 | import java.util.ArrayList; |
||
65 | import java.util.Collection; |
||
66 | import java.util.Iterator; |
||
67 | import java.util.List; |
||
68 | |||
69 | import com.vividsolutions.jts.algorithm.CGAlgorithms; |
||
70 | import com.vividsolutions.jts.geom.Coordinate; |
||
71 | import com.vividsolutions.jts.geom.Envelope; |
||
72 | import com.vividsolutions.jts.geom.GeometryFactory; |
||
73 | import com.vividsolutions.jts.geom.LinearRing; |
||
74 | import com.vividsolutions.jts.geom.Polygon; |
||
75 | import com.vividsolutions.jts.geomgraph.DirectedEdge; |
||
76 | import com.vividsolutions.jts.geomgraph.EdgeRing; |
||
77 | import com.vividsolutions.jts.geomgraph.SnappingPlanarGraph; |
||
78 | //import com.vividsolutions.jts.util.//assert;
|
||
79 | |||
80 | public class SnapPolygonBuilder extends PolygonBuilder { |
||
81 | |||
82 | private GeometryFactory geometryFactory;
|
||
83 | private CGAlgorithms cga;
|
||
84 | //private List dirEdgeList;
|
||
85 | //private NodeMap nodes;
|
||
86 | private List shellList = new ArrayList(); |
||
87 | |||
88 | public SnapPolygonBuilder(GeometryFactory geometryFactory,
|
||
89 | CGAlgorithms cga) |
||
90 | { |
||
91 | super(geometryFactory, cga);
|
||
92 | this.geometryFactory = geometryFactory;
|
||
93 | this.cga = cga;
|
||
94 | } |
||
95 | |||
96 | /**
|
||
97 | * Add a complete graph.
|
||
98 | * The graph is assumed to contain one or more polygons,
|
||
99 | * possibly with holes.
|
||
100 | */
|
||
101 | public void add(SnappingPlanarGraph graph) |
||
102 | { |
||
103 | add(graph.getEdgeEnds(), graph.getNodes()); |
||
104 | } |
||
105 | |||
106 | /**
|
||
107 | * Add a set of edges and nodes, which form a graph.
|
||
108 | * The graph is assumed to contain one or more polygons,
|
||
109 | * possibly with holes.
|
||
110 | */
|
||
111 | public void add(Collection dirEdges, Collection nodes) |
||
112 | { |
||
113 | SnappingPlanarGraph.linkResultDirectedEdges(nodes); |
||
114 | List maxEdgeRings = buildMaximalEdgeRings(dirEdges);
|
||
115 | List freeHoleList = new ArrayList(); |
||
116 | List edgeRings = buildMinimalEdgeRings(maxEdgeRings, shellList, freeHoleList);
|
||
117 | sortShellsAndHoles(edgeRings, shellList, freeHoleList); |
||
118 | placeFreeHoles(shellList, freeHoleList); |
||
119 | } |
||
120 | |||
121 | public List getPolygons() |
||
122 | { |
||
123 | List resultPolyList = computePolygons(shellList);
|
||
124 | return resultPolyList;
|
||
125 | } |
||
126 | |||
127 | |||
128 | /**
|
||
129 | * for all DirectedEdges in result, form them into MaximalEdgeRings
|
||
130 | */
|
||
131 | private List buildMaximalEdgeRings(Collection dirEdges) |
||
132 | { |
||
133 | List maxEdgeRings = new ArrayList(); |
||
134 | for (Iterator it = dirEdges.iterator(); it.hasNext(); ) { |
||
135 | DirectedEdge de = (DirectedEdge) it.next(); |
||
136 | if (de.isInResult() && de.getLabel().isArea() ) {
|
||
137 | // if this edge has not yet been processed
|
||
138 | if (de.getEdgeRing() == null) { |
||
139 | MaximalEdgeRing er = new MaximalEdgeRing(de, geometryFactory, cga);
|
||
140 | maxEdgeRings.add(er); |
||
141 | er.setInResult(); |
||
142 | // System.out.println("max node degree = " + er.getMaxDegree());
|
||
143 | } |
||
144 | } |
||
145 | } |
||
146 | return maxEdgeRings;
|
||
147 | } |
||
148 | |||
149 | private List buildMinimalEdgeRings(List maxEdgeRings, List shellList, List freeHoleList) |
||
150 | { |
||
151 | List edgeRings = new ArrayList(); |
||
152 | for (Iterator it = maxEdgeRings.iterator(); it.hasNext(); ) { |
||
153 | MaximalEdgeRing er = (MaximalEdgeRing) it.next(); |
||
154 | if (er.getMaxNodeDegree() > 2) { |
||
155 | er.linkDirectedEdgesForMinimalEdgeRings(); |
||
156 | List minEdgeRings = er.buildMinimalRings();
|
||
157 | // at this point we can go ahead and attempt to place holes, if this EdgeRing is a polygon
|
||
158 | EdgeRing shell = findShell(minEdgeRings); |
||
159 | if (shell != null) { |
||
160 | placePolygonHoles(shell, minEdgeRings); |
||
161 | shellList.add(shell); |
||
162 | } |
||
163 | else {
|
||
164 | freeHoleList.addAll(minEdgeRings); |
||
165 | } |
||
166 | } |
||
167 | else {
|
||
168 | edgeRings.add(er); |
||
169 | } |
||
170 | } |
||
171 | return edgeRings;
|
||
172 | } |
||
173 | |||
174 | /**
|
||
175 | * This method takes a list of MinimalEdgeRings derived from a MaximalEdgeRing,
|
||
176 | * and tests whether they form a Polygon. This is the case if there is a single shell
|
||
177 | * in the list. In this case the shell is returned.
|
||
178 | * The other possibility is that they are a series of connected holes, in which case
|
||
179 | * no shell is returned.
|
||
180 | *
|
||
181 | * @return the shell EdgeRing, if there is one
|
||
182 | * @return null, if all the rings are holes
|
||
183 | */
|
||
184 | private EdgeRing findShell(List minEdgeRings) |
||
185 | { |
||
186 | int shellCount = 0; |
||
187 | EdgeRing shell = null;
|
||
188 | for (Iterator it = minEdgeRings.iterator(); it.hasNext(); ) { |
||
189 | EdgeRing er = (MinimalEdgeRing) it.next(); |
||
190 | if (! er.isHole()) {
|
||
191 | shell = er; |
||
192 | shellCount++; |
||
193 | } |
||
194 | } |
||
195 | //assert.isTrue(shellCount <= 1, "found two shells in MinimalEdgeRing list");
|
||
196 | return shell;
|
||
197 | } |
||
198 | /**
|
||
199 | * This method assigns the holes for a Polygon (formed from a list of
|
||
200 | * MinimalEdgeRings) to its shell.
|
||
201 | * Determining the holes for a MinimalEdgeRing polygon serves two purposes:
|
||
202 | * <ul>
|
||
203 | * <li>it is faster than using a point-in-polygon check later on.
|
||
204 | * <li>it ensures correctness, since if the PIP test was used the point
|
||
205 | * chosen might lie on the shell, which might return an incorrect result from the
|
||
206 | * PIP test
|
||
207 | * </ul>
|
||
208 | */
|
||
209 | private void placePolygonHoles(EdgeRing shell, List minEdgeRings) |
||
210 | { |
||
211 | for (Iterator it = minEdgeRings.iterator(); it.hasNext(); ) { |
||
212 | MinimalEdgeRing er = (MinimalEdgeRing) it.next(); |
||
213 | if (er.isHole()) {
|
||
214 | er.setShell(shell); |
||
215 | } |
||
216 | } |
||
217 | } |
||
218 | /**
|
||
219 | * For all rings in the input list,
|
||
220 | * determine whether the ring is a shell or a hole
|
||
221 | * and add it to the appropriate list.
|
||
222 | * Due to the way the DirectedEdges were linked,
|
||
223 | * a ring is a shell if it is oriented CW, a hole otherwise.
|
||
224 | */
|
||
225 | private void sortShellsAndHoles(List edgeRings, List shellList, List freeHoleList) |
||
226 | { |
||
227 | for (Iterator it = edgeRings.iterator(); it.hasNext(); ) { |
||
228 | EdgeRing er = (EdgeRing) it.next(); |
||
229 | // er.setInResult();
|
||
230 | if (er.isHole() ) {
|
||
231 | freeHoleList.add(er); |
||
232 | } |
||
233 | else {
|
||
234 | shellList.add(er); |
||
235 | } |
||
236 | } |
||
237 | } |
||
238 | /**
|
||
239 | * This method determines finds a containing shell for all holes
|
||
240 | * which have not yet been assigned to a shell.
|
||
241 | * These "free" holes should
|
||
242 | * all be <b>properly</b> contained in their parent shells, so it is safe to use the
|
||
243 | * <code>findEdgeRingContaining</code> method.
|
||
244 | * (This is the case because any holes which are NOT
|
||
245 | * properly contained (i.e. are connected to their
|
||
246 | * parent shell) would have formed part of a MaximalEdgeRing
|
||
247 | * and been handled in a previous step).
|
||
248 | */
|
||
249 | private void placeFreeHoles(List shellList, List freeHoleList) |
||
250 | { |
||
251 | for (Iterator it = freeHoleList.iterator(); it.hasNext(); ) { |
||
252 | EdgeRing hole = (EdgeRing) it.next(); |
||
253 | // only place this hole if it doesn't yet have a shell
|
||
254 | if (hole.getShell() == null) { |
||
255 | EdgeRing shell = findEdgeRingContaining(hole, shellList); |
||
256 | //assert.isTrue(shell != null, "unable to assign hole to a shell");
|
||
257 | hole.setShell(shell); |
||
258 | } |
||
259 | } |
||
260 | } |
||
261 | /**
|
||
262 | * Find the innermost enclosing shell EdgeRing containing the argument EdgeRing, if any.
|
||
263 | * The innermost enclosing ring is the <i>smallest</i> enclosing ring.
|
||
264 | * The algorithm used depends on the fact that:
|
||
265 | * <br>
|
||
266 | * ring A contains ring B iff envelope(ring A) contains envelope(ring B)
|
||
267 | * <br>
|
||
268 | * This routine is only safe to use if the chosen point of the hole
|
||
269 | * is known to be properly contained in a shell
|
||
270 | * (which is guaranteed to be the case if the hole does not touch its shell)
|
||
271 | *
|
||
272 | * @return containing EdgeRing, if there is one
|
||
273 | * @return null if no containing EdgeRing is found
|
||
274 | */
|
||
275 | |||
276 | |||
277 | //TODO Estudiar como meter el snapping
|
||
278 | private EdgeRing findEdgeRingContaining(EdgeRing testEr, List shellList) |
||
279 | { |
||
280 | LinearRing testRing = testEr.getLinearRing(); |
||
281 | Envelope testEnv = testRing.getEnvelopeInternal(); |
||
282 | Coordinate testPt = testRing.getCoordinateN(0);
|
||
283 | |||
284 | EdgeRing minShell = null;
|
||
285 | Envelope minEnv = null;
|
||
286 | for (Iterator it = shellList.iterator(); it.hasNext(); ) { |
||
287 | EdgeRing tryShell = (EdgeRing) it.next(); |
||
288 | LinearRing tryRing = tryShell.getLinearRing(); |
||
289 | Envelope tryEnv = tryRing.getEnvelopeInternal(); |
||
290 | if (minShell != null) minEnv = minShell.getLinearRing().getEnvelopeInternal(); |
||
291 | boolean isContained = false; |
||
292 | if (tryEnv.contains(testEnv)
|
||
293 | && CGAlgorithms.isPointInRing(testPt, tryRing.getCoordinates()) ) |
||
294 | isContained = true;
|
||
295 | // check if this new containing ring is smaller than the current minimum ring
|
||
296 | if (isContained) {
|
||
297 | if (minShell == null |
||
298 | || minEnv.contains(tryEnv)) { |
||
299 | minShell = tryShell; |
||
300 | } |
||
301 | } |
||
302 | } |
||
303 | return minShell;
|
||
304 | } |
||
305 | private List computePolygons(List shellList) |
||
306 | { |
||
307 | List resultPolyList = new ArrayList(); |
||
308 | // add Polygons for all shells
|
||
309 | for (Iterator it = shellList.iterator(); it.hasNext(); ) { |
||
310 | EdgeRing er = (EdgeRing) it.next(); |
||
311 | Polygon poly = er.toPolygon(geometryFactory);
|
||
312 | resultPolyList.add(poly); |
||
313 | } |
||
314 | return resultPolyList;
|
||
315 | } |
||
316 | |||
317 | /**
|
||
318 | * Checks the current set of shells (with their associated holes) to
|
||
319 | * see if any of them contain the point.
|
||
320 | */
|
||
321 | |||
322 | //TODO METER SNAPPING
|
||
323 | public boolean containsPoint(Coordinate p) |
||
324 | { |
||
325 | for (Iterator it = shellList.iterator(); it.hasNext(); ) { |
||
326 | EdgeRing er = (EdgeRing) it.next(); |
||
327 | if (er.containsPoint(p))
|
||
328 | return true; |
||
329 | } |
||
330 | return false; |
||
331 | } |
||
332 | |||
333 | |||
334 | |||
335 | } |