/*******************************************************************************
+
+  LEDA 3.5
+
+  locate.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include<math.h>
#include <LEDA/graphwin.h>

//----------------------------------------------------------------------------

static double distance(const point& p, const list<point>& P) {

  if (P.empty()) return MAXDOUBLE;
  
  double d_min=MAXDOUBLE;

  list_item it=P.first();
  
  point p1=P[it],p2;
  
  double x_min,y_min,x_max,y_max;
  
  double x=p.xcoord();
  double y=p.ycoord();

  while ((it=P.succ(it)) != nil) {
  
    p2=P[it];
    
    if (p1.xcoord() > p2.xcoord()) {
      x_min=p2.xcoord();
      x_max=p1.xcoord();
    }
    else {
      x_min=p1.xcoord();
      x_max=p2.xcoord();
    }
    
    if (p1.ycoord() > p2.ycoord()) {
      y_min=p2.ycoord();
      y_max=p1.ycoord();
    }
    else {
      y_min=p1.ycoord();
      y_max=p2.ycoord();
    }
    
    bool b=true;
    
    if (y_max-y_min > x_max-x_min) {
        if ((y<y_min)||(y>y_max)) b=false;
    }
    else {
      if ((x<x_min)||(x>x_max)) b=false;
    }
      
    if (b) {
      double d = (line(p1,p2).perpendicular(p)).length();
      if (d < d_min) d_min=d;
    }
        
    p1=p2;
  
  }

  return d_min;

}

//----------------------------------------------------------------------------

edge GraphWin::find_edge(const point& p, edge from) { 

  edge e_min = nil;

  double d,d_min = MAXDOUBLE;

  edge e = from == nil ? gr_p->first_edge() : gr_p->succ_edge(from);

  while (e != nil) {
  
    d=distance(p,e_info[e].p);
    
    if (d < d_min) {
      e_min = e;
      d_min = d;
    }      
    
    e=gr_p->succ_edge(e);

  }

  if (d_min < 10.0/win_p->scale()) found_edge=e_min;
  else found_edge=nil;

  return found_edge;
}
 
//----------------------------------------------------------------------------

node GraphWin::find_node(const point& p, node from) {
   
  //node v = (from == nil) ? gr_p->first_node() : gr_p->succ_node(from);


//sn: search from last node to first node

  node v = (from == nil) ? gr_p->last_node() : gr_p->pred_node(from);

  point v_p;
  double v_x,v_y;
  
  double p_x=p.xcoord();
  double p_y=p.ycoord();
  double r1,r2;

  bool stop_search=false;
  
  while (v != nil) {
    
    v_p=get_position(v);
    v_x=v_p.xcoord(); 
    v_y=v_p.ycoord();
    r1=get_radius1(v); 
    r2=get_radius2(v);
    
    switch (get_shape(v)) {
    
      case circle_node:
        if (p.distance(get_position(v)) < r1) stop_search=true;
        break;
    
      case ellipse_node: {
        double dx=p_x-v_x;
        double dy=p_y-v_y;
        if ( dx*dx/(r1*r1) + dy*dy/(r2*r2) <= 1.0 ) stop_search=true;
      }
        break;
      
      case square_node:
        r2=r1;

      case rectangle_node: 
        if ( (p_x >= v_x-r1) && (p_x <= v_x+r1) 
                             && 
             (p_y >= v_y-r2) && (p_y <= v_y+r2) ) stop_search=true;
        break;
      
    }

    if (stop_search) break;
    
    v=gr_p->pred_node(v);  
  }
  
  found_node=v;

  return v;
}

//----------------------------------------------------------------------------
