geowin_conv_comp.c

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

#include <LEDA/geowin.h>
#include <LEDA/rat_geo_alg.h>
#include <LEDA/float_geo_alg.h>
#include <LEDA/stack.h>
#include <LEDA/map.h>

/*
typedef rat_point     POINT;
typedef rat_segment   SEGMENT;
typedef rat_polygon   POLYGON;
*/

typedef point     POINT;
typedef segment   SEGMENT;
typedef polygon   POLYGON;


void constr_poly(const list<POINT>& L, list<POLYGON>& P)
{ 
  P.clear();
  if (L.length() > 1) P.append(POLYGON(L,POLYGON::NO_CHECK)); 
}

void compute_convex_components(GRAPH<POINT,SEGMENT>& G, list<edge>& in)
{
  stack<edge> ST;
  edge e,rev;
  node nb1,nb2,nb3,na1,na2,na3;
  POINT b1,b2,b3,a1,a2,a3;
  
  // don't insert reversals in the stack
  map<edge,int> EM;
  forall(e,in) { 
    rev = G.reversal(e);
    if (! (EM.defined(rev))){
      ST.push(e);
      EM[e]=1;
    }
  }
  
  in.clear();
  
  while (! ST.empty()){
    e = ST.pop();
    // get the points for the convexity test ...
    rev = G.reversal(e);
    nb2 = G.source(e); na2 = G.target(e);
    na3 = G.target(G.face_cycle_succ(e)); nb3 = G.source(G.face_cycle_pred(e));
    nb1 = G.target(G.face_cycle_succ(rev)); na1 = G.source(G.face_cycle_pred(rev));
    a1 = G[na1]; a2 = G[na2]; a3 = G[na3];
    b1 = G[nb1]; b2 = G[nb2]; b3 = G[nb3];
    
    int o1 = orientation(a1,a2,b2), o2 = orientation(a1,a2,a3);
    
    if ((o2==0) || (o1==o2)){ // convexity ...
      o1 = orientation(b1,b2,a2); o2 = orientation(b1,b2,b3);
      
      if ((o2==0) || (o1==o2)){
        // convexity; we have to delete e and its reversal edge ...
	G.del_edge(e);
	G.del_edge(rev);
      }
      else { in.append(e); in.append(rev); }
    }
    else { in.append(e); in.append(rev); }
  }
}

void convex_components(const list<POLYGON>& L, list<SEGMENT>& S)
{ S.clear();
  POLYGON P;
  forall(P,L)
  { if (!P.is_simple()) continue;
    GRAPH<POINT,SEGMENT> G;
    list<edge> out,in,bound;
    TRIANGULATE_POLYGON(P.vertices(),G,in,out,bound);
    edge e;
    
    compute_convex_components(G, in);  
    
    forall(e,in) S.append(SEGMENT(G[source(e)],G[target(e)]));
  } 
}


int main()
{
  GeoWin GW("Convex components of polygons");
 
  // Inputscene
  list<POINT> L;
  geo_scene sc_input =  geowin_new_scene(GW,L); 
  GW.set_color(sc_input,black);
  GW.set_fill_color(sc_input,yellow);
  GW.set_point_style(sc_input,circle_point);
  
  geowin_update<list<POINT>,   list<POLYGON> > construct(constr_poly);
  geowin_update<list<POLYGON>, list<SEGMENT> > convcomp(convex_components);

  geo_scene sc_poly= geowin_new_scene(GW,construct, sc_input, "Polygon");
  GW.set_fill_color(sc_poly,blue2);
  GW.set_color(sc_poly,black); 
  GW.set_line_width(sc_poly,2); 
  GW.set_visible(sc_poly,true);

  geo_scene sc_cc = geowin_new_scene(GW,convcomp,sc_poly,"Convex components"); 
  GW.set_color(sc_cc,red);
  GW.set_line_width(sc_cc,2);
  GW.set_all_visible(true);
  
  GW.edit(sc_input);
  
  return 0;  
}