contrib/gel/vtol/vtol_cycle_processor.h Source File

Go to the documentation of this file.
00001 #ifndef vtol_cycle_processor_h_
00002 #define vtol_cycle_processor_h_
00003 
00004 //:
00005 // \file
00006 // \brief A class for tracing boundaries and forming nested one_cycles.
00007 //
00008 // The input is a set of vtol_edge(s) which may or may not
00009 // define one or more closed paths, or cycles. The output is a set of
00010 // vtol_one_chain(s) which define a nested set of cycles.  That is, there is
00011 // an outer, bounding, cycle and zero or more interior hole boundaries.
00012 // The algorithm requires a tolerance which is used in the process of
00013 // deciding if one boundary is enclosed by another.
00014 //
00015 // \author
00016 //          J.L. Mundy August 13, 2000
00017 //          GE Corporate Research and Development
00018 //
00019 //-----------------------------------------------------------------------------
00020 
00021 #include <vcl_vector.h>
00022 #include <vtol/vtol_edge_sptr.h>
00023 #include <vtol/vtol_edge_2d_sptr.h>
00024 #include <vtol/vtol_one_chain_sptr.h>
00025 #include <vtol/vtol_vertex_sptr.h>
00026 class vtol_edge;
00027 
00028 class vtol_cycle_processor
00029 {
00030  public:
00031   vtol_cycle_processor(vcl_vector<vtol_edge_2d_sptr>& edges,
00032                        bool debug1=false, bool debug_2=false);
00033   vtol_cycle_processor(vcl_vector<vtol_edge*>& edges,
00034                        bool debug1=false, bool debug_2=false);
00035   ~vtol_cycle_processor() {}
00036 
00037   // PUBLIC INTERFACE----------------------------------------------------------
00038   bool nested_one_cycles(vcl_vector<vtol_one_chain_sptr>& one_chains,
00039                          const float& tolerance = 1e-03);
00040   //:
00041   // set operations on edges
00042   //
00043   static bool intersect_edges(vcl_vector<vtol_edge_sptr>& s1,
00044                               vcl_vector<vtol_edge_sptr>& s2,
00045                               vcl_vector<vtol_edge_sptr>& s1_and_s2);
00046   static bool difference_edges(vcl_vector<vtol_edge_sptr>& s1,
00047                                vcl_vector<vtol_edge_sptr>& s2,
00048                                vcl_vector<vtol_edge_sptr>& s1_minus_s2);
00049 
00050   //: topology repair methods useful in forming cycles.
00051   static bool corrupt_boundary(vcl_vector<vtol_edge_2d_sptr>& edges,
00052                                vcl_vector<vtol_vertex_sptr>& bad_verts);
00053 
00054   static bool connect_paths(vcl_vector<vtol_edge_2d_sptr>& edges,
00055                             vcl_vector<vtol_vertex_sptr>& bad_verts);
00056 
00057   static double angle_between_edges(vtol_edge_2d_sptr e0, vtol_edge_2d_sptr e1,
00058                                     vtol_vertex_sptr v);
00059 
00060  protected:
00061   //internal utilities
00062   void print_edge(vtol_edge_2d_sptr& e);
00063   void set_bridge_vars();
00064   void init(vcl_vector<vtol_edge_2d_sptr>& edges);
00065   vtol_edge_2d_sptr search_for_next_edge(vcl_vector<vtol_edge_2d_sptr>& edges_at_last);
00066   bool assignable(vtol_edge_2d_sptr edg, vtol_vertex_sptr last);
00067   void assign_initial_edge(vtol_edge_2d_sptr& e, vtol_vertex_sptr& first,
00068                            vtol_vertex_sptr& last);
00069   void assign_ends(vtol_edge_2d_sptr edg, vtol_vertex_sptr& last);
00070   void add_edge_to_path();
00071   bool classify_path(vcl_vector<vtol_edge_2d_sptr>& path_edges, vtol_one_chain_sptr& chain);
00072   void compute_cycles();
00073   void sort_one_cycles();
00074   void process();
00075   //members
00076   bool debug1_;
00077   bool debug2_;
00078   bool valid_;
00079   float tolerance_;
00080   bool cycle_;
00081   bool found_next_edge_;
00082   vtol_vertex_sptr first_;
00083   vtol_vertex_sptr last_;
00084   vtol_edge_2d_sptr l_;
00085   vtol_edge_2d_sptr next_edge_;
00086   vcl_vector<vtol_edge_2d_sptr> edges_;
00087   vcl_vector<vtol_edge_2d_sptr> e_stack_;
00088   vcl_vector<vtol_vertex_sptr> v_stack_;
00089   vcl_vector<vtol_one_chain_sptr> chains_;
00090   vcl_vector<vtol_one_chain_sptr> nested_one_cycles_;
00091 };
00092 
00093 #endif // vtol_cycle_processor_h_