001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.build.polygon;
018:
019: import java.util.Iterator;
020: import java.util.List;
021:
022: import org.geotools.graph.build.GraphBuilder;
023: import org.geotools.graph.build.GraphGenerator;
024: import org.geotools.graph.structure.Edge;
025: import org.geotools.graph.structure.Graph;
026: import org.geotools.graph.structure.Graphable;
027: import org.geotools.graph.structure.Node;
028:
029: import com.vividsolutions.jts.geom.Polygon;
030: import com.vividsolutions.jts.index.quadtree.Quadtree;
031: import com.vividsolutions.jts.index.strtree.STRtree;
032:
033: /**
034: * An implementation of GraphGenerator used to build graphs from a set
035: * of polygons.
036: * <p>
037: * This graph generator takes {@link com.vividsolutions.jts.geom.Polygon}
038: * objects as input when constructing a graph. The following code constructs
039: * a graph from a set of polygons.
040: *
041: * <pre>
042: * <code>
043: * //get some polygons
044: * Polygon[] polygons = ...
045: *
046: * //determine what the relationship will be
047: * PolygonGraphGenerator rel = new PolygonGraphGenerator.PolygonRelationship() {
048: *
049: * public boolean related(Polygon p1, Polygon p2) {
050: * return p1.intersects(p2);
051: * }
052: *
053: * public boolean equal(Polygon p1, Polygon p2) {
054: * return p1.equals(p2);
055: * }
056: * }
057: * //create the generator
058: * PolygonGraphGenerator gg = new PolygonGraphGenerator(new BasicGraphBuilder(),rel);
059: *
060: * //start building
061: * for (int i = 0; i < polygons.length; i++) {
062: * gg.add(polygons[i]);
063: * }
064: * </code>
065: * </pre>
066: * </p>
067: * For each distinct polygon added to the graph, a node is created. If two
068: * polygons are considered equal, only a single node is created. If two
069: * polygons are considered related, the associated nodes share an edge. Equality
070: * and relationship is determined by {@link org.geotools.graph.build.polygon.PolygonGraphGenerator.PolygonRelationship}
071: * interface. An instance of this interface is passed to the generator at construction.
072:
073: * @author Justin Deoliveira, The Open Planning Project
074: *
075: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/build/polygon/PolygonGraphGenerator.java $
076: */
077: public class PolygonGraphGenerator implements GraphGenerator {
078:
079: /**
080: * Determines the relationship among two polygons.
081: */
082: public static interface PolygonRelationship {
083: /**
084: * Determines if two polygons are related in any way. Rel
085: * @param p1
086: * @param p2
087: */
088: boolean related(Polygon p1, Polygon p2);
089:
090: boolean equal(Polygon p1, Polygon p2);
091: }
092:
093: /** store polygon to node mapping in spatial index **/
094: Quadtree index;
095: /** relationship between polygons in graph **/
096: PolygonRelationship rel;
097: /** the node/edge builder **/
098: GraphBuilder builder;
099:
100: public PolygonGraphGenerator(GraphBuilder builder,
101: PolygonRelationship rel) {
102: setGraphBuilder(builder);
103: this .rel = rel;
104:
105: index = new Quadtree();
106: }
107:
108: public Graphable add(Object obj) {
109: Node node = (Node) get(obj);
110: if (node == null) {
111: node = builder.buildNode();
112: builder.addNode(node);
113:
114: node.setObject(obj);
115: relate(node);
116:
117: //TODO: the envelope should be buffered by some tolerance
118: index.insert(((Polygon) obj).getEnvelopeInternal(), node);
119: }
120:
121: return node;
122: }
123:
124: public Graphable get(Object obj) {
125: Polygon polygon = (Polygon) obj;
126: return find(polygon);
127: }
128:
129: public Graphable remove(Object obj) {
130: Node node = (Node) get(obj);
131: if (node != null) {
132: Polygon polygon = (Polygon) node.getObject();
133: index.remove(polygon.getEnvelopeInternal(), node);
134:
135: builder.removeNode(node);
136: }
137:
138: return node;
139: }
140:
141: public void setGraphBuilder(GraphBuilder builder) {
142: this .builder = builder;
143:
144: }
145:
146: public GraphBuilder getGraphBuilder() {
147: return builder;
148: }
149:
150: public Graph getGraph() {
151: return builder.getGraph();
152: }
153:
154: protected Node find(Polygon polygon) {
155: List close = index.query(polygon.getEnvelopeInternal());
156: for (Iterator itr = close.iterator(); itr.hasNext();) {
157: Node node = (Node) itr.next();
158: Polygon p = (Polygon) node.getObject();
159:
160: if (rel.equal(polygon, p)) {
161: return node;
162: }
163: }
164:
165: return null;
166: }
167:
168: protected void relate(Node node) {
169: Polygon polygon = (Polygon) node.getObject();
170: List close = index.query(polygon.getEnvelopeInternal());
171:
172: for (Iterator itr = close.iterator(); itr.hasNext();) {
173: Node n = (Node) itr.next();
174: Polygon p = (Polygon) n.getObject();
175:
176: if (!rel.equal(polygon, p) && rel.related(polygon, p)) {
177: Edge edge = builder.buildEdge(node, n);
178: builder.addEdge(edge);
179: builder.addEdge(edge);
180: }
181: }
182: }
183:
184: }
|