geowin_chull_incr.c

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

#include <LEDA/geowin.h>
#include <LEDA/geo_global_enums.h>
#include <LEDA/rat_geo_alg.h>
#include <LEDA/polygon.h>

#define POINT    point
#define SEGMENT  segment

class ch_edge;

static ch_edge* last_edge = NULL;

class ch_edge {

public:

POINT   source;
POINT   target;
ch_edge* succ;
ch_edge* pred;
ch_edge* link;
bool     outside;

ch_edge(const POINT& a, const POINT& b) : source(a), target(b) 
{ outside = true; 
  link = last_edge;
  last_edge = this;
}

~ch_edge() {}

};

bool bval;

void window_output(window& w, const POINT& p, ch_edge* e , ch_edge* low, ch_edge* high)
{ // output point ...
  point_style pold = w.set_point_style(disc_point);
  w << p;
  w.set_point_style(pold);
  
  // output current hull ...
  ch_edge* e_start = e;
  do {
    w << SEGMENT(e->source,e->target);
    e = e->succ;
  } while ((e != e_start) && (e!= NULL));
  
  //output higher and lower tangent ...
  if (low != NULL){
    color cold = w.set_color(red);
    w << SEGMENT(p,low->target);
    w.set_color(green);
    w << SEGMENT(p,high->source);
    w.set_color(cold);
  }

  if (bval) w.read_mouse();
  else leda_wait(0.6);
}

list<POINT>  GW_CONVEX_HULL_IC(const list<POINT>& L)
{ 
  GeoWin* gw = GeoWin::get_call_geowin();
  window& w = gw->get_window();
  w.clear();
  
  if (L.length() < 2) return L;

  list<POINT> CH;

  POINT a = L.head();
  POINT b = L.tail();
  POINT c, p;

  if ( a == b )
  { forall(p,L)
      if (p != a) { b = p; break; }
    if ( a == b )
    { // all points are equal
      CH.append(a);
      return CH; 
    } 
  }

  int orient = 0; 
  forall(c,L)
    if ( (orient = orientation(a,b,c)) != 0 ) break;

  if ( orient == 0 )
  { // all points are collinear 
    forall(p,L)
    { if ( compare(p,a) < 0 ) a = p;
      if ( compare(p,b) > 0 ) b = p;
    }
    CH.append(a); CH.append(b);
    return CH;
  }
  // a, b, and c are not collinear

  if ( orient < 0 ) leda_swap(b,c);

  
  last_edge = NULL;

  ch_edge* T[3];

  T[0] = new ch_edge(a,b);
  T[1] = new ch_edge(b,c);
  T[2] = new ch_edge(c,a);

  int i;
  for(i = 0; i < 2; i++)  T[i]->succ = T[i+1];
  T[2]->succ = T[0];

  for(i = 1; i < 3; i++)  T[i]->pred = T[i-1];
  T[0]->pred = T[2];

  forall(p,L)
    {   
      w << p;
      int i = 0;
      while (i < 3 && !right_turn(T[i]->source,T[i]->target,p) ) {
       w.draw_segment(SEGMENT(T[i]->source,T[i]->target),pink);
       if (bval) w.read_mouse(); else leda_wait(0.6);
       w.draw_segment(SEGMENT(T[i]->source,T[i]->target),black);
       i++;
      }
      if (i == 3) 
      { // p inside initial triangle
        continue; 
      }

      ch_edge* e = T[i];

      while (! e->outside)
      { ch_edge* r0 = e->pred;
        w.draw_segment(SEGMENT(r0->source,r0->target),pink);
	if (bval) w.read_mouse(); else leda_wait(0.6);
	w.draw_segment(SEGMENT(r0->source,r0->target),black);
        if ( right_turn(r0->source,r0->target,p) ) e = r0;
        else { ch_edge* r1 = e->succ;
              if ( right_turn(r1->source,r1->target,p) ) e = r1;
              else { e = nil; break; }
            }
      }

      if (e == nil) continue;  // p inside current hull
      
      window_output(w,p,e,NULL,NULL);

      
      // compute "upper" tangent (p,high->source)

      ch_edge* high = e->succ;
      while (orientation(high->source,high->target,p) <= 0) 
        high = high->succ;

      // compute "lower" tangent (p,low->target)

      ch_edge* low = e->pred;
      while (orientation(low->source,low->target,p) <= 0) 
        low = low->pred;
	
      window_output(w,p,e,low,high);

      e = low->succ;  // e = successor of low edge

      // add new tangents between low and high

      ch_edge* e_l = new ch_edge(low->target,p);
      ch_edge* e_h = new ch_edge(p,high->source);

      e_h->succ = high;
      e_l->pred = low;
      high->pred = e_l->succ = e_h;
      low->succ  = e_h->pred = e_l;

      // mark edges between low and high as "inside" 
      // and define refinements

      while (e != high)
      { ch_edge* q = e->succ;
        e->pred = e_l;
        e->succ = e_h;
        e->outside = false;
        e = q;
      }

 }
  
  ch_edge* l_edge = last_edge;

  CH.append(l_edge->source);
  for(ch_edge* e = l_edge->succ; e != l_edge; e = e->succ) 
     CH.append(e->source);

  // clean up 

  while (l_edge)
  { ch_edge* e = l_edge;
    l_edge = l_edge->link;
    delete e;
  }

  return CH;
}


class chull_update : public geowin_update<list<POINT>, list<polygon> >
{
public:
 void update(const list<POINT>& L, list<polygon>& P)
 {
   P.clear();
   list<POINT> ch = GW_CONVEX_HULL_IC(L);
   if( ch.length() > 2 ) P.append(polygon(ch));   
 }
};


int main()
{
  GeoWin gw("Incremental Construction of the Convex hull");
  list<POINT> LP;
 
  geo_scene sc1 = geowin_new_scene(gw, LP);
  
  chull_update chull;
  geo_scene sc2 = geowin_new_scene(gw, chull, sc1, "Convex hull");
  gw.set_color(sc2,blue2);
  gw.set_line_width(sc2,2);
  
  gw.set_all_visible(true);
  
  gw.init_menu();
  gw.get_window().bool_item(" Mouse input in animation:",bval);
  
  gw.edit(sc1);
  
  return 0;
}