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: * This class implements the AUTOCLUST algorithm of Estivill-Castro and Lee (2002)
017: * "Argument free clustering for large spatial point-data sets via boundary extraction
018: * from Delaunay Diagram" in Computers, Environment and Urban Systems, 26:315-334.
019: */
020: package org.geotools.graph.util.delaunay;
021:
022: import java.util.Collection;
023: import java.util.HashMap;
024: import java.util.Iterator;
025: import java.util.List;
026: import java.util.Vector;
027: import java.util.logging.Logger;
028: import java.util.logging.Level;
029: import org.geotools.graph.structure.Edge;
030: import org.geotools.graph.structure.Graph;
031: import org.geotools.graph.structure.Node;
032: import org.geotools.graph.structure.basic.BasicGraph;
033:
034: /**
035: *
036: * @author jfc173
037: */
038: public class AutoClust {
039:
040: private static final Logger LOGGER = org.geotools.util.logging.Logging
041: .getLogger("org.geotools.graph");
042:
043: /** Creates a new instance of AutoClust */
044: public AutoClust() {
045: }
046:
047: public static Graph runAutoClust(Graph d) {
048: //this is assuming d is a delaunay triangulation. If it isn't, results are unspecified.
049: //Such a diagram can be obtained through org.geotools.graph.util.delaunay.DelaunayTriangulator.
050:
051: HashMap map = new HashMap();
052: Collection nodes = d.getNodes();
053: Collection edges = d.getEdges();
054: showGraph(nodes, edges, 0);
055: Iterator nodeIt = nodes.iterator();
056: double[] localDevs = new double[nodes.size()];
057: int index = 0;
058: while (nodeIt.hasNext()) {
059: DelaunayNode next = (DelaunayNode) nodeIt.next();
060: AutoClustData acd = new AutoClustData();
061: List localEdges = AutoClustUtils.findAdjacentEdges(next,
062: edges);
063: double totalLength = 0;
064: Iterator edgeIt = localEdges.iterator();
065: while (edgeIt.hasNext()) {
066: DelaunayEdge nextEdge = (DelaunayEdge) edgeIt.next();
067: totalLength = totalLength
068: + nextEdge.getEuclideanDistance();
069: }
070: double meanLength = totalLength / localEdges.size();
071: double sumOfSquaredDiffs = 0;
072: Iterator anotherEdgeIt = localEdges.iterator();
073: while (anotherEdgeIt.hasNext()) {
074: DelaunayEdge nextEdge = (DelaunayEdge) anotherEdgeIt
075: .next();
076: sumOfSquaredDiffs = sumOfSquaredDiffs
077: + Math
078: .pow(
079: (nextEdge
080: .getEuclideanDistance() - meanLength),
081: 2);
082: }
083: double variance = sumOfSquaredDiffs / (localEdges.size());
084: double stDev = Math.sqrt(variance);
085: localDevs[index] = stDev;
086: index++;
087: acd.setLocalMean(meanLength);
088: acd.setLocalStDev(stDev);
089: map.put(next, acd);
090: }
091: double total = 0;
092: for (int i = 0; i < localDevs.length; i++) {
093: total = total + localDevs[i];
094: }
095: double meanStDev = total / localDevs.length;
096:
097: //these three are for coloring the graph in the poster, not for algorithmic purposes
098: Vector allShortEdges = new Vector();
099: Vector allLongEdges = new Vector();
100: Vector allOtherEdges = new Vector();
101:
102: Iterator anotherNodeIt = nodes.iterator();
103: while (anotherNodeIt.hasNext()) {
104: DelaunayNode next = (DelaunayNode) anotherNodeIt.next();
105: List localEdges = AutoClustUtils.findAdjacentEdges(next,
106: edges);
107: AutoClustData acd = (AutoClustData) map.get(next);
108: Iterator edgeIt = localEdges.iterator();
109: Vector shortEdges = new Vector();
110: Vector longEdges = new Vector();
111: Vector otherEdges = new Vector();
112: LOGGER.fine("local mean is " + acd.getLocalMean());
113: LOGGER.fine("mean st dev is " + meanStDev);
114: while (edgeIt.hasNext()) {
115: DelaunayEdge nextEdge = (DelaunayEdge) edgeIt.next();
116: double length = nextEdge.getEuclideanDistance();
117: if (length < acd.getLocalMean() - meanStDev) {
118: shortEdges.add(nextEdge);
119: LOGGER.finer(nextEdge + ": length "
120: + nextEdge.getEuclideanDistance()
121: + " is short");
122: } else if (length > acd.getLocalMean() + meanStDev) {
123: longEdges.add(nextEdge);
124: LOGGER.finer(nextEdge + ": length "
125: + nextEdge.getEuclideanDistance()
126: + " is long");
127: } else {
128: otherEdges.add(nextEdge);
129: LOGGER.finer(nextEdge + ": length "
130: + nextEdge.getEuclideanDistance()
131: + " is medium");
132: }
133: }
134: acd.setShortEdges(shortEdges);
135: acd.setLongEdges(longEdges);
136: acd.setOtherEdges(otherEdges);
137:
138: allLongEdges.addAll(longEdges);
139: allShortEdges.addAll(shortEdges);
140: allOtherEdges.addAll(otherEdges);
141: }
142:
143: //for the poster
144: Graph gp = new BasicGraph(nodes, edges);
145: javax.swing.JFrame frame = new javax.swing.JFrame();
146: GraphViewer viewer = new GraphViewer();
147: viewer.setLongEdges(allLongEdges);
148: viewer.setShortEdges(allShortEdges);
149: viewer.setOtherEdges(allOtherEdges);
150: viewer.setColorEdges(true);
151: viewer.setGraph(gp);
152: frame.getContentPane().add(viewer);
153: frame
154: .setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
155: frame.setSize(new java.awt.Dimension(800, 800));
156: frame.setTitle("Assigned edge categories");
157: frame.setVisible(true);
158:
159: //Phase I
160: Iterator nodeIt3 = nodes.iterator();
161: while (nodeIt3.hasNext()) {
162: DelaunayNode next = (DelaunayNode) nodeIt3.next();
163: AutoClustData acd = (AutoClustData) map.get(next);
164: List shortEdges = acd.getShortEdges();
165: List longEdges = acd.getLongEdges();
166: edges.removeAll(shortEdges);
167: LOGGER.finer("removed " + shortEdges);
168: edges.removeAll(longEdges);
169: LOGGER.finer("removed " + longEdges);
170: }
171:
172: LOGGER.fine("End of phase one and ");
173: LOGGER.fine("Nodes are " + nodes);
174: LOGGER.fine("Edges are " + edges);
175: showGraph(nodes, edges, 1);
176: Vector connectedComponents = AutoClustUtils
177: .findConnectedComponents(nodes, edges);
178:
179: //Phase II
180: Iterator nodeIt4 = nodes.iterator();
181: while (nodeIt4.hasNext()) {
182: DelaunayNode next = (DelaunayNode) nodeIt4.next();
183: AutoClustData acd = (AutoClustData) map.get(next);
184: List shortEdges = acd.getShortEdges();
185: if (!(shortEdges.isEmpty())) {
186: Vector shortlyConnectedComponents = new Vector();
187: Iterator shortIt = shortEdges.iterator();
188: while (shortIt.hasNext()) {
189: Edge nextEdge = (Edge) shortIt.next();
190: Node other = nextEdge.getOtherNode(next);
191: Graph g = getMyComponent(other, connectedComponents);
192: if (!(shortlyConnectedComponents.contains(g))) {
193: shortlyConnectedComponents.add(g);
194: }
195: }
196: Graph cv = null;
197: if (shortlyConnectedComponents.size() > 1) {
198: Iterator sccIt = shortlyConnectedComponents
199: .iterator();
200: int maxSize = 0;
201: while (sccIt.hasNext()) {
202: Graph nextGraph = (Graph) sccIt.next();
203: int size = nextGraph.getNodes().size();
204: if (size > maxSize) {
205: maxSize = size;
206: cv = nextGraph;
207: }
208: }
209: } else {
210: cv = (Graph) shortlyConnectedComponents.get(0);
211: }
212: Iterator shortIt2 = shortEdges.iterator();
213: while (shortIt2.hasNext()) {
214: Edge nextEdge = (Edge) shortIt2.next();
215: Node other = nextEdge.getOtherNode(next);
216: if (cv.equals(getMyComponent(other,
217: shortlyConnectedComponents))) {
218: edges.add(nextEdge);
219: }
220: }
221: } //end if shortEdges isn't empty
222: Graph gr = getMyComponent(next, connectedComponents);
223: if (gr.getNodes().size() == 1) {
224: Vector shortlyConnectedComponents = new Vector();
225: Iterator shortIt = shortEdges.iterator();
226: while (shortIt.hasNext()) {
227: Edge nextEdge = (Edge) shortIt.next();
228: Node other = nextEdge.getOtherNode(next);
229: Graph g = getMyComponent(other, connectedComponents);
230: if (!(shortlyConnectedComponents.contains(g))) {
231: shortlyConnectedComponents.add(g);
232: }
233: }
234: if (shortlyConnectedComponents.size() == 1) {
235: edges.addAll(shortEdges);
236: }
237: }
238: } //end nodeIt4 while loop.
239:
240: LOGGER.fine("End of phase two and ");
241: LOGGER.fine("Nodes are " + nodes);
242: LOGGER.fine("Edges are " + edges);
243: showGraph(nodes, edges, 2);
244: connectedComponents = AutoClustUtils.findConnectedComponents(
245: nodes, edges);
246:
247: //Phase III
248: Iterator nodeIt5 = nodes.iterator();
249: while (nodeIt5.hasNext()) {
250: DelaunayNode next = (DelaunayNode) nodeIt5.next();
251: Vector edgesWithinTwo = new Vector();
252: List adjacentEdges = AutoClustUtils.findAdjacentEdges(next,
253: edges); //yes, next.getEdges() could work, but there's no guarantee that next's edge list is current anymore
254: edgesWithinTwo.addAll(adjacentEdges);
255: Iterator adjacentIt = adjacentEdges.iterator();
256: while (adjacentIt.hasNext()) {
257: Edge nextEdge = (Edge) adjacentIt.next();
258: Node other = nextEdge.getOtherNode(next);
259: List adjacentToOther = AutoClustUtils
260: .findAdjacentEdges(other, edges); //yes, other.getEdges() could work, but there's no guarantee that other's edge list is current anymore
261: Iterator atoIt = adjacentToOther.iterator();
262: while (atoIt.hasNext()) {
263: Edge nextEdge2 = (Edge) atoIt.next();
264: if (!(edgesWithinTwo.contains(nextEdge2))) {
265: edgesWithinTwo.add(nextEdge2);
266: }
267: }
268: }
269: double totalLength = 0;
270: Iterator ewtIt = edgesWithinTwo.iterator();
271: while (ewtIt.hasNext()) {
272: totalLength = totalLength
273: + ((DelaunayEdge) ewtIt.next())
274: .getEuclideanDistance();
275: }
276: double local2Mean = totalLength / edgesWithinTwo.size();
277:
278: Iterator ewtIt2 = edgesWithinTwo.iterator();
279: while (ewtIt2.hasNext()) {
280: DelaunayEdge dEdge = (DelaunayEdge) ewtIt2.next();
281: if (dEdge.getEuclideanDistance() > (local2Mean + meanStDev)) {
282: edges.remove(dEdge);
283: }
284: }
285: } //end nodeIt5 loop
286:
287: LOGGER.fine("End of phase three and ");
288: LOGGER.fine("Nodes are " + nodes);
289: LOGGER.fine("Edges are " + edges);
290: showGraph(nodes, edges, 3);
291: connectedComponents = AutoClustUtils.findConnectedComponents(
292: nodes, edges);
293:
294: return new BasicGraph(nodes, edges);
295: }
296:
297: private static Graph getMyComponent(Node node, Vector components) {
298: Iterator it = components.iterator();
299: Graph ret = null;
300: boolean found = false;
301: while ((it.hasNext()) && (!(found))) {
302: Graph next = (Graph) it.next();
303: if (next.getNodes().contains(node)) {
304: found = true;
305: ret = next;
306: }
307: }
308: if (ret == null) {
309: throw new RuntimeException(
310: "Couldn't find the graph component containing node: "
311: + node);
312: }
313: return ret;
314: }
315:
316: private static void showGraph(Collection nodes, Collection edges,
317: int phase) {
318: Graph g = new BasicGraph(nodes, edges);
319: javax.swing.JFrame frame = new javax.swing.JFrame();
320: GraphViewer viewer = new GraphViewer();
321: viewer.setGraph(g);
322: frame.getContentPane().add(viewer);
323: frame
324: .setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
325: frame.setSize(new java.awt.Dimension(800, 800));
326: frame.setTitle("Phase " + phase);
327: frame.setVisible(true);
328: }
329:
330: }
|