1 /*
2 * Copyright (c) 2005, the JUNG Project and the Regents of the University
3 * of California
4 * All rights reserved.
5 *
6 * This software is open-source under the BSD license; see either
7 * "license.txt" or
8 * http://jung.sourceforge.net/license.txt for a description.
9 * Created on Mar 11, 2005
10 *
11 */
12 package edu.uci.ics.jung.visualization.picking;
13
14 import java.awt.Shape;
15 import java.awt.geom.AffineTransform;
16 import java.awt.geom.GeneralPath;
17 import java.awt.geom.PathIterator;
18 import java.awt.geom.Point2D;
19 import java.awt.geom.Rectangle2D;
20 import java.util.Collection;
21 import java.util.ConcurrentModificationException;
22 import java.util.HashSet;
23 import java.util.LinkedHashSet;
24 import java.util.Set;
25
26 import org.apache.commons.collections15.Predicate;
27 import org.apache.commons.collections15.functors.TruePredicate;
28
29 import edu.uci.ics.jung.algorithms.layout.GraphElementAccessor;
30 import edu.uci.ics.jung.algorithms.layout.Layout;
31 import edu.uci.ics.jung.graph.Graph;
32 import edu.uci.ics.jung.graph.util.Context;
33 import edu.uci.ics.jung.graph.util.Pair;
34 import edu.uci.ics.jung.visualization.Layer;
35 import edu.uci.ics.jung.visualization.VisualizationServer;
36
37 /**
38 * A <code>GraphElementAccessor</code> that returns elements whose <code>Shape</code>
39 * contains the specified pick point or region.
40 *
41 * @author Tom Nelson
42 *
43 */
44 public class ShapePickSupport<V, E> implements GraphElementAccessor<V,E> {
45
46 /**
47 * The available picking heuristics:
48 * <ul>
49 * <li/><code>Style.CENTERED</code>: returns the element whose
50 * center is closest to the pick point.
51 * <li/><code>Style.LOWEST</code>: returns the first such element
52 * encountered. (If the element collection has a consistent
53 * ordering, this will also be the element "on the bottom",
54 * that is, the one which is rendered first.)
55 * <li/><code>Style.HIGHEST</code>: returns the last such element
56 * encountered. (If the element collection has a consistent
57 * ordering, this will also be the element "on the top",
58 * that is, the one which is rendered last.)
59 * </ul>
60 *
61 */
62 public static enum Style { LOWEST, CENTERED, HIGHEST };
63
64 /**
65 *
66 *
67 */
68 protected float pickSize;
69
70 /**
71 * The <code>VisualizationServer</code> in which the
72 * this instance is being used for picking. Used to
73 * retrieve properties such as the layout, renderer,
74 * vertex and edge shapes, and coordinate transformations.
75 */
76 protected VisualizationServer<V,E> vv;
77
78 /**
79 * The current picking heuristic for this instance. Defaults
80 * to <code>CENTERED</code>.
81 */
82 protected Style style = Style.CENTERED;
83
84 /**
85 * Creates a <code>ShapePickSupport</code> for the <code>vv</code>
86 * VisualizationServer, with the specified pick footprint and
87 * the default pick style.
88 * The <code>VisualizationServer</code> is used to access
89 * properties of the current visualization (layout, renderer,
90 * coordinate transformations, vertex/edge shapes, etc.).
91 * @param vv source of the current <code>Layout</code>.
92 * @param pickSize the size of the pick footprint for line edges
93 */
94 public ShapePickSupport(VisualizationServer<V,E> vv, float pickSize) {
95 this.vv = vv;
96 this.pickSize = pickSize;
97 }
98
99 /**
100 * Create a <code>ShapePickSupport</code> for the specified
101 * <code>VisualizationServer</code> with a default pick footprint.
102 * of size 2.
103 */
104 public ShapePickSupport(VisualizationServer<V,E> vv) {
105 this.vv = vv;
106 this.pickSize = 2;
107 }
108
109 /**
110 * Returns the style of picking used by this instance.
111 * This specifies which of the elements, among those
112 * whose shapes contain the pick point, is returned.
113 * The available styles are:
114 * <ul>
115 * <li/><code>Style.CENTERED</code>: returns the element whose
116 * center is closest to the pick point.
117 * <li/><code>Style.LOWEST</code>: returns the first such element
118 * encountered. (If the element collection has a consistent
119 * ordering, this will also be the element "on the bottom",
120 * that is, the one which is rendered first.)
121 * <li/><code>Style.HIGHEST</code>: returns the last such element
122 * encountered. (If the element collection has a consistent
123 * ordering, this will also be the element "on the top",
124 * that is, the one which is rendered last.)
125 * </ul>
126 *
127 * @return the style of picking used by this instance
128 */
129 public Style getStyle() {
130 return style;
131 }
132
133 /**
134 * Specifies the style of picking to be used by this instance.
135 * This specifies which of the elements, among those
136 * whose shapes contain the pick point, will be returned.
137 * The available styles are:
138 * <ul>
139 * <li/><code>Style.CENTERED</code>: returns the element whose
140 * center is closest to the pick point.
141 * <li/><code>Style.LOWEST</code>: returns the first such element
142 * encountered. (If the element collection has a consistent
143 * ordering, this will also be the element "on the bottom",
144 * that is, the one which is rendered first.)
145 * <li/><code>Style.HIGHEST</code>: returns the last such element
146 * encountered. (If the element collection has a consistent
147 * ordering, this will also be the element "on the top",
148 * that is, the one which is rendered last.)
149 * </ul>
150 * @param style the style to set
151 */
152 public void setStyle(Style style) {
153 this.style = style;
154 }
155
156 /**
157 * Iterates over Vertices, checking to see if x,y is contained in the
158 * Vertex's Shape. If (x,y) is contained in more than one vertex, use
159 * the vertex whose center is closest to the pick point.
160 * @see edu.uci.ics.jung.visualization.picking.PickSupport#getVertex(double, double)
161 */
162 public V getVertex(Layout<V, E> layout, double x, double y) {
163
164 V closest = null;
165 double minDistance = Double.MAX_VALUE;
166 Point2D ip = vv.getRenderContext().getMultiLayerTransformer().inverseTransform(Layer.VIEW,
167 new Point2D.Double(x,y));
168 x = ip.getX();
169 y = ip.getY();
170
171 while(true) {
172 try {
173 for(V v : getFilteredVertices(layout)) {
174
175 Shape shape = vv.getRenderContext().getVertexShapeTransformer().transform(v);
176 // get the vertex location
177 Point2D p = layout.transform(v);
178 if(p == null) continue;
179 // transform the vertex location to screen coords
180 p = vv.getRenderContext().getMultiLayerTransformer().transform(Layer.LAYOUT, p);
181
182 double ox = x - p.getX();
183 double oy = y - p.getY();
184
185 if(shape.contains(ox, oy)) {
186
187 if(style == Style.LOWEST) {
188 // return the first match
189 return v;
190 } else if(style == Style.HIGHEST) {
191 // will return the last match
192 closest = v;
193 } else {
194
195 // return the vertex closest to the
196 // center of a vertex shape
197 Rectangle2D bounds = shape.getBounds2D();
198 double dx = bounds.getCenterX() - ox;
199 double dy = bounds.getCenterY() - oy;
200 double dist = dx * dx + dy * dy;
201 if (dist < minDistance) {
202 minDistance = dist;
203 closest = v;
204 }
205 }
206 }
207 }
208 break;
209 } catch(ConcurrentModificationException cme) {}
210 }
211 return closest;
212 }
213
214 /**
215 * Returns the vertices whose layout coordinates are contained in
216 * <code>Shape</code>.
217 * The shape is in screen coordinates, and the graph vertices
218 * are transformed to screen coordinates before they are tested
219 * for inclusion.
220 * @return the <code>Collection</code> of vertices whose <code>layout</code>
221 * coordinates are contained in <code>shape</code>.
222 */
223 public Collection<V> getVertices(Layout<V, E> layout, Shape shape) {
224 Set<V> pickedVertices = new HashSet<V>();
225
226 // remove the view transform from the rectangle
227 shape = vv.getRenderContext().getMultiLayerTransformer().inverseTransform(Layer.VIEW, shape);
228
229 while(true) {
230 try {
231 for(V v : getFilteredVertices(layout)) {
232 Point2D p = layout.transform(v);
233 if(p == null) continue;
234
235 p = vv.getRenderContext().getMultiLayerTransformer().transform(Layer.LAYOUT, p);
236 if(shape.contains(p)) {
237 pickedVertices.add(v);
238 }
239 }
240 break;
241 } catch(ConcurrentModificationException cme) {}
242 }
243 return pickedVertices;
244 }
245
246 /**
247 * Returns an edge whose shape intersects the 'pickArea' footprint of the passed
248 * x,y, coordinates.
249 */
250 public E getEdge(Layout<V, E> layout, double x, double y) {
251
252 Point2D ip = vv.getRenderContext().getMultiLayerTransformer().inverseTransform(Layer.VIEW, new Point2D.Double(x,y));
253 x = ip.getX();
254 y = ip.getY();
255
256 // as a Line has no area, we can't always use edgeshape.contains(point) so we
257 // make a small rectangular pickArea around the point and check if the
258 // edgeshape.intersects(pickArea)
259 Rectangle2D pickArea =
260 new Rectangle2D.Float((float)x-pickSize/2,(float)y-pickSize/2,pickSize,pickSize);
261 E closest = null;
262 double minDistance = Double.MAX_VALUE;
263 while(true) {
264 try {
265 for(E e : getFilteredEdges(layout)) {
266
267 Shape edgeShape = getTransformedEdgeShape(layout, e);
268 if (edgeShape == null)
269 continue;
270
271 // because of the transform, the edgeShape is now a GeneralPath
272 // see if this edge is the closest of any that intersect
273 if(edgeShape.intersects(pickArea)) {
274 float cx=0;
275 float cy=0;
276 float[] f = new float[6];
277 PathIterator pi = new GeneralPath(edgeShape).getPathIterator(null);
278 if(pi.isDone()==false) {
279 pi.next();
280 pi.currentSegment(f);
281 cx = f[0];
282 cy = f[1];
283 if(pi.isDone()==false) {
284 pi.currentSegment(f);
285 cx = f[0];
286 cy = f[1];
287 }
288 }
289 float dx = (float) (cx - x);
290 float dy = (float) (cy - y);
291 float dist = dx * dx + dy * dy;
292 if (dist < minDistance) {
293 minDistance = dist;
294 closest = e;
295 }
296 }
297 }
298 break;
299 } catch(ConcurrentModificationException cme) {}
300 }
301 return closest;
302 }
303
304 /**
305 * Retrieves the shape template for <code>e</code> and
306 * transforms it according to the positions of its endpoints
307 * in <code>layout</code>.
308 * @param layout the <code>Layout</code> which specifies
309 * <code>e</code>'s endpoints' positions
310 * @param e the edge whose shape is to be returned
311 * @return
312 */
313 private Shape getTransformedEdgeShape(Layout<V, E> layout, E e) {
314 Pair<V> pair = layout.getGraph().getEndpoints(e);
315 V v1 = pair.getFirst();
316 V v2 = pair.getSecond();
317 boolean isLoop = v1.equals(v2);
318 Point2D p1 = vv.getRenderContext().getMultiLayerTransformer().transform(Layer.LAYOUT, layout.transform(v1));
319 Point2D p2 = vv.getRenderContext().getMultiLayerTransformer().transform(Layer.LAYOUT, layout.transform(v2));
320 if(p1 == null || p2 == null)
321 return null;
322 float x1 = (float) p1.getX();
323 float y1 = (float) p1.getY();
324 float x2 = (float) p2.getX();
325 float y2 = (float) p2.getY();
326
327 // translate the edge to the starting vertex
328 AffineTransform xform = AffineTransform.getTranslateInstance(x1, y1);
329
330 Shape edgeShape =
331 vv.getRenderContext().getEdgeShapeTransformer().transform(Context.<Graph<V,E>,E>getInstance(vv.getGraphLayout().getGraph(),e));
332 if(isLoop) {
333 // make the loops proportional to the size of the vertex
334 Shape s2 = vv.getRenderContext().getVertexShapeTransformer().transform(v2);
335 Rectangle2D s2Bounds = s2.getBounds2D();
336 xform.scale(s2Bounds.getWidth(),s2Bounds.getHeight());
337 // move the loop so that the nadir is centered in the vertex
338 xform.translate(0, -edgeShape.getBounds2D().getHeight()/2);
339 } else {
340 float dx = x2 - x1;
341 float dy = y2 - y1;
342 // rotate the edge to the angle between the vertices
343 double theta = Math.atan2(dy,dx);
344 xform.rotate(theta);
345 // stretch the edge to span the distance between the vertices
346 float dist = (float) Math.sqrt(dx*dx + dy*dy);
347 xform.scale(dist, 1.0f);
348 }
349
350 // transform the edge to its location and dimensions
351 edgeShape = xform.createTransformedShape(edgeShape);
352 return edgeShape;
353 }
354
355 /**
356 *
357 * @param layout
358 * @return
359 */
360 protected Collection<V> getFilteredVertices(Layout<V,E> layout) {
361 if(verticesAreFiltered()) {
362 Collection<V> unfiltered = layout.getGraph().getVertices();
363 Collection<V> filtered = new LinkedHashSet<V>();
364 for(V v : unfiltered) {
365 if(isVertexRendered(Context.<Graph<V,E>,V>getInstance(layout.getGraph(),v))) {
366 filtered.add(v);
367 }
368 }
369 return filtered;
370 } else {
371 return layout.getGraph().getVertices();
372 }
373 }
374
375 /**
376 *
377 * @param layout
378 * @return
379 */
380 protected Collection<E> getFilteredEdges(Layout<V,E> layout) {
381 if(edgesAreFiltered()) {
382 Collection<E> unfiltered = layout.getGraph().getEdges();
383 Collection<E> filtered = new LinkedHashSet<E>();
384 for(E e : unfiltered) {
385 if(isEdgeRendered(Context.<Graph<V,E>,E>getInstance(layout.getGraph(),e))) {
386 filtered.add(e);
387 }
388 }
389 return filtered;
390 } else {
391 return layout.getGraph().getEdges();
392 }
393 }
394
395 /**
396 * Quick test to allow optimization of <code>getFilteredVertices()</code>.
397 * @return <code>true</code> if there is an active vertex filtering
398 * mechanism for this visualization, <code>false</code> otherwise
399 */
400 protected boolean verticesAreFiltered() {
401 Predicate<Context<Graph<V,E>,V>> vertexIncludePredicate =
402 vv.getRenderContext().getVertexIncludePredicate();
403 return vertexIncludePredicate != null &&
404 vertexIncludePredicate instanceof TruePredicate == false;
405 }
406
407 /**
408 * Quick test to allow optimization of <code>getFilteredEdges()</code>.
409 * @return <code>true</code> if there is an active edge filtering
410 * mechanism for this visualization, <code>false</code> otherwise
411 */
412 protected boolean edgesAreFiltered() {
413 Predicate<Context<Graph<V,E>,E>> edgeIncludePredicate =
414 vv.getRenderContext().getEdgeIncludePredicate();
415 return edgeIncludePredicate != null &&
416 edgeIncludePredicate instanceof TruePredicate == false;
417 }
418
419 /**
420 * Returns <code>true</code> if this vertex in this graph is included
421 * in the collections of elements to be rendered, and <code>false</code> otherwise.
422 * @param context the vertex and graph to be queried
423 * @return <code>true</code> if this vertex is
424 * included in the collections of elements to be rendered, <code>false</code>
425 * otherwise.
426 */
427 protected boolean isVertexRendered(Context<Graph<V,E>,V> context) {
428 Predicate<Context<Graph<V,E>,V>> vertexIncludePredicate =
429 vv.getRenderContext().getVertexIncludePredicate();
430 return vertexIncludePredicate == null || vertexIncludePredicate.evaluate(context);
431 }
432
433 /**
434 * Returns <code>true</code> if this edge and its endpoints
435 * in this graph are all included in the collections of
436 * elements to be rendered, and <code>false</code> otherwise.
437 * @param context the edge and graph to be queried
438 * @return <code>true</code> if this edge and its endpoints are all
439 * included in the collections of elements to be rendered, <code>false</code>
440 * otherwise.
441 */
442 protected boolean isEdgeRendered(Context<Graph<V,E>,E> context) {
443 Predicate<Context<Graph<V,E>,V>> vertexIncludePredicate =
444 vv.getRenderContext().getVertexIncludePredicate();
445 Predicate<Context<Graph<V,E>,E>> edgeIncludePredicate =
446 vv.getRenderContext().getEdgeIncludePredicate();
447 Graph<V,E> g = context.graph;
448 E e = context.element;
449 boolean edgeTest = edgeIncludePredicate == null || edgeIncludePredicate.evaluate(context);
450 Pair<V> endpoints = g.getEndpoints(e);
451 V v1 = endpoints.getFirst();
452 V v2 = endpoints.getSecond();
453 boolean endpointsTest = vertexIncludePredicate == null ||
454 (vertexIncludePredicate.evaluate(Context.<Graph<V,E>,V>getInstance(g,v1)) &&
455 vertexIncludePredicate.evaluate(Context.<Graph<V,E>,V>getInstance(g,v2)));
456 return edgeTest && endpointsTest;
457 }
458
459 /**
460 * Returns the size of the edge picking area.
461 * The picking area is square; the size is specified as the length of one
462 * side, in view coordinates.
463 * @return the size of the edge picking area
464 */
465 public float getPickSize() {
466 return pickSize;
467 }
468
469 /**
470 * Sets the size of the edge picking area.
471 * @param the length of one side of the (square) picking area, in view coordinates
472 */
473 public void setPickSize(float pickSize) {
474 this.pickSize = pickSize;
475 }
476
477 }