node.java

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

	     (exit = e.destination.exitPoint(dir)) != null)
	  {
	    oldPosition = new Point (exit);
	    oldPosition.x += offset*Edge.xNorm[dir];
	    oldPosition.y += offset*Edge.yNorm[dir];
	  }
      }
    if (oldPosition == null)
      {
	oldPosition = new Point();
	int r = rnd.nextInt() % 300;
	r = (r > 0)? r : (-r);
	oldPosition.x = r;
	r = rnd.nextInt() % 300;
	r = (r > 0)? r : (-r);
	oldPosition.y = r;
      }
    newPosition = new Point(oldPosition);
    currentPosition = new Point(oldPosition);
  }

  
  /**
   *  Try to find a more visibly pleasing position for this node.
   *  The chosen position will be assigned as the new position.
   *
   *   @param gi Graphics context information
   *   @param graph  The data graph within which this node occurs.
   *   @param targetLength  Desired average length for all edges.
   */
  void reposition (GraphicsInfo gi, IDTree graph, double targetLength)
  {
    double zeroLimit = 1.0E-10;
    
    if (oldPosition == null)
      {
	chooseInitialPosition (gi, graph);
      }
    else
      {
	if (currentPosition == null)
	    currentPosition = new Point(oldPosition.x, oldPosition.y);
	if (newPosition == null)
	    newPosition = new Point(currentPosition.x, currentPosition.y);
	
	oldPosition.x = currentPosition.x = newPosition.x;
	oldPosition.y = currentPosition.y = newPosition.y;

	// Positions are scored - we seek to minimize the score

	// First, approximate the gradient of the score function
	double score0 = positionScore(targetLength);
	currentPosition.x += 5;
	double score1 = positionScore(targetLength);
	currentPosition.x -= 5;
	currentPosition.y += 5;
	double score2 = positionScore(targetLength);
	currentPosition.y -= 5;
	Debug.show(Debug.reposition, "reposition ", ID());
	Debug.show(Debug.reposition, "  score0: " , score0);
	Debug.show(Debug.reposition, "  score1: " , score1);
	Debug.show(Debug.reposition, "  score2: " , score2);

	
	double gradx = score0 - score1;
	double grady = score0 - score2;

	// If the node is near the edge of the canvas, and the gradient
	// has a component that would move us past that edge, zero out
	// that component so we "slide" along the edge.
	if (gradx < 0 && currentPosition.x < 2*gi.getTextOffset().width)
	  gradx = 0.0;
	else if (gradx > 0
		 && currentPosition.x + nodeSize.width >
		 gi.getCanvasSize().width - 2*gi.getTextOffset().width)
	  gradx = 0.0;
	if (grady < 0 && currentPosition.y < 2*gi.getTextOffset().height)
	  grady = 0.0;
	else if (grady > 0
		 && currentPosition.y + nodeSize.height >
		 gi.getCanvasSize().height - 2*gi.getTextOffset().height)
	  grady = 0.0;
	
	double len = Math.sqrt(gradx*gradx + grady*grady);
	Debug.show(Debug.reposition, "  gradient.x: ",  gradx);
	Debug.show(Debug.reposition, "  gradient.y: ",  grady);
      

	if (len < zeroLimit) {
	  // Can't find a measureable gradient
	  // Choose a direction at random.
	  Debug.show(Debug.reposition, "  random gradient direction");
	  gradx = 1.0 - 2.0*rnd.nextDouble();
	  grady = Math.sqrt(1 - gradx*gradx);
	}
	else {
	  gradx = gradx / len;
	  grady = grady / len;
	}

	// Consider a line starting from currentPosition, extending
	// in the direction (gradx, grady), until it hits the edge
	// of the window.

	Point targetPosition = new Point();
	double tx, ty;
	if (gradx > zeroLimit)
	  tx = (gi.getCanvasSize().width - newPosition.x - nodeSize.width) / gradx;
	else if (gradx < -zeroLimit)
	  tx = (newPosition.x) / (-gradx);
	else
	  tx = 1.0 / zeroLimit;
      
	if (grady > zeroLimit)
	  ty = (gi.getCanvasSize().height - newPosition.y  - nodeSize.height)
	    / grady;
	else if (grady < -zeroLimit)
	  ty = (newPosition.y) / (-grady);
	else
	  ty = 1.0 / zeroLimit;

	Debug.show(Debug.reposition, "  tx ", tx);
	Debug.show(Debug.reposition, "  ty ", ty);

	tx = (tx < ty) ? tx : ty;
	
	targetPosition.x = newPosition.x + (int)(tx*gradx);
	targetPosition.y = newPosition.y + (int)(tx*grady);

	newPosition = optimalPosition
	  (targetLength, oldPosition, targetPosition);
	currentPosition.x = oldPosition.x = newPosition.x;
	currentPosition.y = oldPosition.y = newPosition.y;
      }
  }

  /**
   * @return The current position of the node.
   */
  public Point position()
  {
    IDTree par = parent();
    if (par.parent() != null)
      {
	Point parentPos = ((Node)par).position();
	if (parentPos != null)
	  {
	    Point p = new Point (parentPos);
	    if (oldPosition != null)
	      {
		p.x += oldPosition.x;
		p.y += oldPosition.y;
	      }
	    return p;
	  }
	else
	  return null;
      }
    else
      return currentPosition;
  }

  /**
   * @return The current size of the node (in pixels).
   */
  public Dimension size()
  {
    return new Dimension(nodeSize);
  }

  /**
   * Sets the old, new, and current position of the node to a specified point.
   *
   *  @param p  The position at which to place the node.
   */
  public void setPosition(Point p)
  {
    if (oldPosition == null) {
      oldPosition = new Point(p);
      newPosition = new Point(p);
      currentPosition = new Point(p);
    }
    else {
      oldPosition.x = newPosition.x = currentPosition.x = p.x;
      oldPosition.y = newPosition.y = currentPosition.y = p.y;
    }
  }


  /**
   * Saves the (old) position to be restored by a <code>endPositioning</code>
   * call
   *
   */
  public void beginPositioning()
  {
    if (oldPosition != null) {
      savedPosition.x = oldPosition.x;
      savedPosition.y = oldPosition.y;
    }
  }


  /**
   * Restores the (old) position saved by a <code>beginPositioning</code>
   * call. Sets the current position to this same oldPosition.
   *
   */
  public void endPositioning()
  {
    if (oldPosition != null) {
      currentPosition.x = oldPosition.x = savedPosition.x;
      currentPosition.y = oldPosition.y = savedPosition.y;
    }
  }





  /**
   * Shifts the old, current, & new positions 
   *
   *  @param dx  The amount to add to the x coordinate
   *  @param dy  The amount to add to the y coordinate
   */
  void translate(int dx, int dy)
  {
    IDTree par = parent();
    if (par.parent() == null)
      {
	if (oldPosition != null) {
	  oldPosition.x += dx;
	  currentPosition.x += dx;
	  newPosition.x += dx;
	  oldPosition.y += dy;
	  currentPosition.y += dy;
	  newPosition.y += dy;
      }
   }
  }


  /**
   * Rescales the old, current, & new positions 
   *
   *  @param sx  The scale factor by which to multiply the x coordinate
   *  @param sy  The scale factor by which to multiply the y coordinate
   */
  void scale(double sx, double sy)
  {
    IDTree par = parent();
    if (par.parent() == null)
      {
        if (oldPosition != null) {
	  oldPosition.x = (int)(sx * (double)oldPosition.x);
          currentPosition.x = (int)(sx * (double)currentPosition.x);
	  newPosition.x = (int)(sx * (double)newPosition.x);

          oldPosition.y = (int)(sy * (double)oldPosition.y);
	  currentPosition.y = (int)(sy * (double)currentPosition.y);
          newPosition.y = (int)(sy * (double)newPosition.y);
      }
  }
  }


  /**
   *  Does the point p lie within this node?
   *   @param p  an (x,y) coordinate
   *   @return true iff p lies within this node
   */
  public boolean contains (Point p)
  {
    if (currentPosition == null)
      return false;
    else
      return ((currentPosition.x <= p.x) 
              && (currentPosition.x + nodeSize.width >= p.x) 
              && (currentPosition.y <= p.y) 
              && (currentPosition.y + nodeSize.height >= p.y));
  }
  
  /**
   *  Set the node's new position equal to its current position.
   */
  void freeze()
  {
    if (oldPosition != null)
      {
       newPosition.x = oldPosition.x = currentPosition.x;
       newPosition.y = oldPosition.y = currentPosition.y;
      }
  }
  
      
  
  /**
   *  Find the center of the rectangular area occupied by this node.
   *   @return coordinates of the center point
   */
  public Point center()
  {
    Point c = new Point(position());
    c.x += nodeSize.width / 2;
    c.y += nodeSize.height / 2;
    
    return c;
  }

  static private final int xPerimeter[] =
  {2, 3, 4, 4, 4, 4, 4, 3, 2, 1, 0, 0, 0, 0, 0, 1};
  static private final int yPerimeter[] =
  {0, 0, 0, 1, 2, 3, 4, 4, 4, 4, 4, 3, 2, 1, 0, 0};


  /**
   *  Where would an outgoing edge leave this node?
   *  @param  direction  Any direction except <code>ANYDIR</code>
   *  @return coordinates of the point on the perimeter of this node at
   *     which an edge with the given <code>direction</code> would emerge.
   */
  public Point exitPoint (int direction)
  {
    Point p = new Point();
    Point currentPos = position();
    if (currentPos != null)
      {
	if (direction < Direction.ANYDIR)
	  {
	    p.x = currentPos.x + xPerimeter[direction] * nodeSize.width / 4;
	    p.y = currentPos.y + yPerimeter[direction] * nodeSize.height / 4;
	  }
	else
	  {
	    p.x = currentPos.x;
	    p.y = currentPos.y;
	  }
      }
    else
      p = null;
    return p;
  }
  
  /**
   *  Recompute the node's current position based on the increment
   *  setting of the graphics context.
   *  @param gi the graphics context
   */
  void incrementPosition(GraphicsInfo gi)
  {
    if (oldPosition != null) {
      int step = gi.getInterpolationStep();
      int nSteps = gi.getInterpolationTotal();
      
      currentPosition.x = oldPosition.x +
	step * (newPosition.x - oldPosition.x) / nSteps;
      currentPosition.y = oldPosition.y +
	step * (newPosition.y - oldPosition.y) / nSteps;
      if (step == nSteps)
	{
	  oldPosition.x = newPosition.x;
	  oldPosition.y = newPosition.y;
	}
    }
  }

  /**
   *  Aids in computing direction to a point
   */
  private static int eastEdge[] =
  {Direction.NE, Direction.NE, Direction.ENE, Direction.ENE,
   Direction.E,
   Direction.ESE, Direction.ESE, Direction.SE, Direction.SE
  };
  private static int westEdge[] =
  {Direction.SW, Direction.SW, Direction.WSW, Direction.WSW,
   Direction.W,
   Direction.WNW, Direction.WNW, Direction.NW, Direction.NW
  };
  private static int northEdge[] =
  {Direction.NE, Direction.NE, Direction.NNE, Direction.NNE,
   Direction.N,
   Direction.NNW, Direction.NNW, Direction.NW, Direction.NW
  };
  private static int southEdge[] =
  {Direction.SW, Direction.SW, Direction.SSW, Direction.SSW,
   Direction.S,
   Direction.SSE, Direction.SSE, Direction.SE, Direction.SE
  };
  
  



  /**
   *  Determine the direction (among the 16 values of
   *   <code>AlgAE.Direction</code>) that most nearly points from the center
   *   of this node to the point <code>p</code>.
   *  @param p Any (x,y) coordinate
   *  @return A direction value
   */
  public int directionTo (Point p)
  {
    boolean debug = Debug.directionTo;

    Point cent = center();
    
    Debug.show(debug, "directionTo//p: ", p);
    Debug.show(debug, "directionTo//cent: ", cent);

    Point offset = new Point(nodeSize.height * (p.x-cent.x),
			     nodeSize.width * (p.y-cent.y));
    Debug.show(debug, "directionTo//offset: ", offset);

    if (offset.x == 0 && offset.y == 0)
      return Direction.ANYDIR;

    int absx = Math.abs(offset.x);
    int absy = Math.abs(offset.y);
    
    int quarters = (absx > absy)
                   ? (4* offset.y / offset.x)
                   : (4* offset.x / offset.y);
    Debug.show(debug, "directionTo//quarters: ", quarters);

    int index = 0;
    if (absx > absy) 
      if (offset.x > 0)
	index = eastEdge[quarters + 4];
      else
	index = westEdge[quarters + 4];
    else
      if (offset.y > 0)
	index = southEdge[quarters + 4];
      else
	index = northEdge[quarters + 4];

    Debug.show(debug, "directionTo//index: ", index);
    
    return index;
  }

  
}