001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2006, GeoTools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation;
009: * version 2.1 of the License.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.graph.util.delaunay;
017:
018: import com.vividsolutions.jts.geom.Coordinate;
019: import com.vividsolutions.jts.geom.Geometry;
020: import com.vividsolutions.jts.geom.Point;
021: import java.util.Collection;
022: import java.util.Iterator;
023: import java.util.Vector;
024: import java.util.logging.Logger;
025: import org.geotools.feature.Feature;
026: import org.geotools.feature.FeatureCollection;
027: import org.geotools.feature.FeatureIterator;
028: import org.geotools.graph.structure.Edge;
029: import org.geotools.graph.structure.Graph;
030: import org.geotools.graph.structure.Node;
031: import org.geotools.graph.structure.basic.BasicGraph;
032:
033: /**
034: *
035: * @author jfc173
036: */
037: public class AutoClustUtils {
038:
039: private static final Logger LOGGER = org.geotools.util.logging.Logging
040: .getLogger("org.geotools.graph");
041:
042: /** Creates a new instance of AutoClustUtils */
043: public AutoClustUtils() {
044: }
045:
046: public static Vector findConnectedComponents(
047: final Collection nodes, final Collection edges) {
048: Vector components = new Vector();
049: Vector nodesVisited = new Vector();
050:
051: Iterator nodesIt = nodes.iterator();
052: while (nodesIt.hasNext()) {
053: Node next = (Node) nodesIt.next();
054: if (!(nodesVisited.contains(next))) {
055: Vector componentNodes = new Vector();
056: Vector componentEdges = new Vector();
057: expandComponent(next, edges, componentNodes,
058: componentEdges);
059: nodesVisited.addAll(componentNodes);
060: Graph component = new BasicGraph(componentNodes,
061: componentEdges);
062: components.add(component);
063: }
064: }
065:
066: return components;
067: }
068:
069: private static void expandComponent(final Node node,
070: final Collection edges, final Collection componentNodes,
071: final Collection componentEdges) {
072: if (componentNodes.contains(node)) {
073: //base case. I've already expanded on node, so no need to repeat the process.
074: // LOGGER.fine("I've already expanded from " + node);
075: } else {
076: componentNodes.add(node);
077: // LOGGER.finer("Adding " + node + " to component");
078: Vector adjacentEdges = findAdjacentEdges(node, edges); //yes, I know node.getEdges() should do this, but this method could be out of data by the time I use this in AutoClust
079: adjacentEdges.trimToSize();
080: componentEdges.addAll(adjacentEdges);
081: // LOGGER.finer("Adding " + adjacentEdges + " to component");
082:
083: Iterator aeIt = adjacentEdges.iterator();
084: while (aeIt.hasNext()) {
085: Edge next = (Edge) aeIt.next();
086: // LOGGER.finer("looking at edge " + next);
087: Node additionalNode = next.getOtherNode(node);
088: // LOGGER.finer("its other node is " + additionalNode);
089: if (additionalNode == null) {
090: throw new RuntimeException(
091: "I tried to get the other node of this edge "
092: + next + " but it doesn't have "
093: + node);
094: }
095: expandComponent(additionalNode, edges, componentNodes,
096: componentEdges);
097: }
098: adjacentEdges.clear();
099: }
100: }
101:
102: public static Vector findAdjacentEdges(final Node node,
103: final Collection edges) {
104: Vector ret = new Vector();
105: Iterator it = edges.iterator();
106: while (it.hasNext()) {
107: Edge next = (Edge) it.next();
108: if ((next.getNodeA().equals(node))
109: || (next.getNodeB().equals(node))) {
110: ret.add(next);
111: }
112: }
113: return ret;
114: }
115:
116: public static DelaunayNode[] featureCollectionToNodeArray(
117: FeatureCollection fc) {
118: FeatureIterator iter = fc.features();
119: int size = fc.size();
120: DelaunayNode[] nodes = new DelaunayNode[size];
121: int index = 0;
122: while (iter.hasNext()) {
123: Feature next = iter.next();
124: Geometry geom = next.getDefaultGeometry();
125: Point centroid;
126: if (geom instanceof Point) {
127: centroid = (Point) geom;
128: } else {
129: centroid = geom.getCentroid();
130: }
131: DelaunayNode node = new DelaunayNode();
132: node.setCoordinate(centroid.getCoordinate());
133: node.setFeature(next);
134: if (!(arrayContains(node, nodes, index))) {
135: nodes[index] = node;
136: index++;
137: }
138: }
139:
140: DelaunayNode[] trimmed = new DelaunayNode[index];
141: for (int i = 0; i < index; i++) {
142: trimmed[i] = nodes[i];
143: }
144: return trimmed;
145: }
146:
147: public static boolean arrayContains(DelaunayNode node,
148: DelaunayNode[] nodes, int index) {
149: boolean ret = false;
150: boolean done = false;
151: int i = 0;
152: while (!(done)) {
153: if (i < index) {
154: done = ret = (nodes[i].equals(node));
155: i++;
156: } else {
157: done = true;
158: }
159: }
160: return ret;
161: }
162:
163: }
|