svn-gvsig-desktop / trunk / org.gvsig.desktop / org.gvsig.desktop.compat.cdc / org.gvsig.fmap.geometry / org.gvsig.fmap.geometry.jts / src / main / java / org / gvsig / fmap / geom / jts / primitive / surface / split / SplitGraph.java @ 47755
History | View | Annotate | Download (10.8 KB)
1 |
/**
|
---|---|
2 |
* gvSIG. Desktop Geographic Information System.
|
3 |
*
|
4 |
* Copyright (C) 2007-2013 gvSIG Association.
|
5 |
*
|
6 |
* This program is free software; you can redistribute it and/or
|
7 |
* modify it under the terms of the GNU General Public License
|
8 |
* as published by the Free Software Foundation; either version 3
|
9 |
* of the License, or (at your option) any later version.
|
10 |
*
|
11 |
* This program is distributed in the hope that it will be useful,
|
12 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
13 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
14 |
* GNU General Public License for more details.
|
15 |
*
|
16 |
* You should have received a copy of the GNU General Public License
|
17 |
* along with this program; if not, write to the Free Software
|
18 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
|
19 |
* MA 02110-1301, USA.
|
20 |
*
|
21 |
* For any additional information, do not hesitate to contact us
|
22 |
* at info AT gvsig.com, or visit our website www.gvsig.com.
|
23 |
*/
|
24 |
/* Spatial Operations & Editing Tools for uDig
|
25 |
*
|
26 |
* Axios Engineering under a funding contract with:
|
27 |
* Diputación Foral de Gipuzkoa, Ordenación Territorial
|
28 |
*
|
29 |
* http://b5m.gipuzkoa.net
|
30 |
* http://www.axios.es
|
31 |
*
|
32 |
* (C) 2006, Diputación Foral de Gipuzkoa, Ordenación Territorial (DFG-OT).
|
33 |
* DFG-OT agrees to licence under Lesser General Public License (LGPL).
|
34 |
*
|
35 |
* You can redistribute it and/or modify it under the terms of the
|
36 |
* GNU Lesser General Public License as published by the Free Software
|
37 |
* Foundation; version 2.1 of the License.
|
38 |
*
|
39 |
* This library is distributed in the hope that it will be useful,
|
40 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
41 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
42 |
* Lesser General Public License for more details.
|
43 |
*/
|
44 |
package org.gvsig.fmap.geom.jts.primitive.surface.split; |
45 |
|
46 |
import com.vividsolutions.jts.geom.Coordinate; |
47 |
import com.vividsolutions.jts.geom.CoordinateArrays; |
48 |
import com.vividsolutions.jts.geom.Geometry; |
49 |
import com.vividsolutions.jts.geom.GeometryFactory; |
50 |
import com.vividsolutions.jts.geom.LineString; |
51 |
import com.vividsolutions.jts.geom.Location; |
52 |
import com.vividsolutions.jts.geom.Point; |
53 |
import com.vividsolutions.jts.geom.Polygon; |
54 |
import com.vividsolutions.jts.geomgraph.DirectedEdge; |
55 |
import com.vividsolutions.jts.geomgraph.Edge; |
56 |
import com.vividsolutions.jts.geomgraph.Label; |
57 |
import com.vividsolutions.jts.geomgraph.NodeFactory; |
58 |
import com.vividsolutions.jts.geomgraph.PlanarGraph; |
59 |
import com.vividsolutions.jts.geomgraph.Position; |
60 |
import com.vividsolutions.jts.geomgraph.Quadrant; |
61 |
import java.util.ArrayList; |
62 |
import java.util.List; |
63 |
import org.slf4j.LoggerFactory; |
64 |
|
65 |
/**
|
66 |
* A {@link PlanarGraph} that builds itself from a {@link Polygon} and a
|
67 |
* {@link LineString splitting line}.
|
68 |
* <p>
|
69 |
* The resulting graph will have the following characteristics:
|
70 |
* <ul>
|
71 |
* <li>It will contain as many edges as linestrings in the boundary of the
|
72 |
* intersection geometry between the polygon and the splitting line string.
|
73 |
* <li>All edges will be labelled {@link Location#BOUNDARY} at
|
74 |
* {@link Position#ON}</li>
|
75 |
* <li>The edges from the polygon's exterior ring will be labelled
|
76 |
* {@link Location#EXTERIOR} at the
|
77 |
* {@link Position#LEFT}, {@link Location#INTERIOR} at
|
78 |
* {@link Position#RIGHT}</li>
|
79 |
* <li>The edges from the polygon's holes will be labelled
|
80 |
* {@link Location#INTERIOR} at the
|
81 |
* {@link Position#LEFT}, {@link Location#EXTERIOR} at
|
82 |
* {@link Position#RIGHT}</li>
|
83 |
* </ul>
|
84 |
* <p>
|
85 |
* Note the provided polygon may result modified as the result of
|
86 |
* {@link Polygon#normalize()}, which is called in order to ensure propper
|
87 |
* orientation of the shell and holes.
|
88 |
* </p>
|
89 |
* </p>
|
90 |
*
|
91 |
* @author Gabriel Roldán, Axios Engineering
|
92 |
* @author Mauricio Pazos, Axios Engineering
|
93 |
* @since 1.1.0
|
94 |
*/
|
95 |
class SplitGraph extends PlanarGraph { |
96 |
|
97 |
private static final NodeFactory NODE_FACTORY = new SplitGraphNodeFactory(); |
98 |
|
99 |
private final Polygon polygon; |
100 |
|
101 |
private final LineString splitter; |
102 |
|
103 |
public SplitGraph(Polygon polygon, LineString splitter) { |
104 |
super(NODE_FACTORY);
|
105 |
this.polygon = polygon;
|
106 |
// after normalize() we know the shell is oriented CW and the holes CCW
|
107 |
this.polygon.normalize();
|
108 |
|
109 |
this.splitter = normalizeSplitter(splitter);
|
110 |
buildGraph(); |
111 |
} |
112 |
|
113 |
private LineString normalizeSplitter(final LineString original) { |
114 |
// ensure the splitter has no endpoints lying inside the polygon
|
115 |
LineString normalizedSplitter = removeInteriorEndPoints(polygon, original); |
116 |
// endure the splitter is directed clockwise, as its going
|
117 |
// to become part of the shell boundary when the tesselation
|
118 |
// process eliminates other shell edges from the graph
|
119 |
Coordinate[] splitterCoords = normalizedSplitter.getCoordinates();
|
120 |
Coordinate coord0 = splitterCoords[0];
|
121 |
Coordinate coord1 = splitterCoords[1];
|
122 |
|
123 |
// determine the orientation of the coordinate sequence given the
|
124 |
// quadrant of its first vector
|
125 |
// 1 | 0
|
126 |
// --+--
|
127 |
// 2 | 3
|
128 |
final int quadrant = Quadrant.quadrant(coord0, coord1); |
129 |
boolean isCounterClockWise = 1 == quadrant || 2 == quadrant; |
130 |
if (isCounterClockWise) {
|
131 |
CoordinateArrays.reverse(splitterCoords); |
132 |
GeometryFactory gf = original.getFactory(); |
133 |
normalizedSplitter = gf.createLineString(splitterCoords); |
134 |
} |
135 |
return normalizedSplitter;
|
136 |
} |
137 |
|
138 |
/**
|
139 |
* Removes the given edge and its related {@link DirectedEdge}'s from this
|
140 |
* graph
|
141 |
*
|
142 |
* @param edge the edge to remove
|
143 |
* @throws IllegalArgumentException if no enclosing DirectedEdge is found
|
144 |
* for <code>edge</code>
|
145 |
* @see #remove(DirectedEdge)
|
146 |
*/
|
147 |
public void remove(final SplitEdge edge) { |
148 |
DirectedEdge edgeEnd = (DirectedEdge) findEdgeEnd(edge); |
149 |
if (edgeEnd == null) { |
150 |
throw new IllegalArgumentException("No enclosing edge end found for " + edge); |
151 |
} |
152 |
remove(edgeEnd); |
153 |
} |
154 |
|
155 |
/**
|
156 |
* Removes a DirectedEdge, its sym and its {@link SplitEdge} from this
|
157 |
* graph. May lead to the graph containing dangling nodes.
|
158 |
*
|
159 |
* @param edgeEnd
|
160 |
*/
|
161 |
public void remove(final DirectedEdge edgeEnd) { |
162 |
if (edgeEnd == null) { |
163 |
throw new NullPointerException(); |
164 |
} |
165 |
if (edgeEndList.remove(edgeEnd)) {
|
166 |
DirectedEdge sym = edgeEnd.getSym(); |
167 |
edgeEndList.remove(sym); |
168 |
|
169 |
// shared edge between both ends
|
170 |
Edge edge = edgeEnd.getEdge(); |
171 |
edges.remove(edge); |
172 |
|
173 |
// node of directed edge end
|
174 |
SplitGraphNode node = (SplitGraphNode) edgeEnd.getNode(); |
175 |
// node of symetric directed edge end
|
176 |
SplitGraphNode endNode = (SplitGraphNode) sym.getNode(); |
177 |
node.remove(edgeEnd); |
178 |
endNode.remove(sym); |
179 |
} |
180 |
} |
181 |
|
182 |
/**
|
183 |
* Builds a linestrnig from splitter such that it contains no endpoints
|
184 |
* lying inside the polygon
|
185 |
*
|
186 |
* @param polygon
|
187 |
* @param splitter
|
188 |
* @return
|
189 |
*/
|
190 |
private LineString removeInteriorEndPoints(Polygon polygon, LineString splitter) { |
191 |
final Coordinate[] coords = splitter.getCoordinates(); |
192 |
final GeometryFactory gf = splitter.getFactory();
|
193 |
int useFrom;
|
194 |
int useTo;
|
195 |
|
196 |
for (useFrom = 0; useFrom < coords.length; useFrom++) { |
197 |
Point p = gf.createPoint(coords[useFrom]);
|
198 |
if (!polygon.contains(p)) {
|
199 |
break;
|
200 |
} |
201 |
} |
202 |
for (useTo = coords.length - 1; useTo >= useFrom; useTo--) { |
203 |
Point p = gf.createPoint(coords[useTo]);
|
204 |
if (!polygon.contains(p)) {
|
205 |
break;
|
206 |
} |
207 |
} |
208 |
|
209 |
if (useFrom == useTo) {
|
210 |
throw new IllegalArgumentException("Line lies completely inside polygon"); |
211 |
} |
212 |
|
213 |
int length = 1 + (useTo - useFrom); |
214 |
Coordinate[] crossingLineCoords = new Coordinate[length]; |
215 |
System.arraycopy(coords, useFrom, crossingLineCoords, 0, length); |
216 |
LineString surelyCrossingLine = gf.createLineString(crossingLineCoords); |
217 |
return surelyCrossingLine;
|
218 |
} |
219 |
|
220 |
/**
|
221 |
* <pre>
|
222 |
* <code>
|
223 |
*
|
224 |
* +----------o-----------+
|
225 |
* | | |
|
226 |
* | | |
|
227 |
* | +-----------+ |
|
228 |
* | | | | |
|
229 |
* | | | | |
|
230 |
* | | | | |
|
231 |
* | o__\__o_____| |
|
232 |
* | / | |
|
233 |
* /|\ /|\ |
|
234 |
* o__________o___________|
|
235 |
*
|
236 |
*
|
237 |
* </code>
|
238 |
* </pre>
|
239 |
*
|
240 |
* @throws Exception
|
241 |
*/
|
242 |
private void buildGraph() { |
243 |
Geometry intersectingLineStrings = polygon.intersection(splitter); |
244 |
Geometry nodedShell = polygon.getExteriorRing().difference(splitter); |
245 |
|
246 |
LineString[] interiorRings = new LineString[polygon.getNumInteriorRing()]; |
247 |
for (int i = 0; i < polygon.getNumInteriorRing(); i++) { |
248 |
LineString interiorRingN = polygon.getInteriorRingN(i); |
249 |
interiorRings[i] = interiorRingN; |
250 |
} |
251 |
GeometryFactory factory = polygon.getFactory(); |
252 |
Geometry interiorRingCollection = factory.createMultiLineString(interiorRings); |
253 |
Geometry nodedHoles = interiorRingCollection.difference(splitter); |
254 |
|
255 |
// shell segments oriented CW means exterior at the left, interior at
|
256 |
// the right
|
257 |
addEdges(nodedShell, Location.BOUNDARY, Location.EXTERIOR, Location.INTERIOR); |
258 |
// hole segments oriented CCW means interior at the left, exterior at
|
259 |
// the right
|
260 |
addEdges(nodedHoles, Location.BOUNDARY, Location.INTERIOR, Location.EXTERIOR); |
261 |
// splitter intersection segments have interior location at both left
|
262 |
// and right
|
263 |
addEdges(intersectingLineStrings, Location.BOUNDARY, Location.INTERIOR, Location.INTERIOR); |
264 |
} |
265 |
|
266 |
private void addEdges(Geometry linearGeom, int onLoc, int leftLoc, int rightLoc) { |
267 |
final int nParts = linearGeom.getNumGeometries(); |
268 |
Geometry currGeom; |
269 |
Coordinate[] coords;
|
270 |
List edgesToAdd = new ArrayList(); |
271 |
for (int i = 0; i < nParts; i++) { |
272 |
currGeom = linearGeom.getGeometryN(i); |
273 |
coords = currGeom.getCoordinates(); |
274 |
if (coords.length < 2) { |
275 |
continue;
|
276 |
} |
277 |
Label label = new Label(onLoc, leftLoc, rightLoc); |
278 |
Edge edge = new SplitEdge(coords, label);
|
279 |
edgesToAdd.add(edge); |
280 |
} |
281 |
// for each edge in the list, adds two DirectedEdge, one reflecting
|
282 |
// the given edge and other the opposite
|
283 |
try {
|
284 |
super.addEdges(edgesToAdd);
|
285 |
} catch (Exception e) { |
286 |
LoggerFactory.getLogger(this.getClass()).error(e.getLocalizedMessage(), e);
|
287 |
} |
288 |
} |
289 |
|
290 |
} |