geowin_voro_seg.c

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

#include <LEDA/geowin.h>
#include <LEDA/plane_alg.h>
#include <LEDA/map.h>


#define SEGMENT rat_segment
#define POINT   rat_point
#define CIRCLE  rat_circle
#define RATIONAL


/*
#define SEGMENT segment
#define POINT   point
#define CIRCLE  circle
*/

typedef list<SEGMENT>           segment_list;
typedef GRAPH<CIRCLE,POINT>     voro_seg_graph;

int SAMPLE_NUMBER = 45;

void segment_points(list<point>& L, segment s, int n);
void rat_segment_points(list<rat_point>& L, rat_segment s, int n);

#if defined(RATIONAL)
void segment_points(list<rat_point>& L, rat_segment s, int n)
{
  L.clear();
  rat_segment_points(L,s,n);
}
#endif


void VORONOI_SEGMENTS(const list<SEGMENT>& LS, voro_seg_graph& VS)
{
  edge e;

  // get point samples ...
  list<POINT> LP;
  list<POINT> all;
  map<POINT,SEGMENT> MS;
  SEGMENT iter;
  POINT  piter;
  
  VS.clear();
  
  forall(iter,LS){
    segment_points(LP,iter,SAMPLE_NUMBER);
    forall(piter,LP){
      all.append(piter);
      MS[piter] = iter;
    }
  }
  
  GRAPH<CIRCLE,POINT> VD;
  VORONOI(all,VD);

  list<edge> remove;
  
  forall_edges(e,VD){
    POINT p1 = VD[e];
    POINT p2 = VD[VD.reversal(e)];
    
    //cout << MS[p1] << "     " << MS[p2] << "\n\n";
    
    if (identical(MS[p1],MS[p2])){
       //cout << "remove edge!\n";
       remove.append(e);
    }
    //else cout << "Don't remove edge!\n";
  }
  
  forall(e,remove) VD.del_edge(e);
  
  // remove nodes with outdegree 0
  node v;
  list<node> remove_node;
  
  forall_nodes(v,VD) { if (VD.outdeg(v) == 0) remove_node.append(v); }
  forall(v,remove_node) VD.del_node(v);
 
  VS=VD;
}


geowin_graph_update<segment_list, voro_seg_graph>  vseg(VORONOI_SEGMENTS);


int main()
{
  GeoWin GW("Approximated voronoi diagram of line segments");
  
  list<SEGMENT> Lseg;
  
  geo_scene segs = geowin_new_scene(GW,Lseg);
  
  geo_scene sc1 = geowin_new_scene(GW,vseg, segs, "VORONOI"); 
  GW.set_color(sc1,blue);

  GW.set_all_visible(true);

  GW.init_menu();
  GW.get_window().int_item(" Accuracy:",SAMPLE_NUMBER,5,200);
  GW.edit(segs);

  return 0;
}