third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/RadiusGraphElementAccessor.java

   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 }