/*******************************************************************************
+
+  LEDA 7.2.3  
+
+
+  frechet_distance.cpp
+
+
+  Copyright (c) 1995-2026
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/


#include <LEDA/graphics/window.h>
#include <LEDA/core/array.h>

using namespace leda;

const int light_grey = 0xfafafa;

const int light_red    = 0xffe0e0;
const int light_green  = 0xe0ffe0;
const int light_blue   = 0xe0e0ff;

//const int light_yellow = 0xffffe0;
const int light_yellow = 0xffffc0;


static double mouse_x = -1;
static double mouse_y = -1;

static bool show_message = true;

static array<segment> P1;
static array<segment> P2;

static double leash_distance = 0;
static int move_seg = 0;


double relative_distance(point p, segment s)
{ double f = p.distance(s.start())/s.length();
  if (side_of_halfspace(s.start(),s.end(),p) < 0) f = -f;
  return f;
}

point project_to_segment(double f, segment s)
{ vector vec = s.end() - s.start();
  return s.start().translate(f*vec);
}


void draw_ellipse(window& W, segment s1, segment s2, double dist,
                                         double x0, double y0, double d,
                                         color clr1, color clr2, color clr3)
{
  int pix_min = 0;
  int pix_max = W.width();

  double x1 = x0 + d;
  double y1 = y0 + d;

  if (clr3 == invisible) {
    pix_min = W.xpix(x0);
    pix_max = W.xpix(x1);
  }

  int w = W.real_to_pix(d);

/*
  line line1(s1);
  line line2(s2);

  double d = leash_distance;
  vector v = d*s2.rotate(-LEDA_PI/2).to_vector().norm();

  point p_left;
  if (line1.intersection(line2+v,p_left))
  { double f_left = relative_distance(p_left,s1);
    point p_right;
    line1.intersection(line2-v,p_right);
    double f_right = relative_distance(p_right,s1);

    //W.draw(line2+v,grey1);
    //W.draw(line2-v,grey1);
    //W.set_node_width(5);
    //W.draw_filled_node(p_left,yellow);
    //W.draw_filled_node(p_right,yellow);

    if (f_left > f_right) swap(f_left,f_right);
    pix_min = W.xpix(x0) + int(f_left * w) - 1;
    pix_max = W.xpix(x0) + int(f_right * w) + 1;
  }
*/

  for(int x = pix_min; x <= pix_max; x++)
  {
    double fx =  double(x-W.xpix(x0))/w;

    point c = project_to_segment(fx,s1);

    list<point>  L = circle(c,dist).intersection(line(s2));

    if (L.empty()) continue;

    point q1 = L.front();
    point q2 = L.back();

    double f1 = relative_distance(q1,s2);
    double f2 = relative_distance(q2,s2);

    if (f1 > f2) swap(f1,f2);

    fx = x0 + fx*d;
    f1 = y0 + f1*d;
    f2 = y0 + f2*d;

    if (fx < x0 || fx > x1) 
    { W.draw_segment(fx,f1,fx,f2,clr2);
      W.draw_pixel(fx,f1,clr3);
      W.draw_pixel(fx,f2,clr3);
      continue;
    }

    if (f1 < y0) {
      W.draw_segment(fx,f1,fx,min(0.0,f2),clr2);
      W.draw_pixel(fx,f1,clr3);
      W.draw_pixel(fx,f2,clr3);
      f1 = y0;
    }

    if (f2 > y1) {
      W.draw_segment(fx,max(1.0,f1),fx,f2,clr2);
      W.draw_pixel(fx,f1,clr3);
      W.draw_pixel(fx,f2,clr3);
      f2 = y1;
    }

    if (f1 <= f2)
    { W.draw_segment(fx,f1,fx,f2,clr1);
      W.draw_pixel(fx,f1,clr3);
      W.draw_pixel(fx,f2,clr3);
    }
  }

  if (clr3 != invisible)
  { // draw center
    point c;
    if (s1.intersection_of_lines(s2,c))
    { double f1 = relative_distance(c,s1);
      double f2 = relative_distance(c,s2);
      int nw = W.set_node_width(2);
      W.draw_filled_node(f1,f2,grey3);
      W.set_node_width(nw);
     }
  }

}




void draw_grid(window& W, const array<segment>& P1, const array<segment>& P2)
{
  int n1 = P1.size();
  int n2 = P2.size();

  assert(n1 >= n2);

  double d = 1.0/n1;

  double dist = leash_distance;

  W.draw_box(0,0,n1*d,n2*d,0xe0e0e0);

  color fill_clr = light_yellow;
  color out_clr = invisible;
  color border_clr = invisible;

  if (n1 == 1 && n2 == 1)
  { border_clr = black;
    out_clr = light_grey;
   }

  for(int i=0; i<P1.size(); i++)
  { double x = i*d;
    for(int j=0; j<P2.size(); j++)
    { double y = j*d;
      draw_ellipse(W,P1[i],P2[j],dist,x,y,d,fill_clr,out_clr,border_clr);
     }
   }

  W.set_line_width(1);
  for(int i=0; i<=n1; i++) W.draw_segment(i*d,0,i*d,n2*d,grey3);
  for(int j=0; j<=n2; j++) W.draw_segment(0,j*d,n1*d,j*d,grey3);


  W.set_line_width(3);
  W.draw_arrow(0,0,n1*d,0,blue2);
  W.draw_arrow(0,0,0,n2*d,green2);

}


void draw_segments(window& W)
{
  W.set_line_width(3);
  for(int i=0; i<P1.size(); i++) W.draw_segment(P1[i],blue2);
  for(int i=0; i<P2.size(); i++) W.draw_segment(P2[i],green2);
}


  
void redraw(window* wp)
{
  window& W = *wp;

  if (P1.size() == 0 || P2.size() == 0) return;

  double xpos = mouse_x;
  double ypos = mouse_y;

  double fx = -1;
  double fy = -1;

  double dist = leash_distance;

  W.start_buffering();
  W.clear();

  W.del_messages();

  if (show_message)
  { W.message("Now move the mouse pointer around in the Free-Space Grid.");
    W.message("You can change the distance parameter using the slider.");
   }

  W.set_line_width(1);
  draw_grid(W,P1,P2);

  int n1 = P1.size();
  int n2 = P2.size();

  assert(n1 >= n2);

  double d = 1.0/n1;

  double ytop = n2*d;

  if (ypos <= ytop) 
  { 
    if (xpos < 0) xpos = 0;
    if (xpos > 1) xpos = 1;
    if (ypos < 0) ypos = 0;
    if (ypos > ytop) ypos = ytop;

    double fx = xpos/d;
    double fy = ypos/d;

    int i = int(fx);
    int j = int(fy);

    if (i < 0) i = 0;
    if (i > n1-1) i = n1-1;
    if (j < 0) j = 0;
    if (j > n2-1) j = n2-1;

    segment s1 = P1[i];
    segment s2 = P2[j];

    W.set_line_width(1);
    W.draw_segment(xpos,0,xpos,ytop,grey2);
    W.draw_segment(0,ypos,1,ypos,grey2);

    W.draw_ctext(xpos,-0.03,string("%.2f",fx),grey3);
    W.draw_ctext(-0.05,ypos,string("%.2f",fy),grey3);

    point p = project_to_segment(fx-i,s1);
    point q = project_to_segment(fy-j,s2);

    color clr = (p.distance(q) > dist) ? red : green;
    W.draw_filled_node(xpos,ypos,clr);
    W.draw_node(xpos,ypos,black);

    color light_clr  = (p.distance(q) > dist) ? light_red : light_green;

    W.set_line_width(1);
    W.draw_disc(p,dist,light_clr);
    W.draw_circle(p,dist,grey3);

    draw_segments(W);

    W.set_line_width(2);
    W.draw_segment(p,q,grey3);

    W.set_line_width(1);

    W.draw_filled_node(p,white);
    W.draw_node(p,grey3);

    W.draw_filled_node(q,white);
    W.draw_node(q,grey3);

    double dist = p.distance(q);
    color dclr = (dist <= leash_distance) ? black : red;  
    W.draw_ctext(0.5,ytop+0.03,string("dist = %.d",W.real_to_pix(dist)),dclr);

    show_message = false;
   }
  else
  {  
    if (P1.size() == 1 && P2.size() == 1)
    { segment s1 = P1[0];
      segment s2 = P2[0];

      point p(xpos,ypos);

      line line1(s1);
      point p1 = line1.perpendicular(p).target(); 
      double dist1 = p.distance(p1);

      line line2(s2);
      point p2 = line2.perpendicular(p).target(); 
      double dist2 = p.distance(p2);

      if (dist1 > 1 && dist2 > 1) 
        move_seg = 0;
      else
      { list<point> L;
        double f = 0;
  
        if (move_seg == 0) {
          if (dist1 < dist2) 
             move_seg = 1;
          else
             move_seg = 2;
        }
        
        if (move_seg == 1) {
          if (dist2 < dist1 && dist1 > 0.10) {
            move_seg = 2;
          }
        }
  
        if (move_seg == 2) {
          if (dist1 < dist2 && dist2 > 0.10) {
            move_seg = 1;
          }
        }
    
        if (move_seg == 1)
        { f = relative_distance(p1,s1);
          L = circle(p1,dist).intersection(line2);
          W.draw_filled_node(p1,black);
          W.set_line_width(1);
          W.draw_circle(p1,dist,grey3);
          if (f >=0 && f <= 1) {
            W.draw_segment(f,0,f,1,grey3);
            W.draw_ctext(f,-0.04,string("%.2f",f),grey3);
           }
         }
  
        if (move_seg == 2)
        { f = relative_distance(p2,s2);
          L = circle(p2,dist).intersection(line1);
          W.draw_filled_node(p2,black);
          W.set_line_width(1);
          W.draw_circle(p2,dist,grey3);
          if (f >=0 && f <= 1) {
            W.draw_segment(0,f,1,f,grey3);
            W.draw_ctext(-0.08,f,string("%.2f",f),grey3);
           }
         }
    
        if (!L.empty())
        { point q1 = L.pop();
          point q2 = L.empty() ? q1 : L.pop();
    
          W.draw_filled_node(q1,red);
          W.draw_filled_node(q2,red);
  
          if (move_seg == 1)
          { double f1 = relative_distance(q1,s2);
            double f2 = relative_distance(q2,s2);
            W.set_line_width(2);
            W.draw_segment(f,f1,f,f2,green2);
            W.draw_filled_node(f,f1,red);
            W.draw_filled_node(f,f2,red);
            W.set_line_width(1);
            W.draw_segment(p1,q1,grey2);
            W.draw_segment(p1,q2,grey2);
           }
  
          if (move_seg == 2)
          { double f1 = relative_distance(q1,s1);
            double f2 = relative_distance(q2,s1);
            W.set_line_width(2);
            W.draw_segment(f1,f,f2,f,blue);
            W.draw_filled_node(f1,f,red);
            W.draw_filled_node(f2,f,red);
            W.set_line_width(1);
            W.draw_segment(p2,q1,grey2);
            W.draw_segment(p2,q2,grey2);
           }
        }
      }
   }

   draw_segments(W);
  }

  W.flush_buffer();
  W.stop_buffering();

}


void set_leash(int x) 
{ window* wp = window::get_call_window();
  leash_distance = wp->pix_to_real(x);
  redraw(wp);
}

  

int main()
{   
  window W("The Frechet Distance of 2 Polylines");

  int dpi = window::screen_dpi();

  int dpx = 100;
  W.int_item("  Length of Leash",dpx,0,500,set_leash);
  W.button("Restart",1);
  W.make_menu_bar();

  W.set_redraw(redraw);

  W.init(-0.25,1.25,-0.075);

  W.display();

//W.set_node_width(5);
  W.set_node_width(dpi/32);


  for(;;)
  {
    show_message = true;

    dpx = 100;
    leash_distance =  W.pix_to_real(dpx);
    W.redraw_panel();

    W.disable_button(1);

    W.clear();
    W.message("Draw a polyline using the left mouse button \
               (finish by clicking the right button).");

    W.set_line_width(3);

    P1.resize(0);
    P2.resize(0);

    polygon poly;
    W.set_color(blue2);
    W >> poly;

    int i = 0;
    int j = 0;
    segment s;

    P1.resize(poly.size()-1);
    forall_segments(s,poly) 
    { if (i == poly.size()-1) break;
      W.draw_segment(s,blue2);
      P1[i++] = s;
     }

    W.clear();
    draw_segments(W);
    W.message("Draw a second polyline close to the first line.");

    W.set_color(green2);
    W >> poly;

    P2.resize(poly.size()-1);
    forall_segments(s,poly) 
    { if (j == poly.size()-1) break;
      W.draw_segment(s,green2);
      P2[j++] = s;
     }

    if (P2.size() > P1.size()) {
      //swap(P1,P2);
      array<segment> Q = P1;
      P1 = P2;
      P2 = Q;
    }

    draw_segments(W);


    W.enable_button(1);

    int but = 0;
    double x,y;
    unsigned long t = 0;
    while (W.read_event(but,x,y,t) != button_press_event || but != 1)   
    { 
      int dx = W.real_to_pix(x - mouse_x);
      int dy = W.real_to_pix(y - mouse_y);
      int d = dx*dx + dy*dy;

      //if (d <= 2) continue;
      //if (d <= 1) continue;

      if (d < 8) continue;

      mouse_x = x;
      mouse_y = y;

      redraw(&W);
    }

  }

  return 0;
}
