1 /*
2 * Copyright (c) 2005, the JUNG Project and the Regents of the University of
3 * California All rights reserved.
4 *
5 * This software is open-source under the BSD license; see either "license.txt"
6 * or http://jung.sourceforge.net/license.txt for a description.
7 *
8 *
9 * Created on Apr 12, 2005
10 */
11 package edu.uci.ics.jung.algorithms.layout;
12
13 import java.awt.Shape;
14 import java.awt.geom.Point2D;
15 import java.util.Collection;
16 import java.util.ConcurrentModificationException;
17 import java.util.HashSet;
18 import java.util.Iterator;
19 import java.util.Set;
20
21 import edu.uci.ics.jung.graph.Graph;
22
23
24 /**
25 * Simple implementation of PickSupport that returns the vertex or edge
26 * that is closest to the specified location. This implementation
27 * provides the same picking options that were available in
28 * previous versions of AbstractLayout.
29 *
30 * <p>No element will be returned that is farther away than the specified
31 * maximum distance.
32 *
33 * @author Tom Nelson
34 * @author Joshua O'Madadhain
35 */
36 public class RadiusGraphElementAccessor<V, E> implements GraphElementAccessor<V, E> {
37
38 protected double maxDistance;
39
40 /**
41 * Creates an instance with an effectively infinite default maximum distance.
42 */
43 public RadiusGraphElementAccessor() {
44 this(Math.sqrt(Double.MAX_VALUE - 1000));
45 }
46
47 /**
48 * Creates an instance with the specified default maximum distance.
49 */
50 public RadiusGraphElementAccessor(double maxDistance) {
51 this.maxDistance = maxDistance;
52 }
53
54 /**
55 * Gets the vertex nearest to the location of the (x,y) location selected,
56 * within a distance of <tt>maxDistance</tt>. Iterates through all
57 * visible vertices and checks their distance from the click. Override this
58 * method to provde a more efficient implementation.
59 */
60 public V getVertex(Layout<V,E> layout, double x, double y) {
61 return getVertex(layout, x, y, this.maxDistance);
62 }
63
64 /**
65 * Gets the vertex nearest to the location of the (x,y) location selected,
66 * within a distance of <tt>maxDistance</tt>. Iterates through all
67 * visible vertices and checks their distance from the click. Override this
68 * method to provde a more efficient implementation.
69 * @param x
70 * @param y
71 * @param maxDistance temporarily overrides member maxDistance
72 */
73 public V getVertex(Layout<V,E> layout, double x, double y, double maxDistance) {
74 double minDistance = maxDistance * maxDistance;
75 V closest = null;
76 while(true) {
77 try {
78 for(V v : layout.getGraph().getVertices()) {
79
80 Point2D p = layout.transform(v);
81 double dx = p.getX() - x;
82 double dy = p.getY() - y;
83 double dist = dx * dx + dy * dy;
84 if (dist < minDistance) {
85 minDistance = dist;
86 closest = v;
87 }
88 }
89 break;
90 } catch(ConcurrentModificationException cme) {}
91 }
92 return closest;
93 }
94
95 public Collection<V> getVertices(Layout<V,E> layout, Shape rectangle) {
96 Set<V> pickedVertices = new HashSet<V>();
97 while(true) {
98 try {
99 for(V v : layout.getGraph().getVertices()) {
100
101 Point2D p = layout.transform(v);
102 if(rectangle.contains(p)) {
103 pickedVertices.add(v);
104 }
105 }
106 break;
107 } catch(ConcurrentModificationException cme) {}
108 }
109 return pickedVertices;
110 }
111
112 /**
113 * Gets the edge nearest to the location of the (x,y) location selected.
114 * Calls the longer form of the call.
115 */
116 public E getEdge(Layout<V,E> layout, double x, double y) {
117 return getEdge(layout, x, y, this.maxDistance);
118 }
119
120 /**
121 * Gets the edge nearest to the location of the (x,y) location selected,
122 * within a distance of <tt>maxDistance</tt>, Iterates through all
123 * visible edges and checks their distance from the click. Override this
124 * method to provide a more efficient implementation.
125 *
126 * @param x
127 * @param y
128 * @param maxDistance temporarily overrides member maxDistance
129 * @return Edge closest to the click.
130 */
131 public E getEdge(Layout<V,E> layout, double x, double y, double maxDistance) {
132 double minDistance = maxDistance * maxDistance;
133 E closest = null;
134 while(true) {
135 try {
136 for(E e : layout.getGraph().getEdges()) {
137
138 // Could replace all this set stuff with getFrom_internal() etc.
139 Graph<V, E> graph = layout.getGraph();
140 Collection<V> vertices = graph.getIncidentVertices(e);
141 Iterator<V> vertexIterator = vertices.iterator();
142 V v1 = vertexIterator.next();
143 V v2 = vertexIterator.next();
144 // Get coords
145 Point2D p1 = layout.transform(v1);
146 Point2D p2 = layout.transform(v2);
147 double x1 = p1.getX();
148 double y1 = p1.getY();
149 double x2 = p2.getX();
150 double y2 = p2.getY();
151 // Calculate location on line closest to (x,y)
152 // First, check that v1 and v2 are not coincident.
153 if (x1 == x2 && y1 == y2)
154 continue;
155 double b =
156 ((y - y1) * (y2 - y1) + (x - x1) * (x2 - x1))
157 / ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
158 //
159 double distance2; // square of the distance
160 if (b <= 0)
161 distance2 = (x - x1) * (x - x1) + (y - y1) * (y - y1);
162 else if (b >= 1)
163 distance2 = (x - x2) * (x - x2) + (y - y2) * (y - y2);
164 else {
165 double x3 = x1 + b * (x2 - x1);
166 double y3 = y1 + b * (y2 - y1);
167 distance2 = (x - x3) * (x - x3) + (y - y3) * (y - y3);
168 }
169
170 if (distance2 < minDistance) {
171 minDistance = distance2;
172 closest = e;
173 }
174 }
175 break;
176 } catch(ConcurrentModificationException cme) {}
177 }
178 return closest;
179 }
180 }