1 // This is core/vgl/vgl_polygon.h 2 #ifndef vgl_polygon_h_ 3 #define vgl_polygon_h_ 4 //: 5 // \file 6 // \author awf@robots.ox.ac.uk 7 // \date 02 Apr 2000 8 // 9 // \verbatim 10 // Modifications 11 // Binary IO added and documentation tidied up NPC, 20/03/01 12 // Feb.2002 - Peter Vanroose - brief doxygen comment placed on single line 13 // Nov.2003 - Peter Vanroose - made vgl_polygon a templated class and added lost of documentation 14 // Nov.2003 - Peter Vanroose - added constructor (to replace new_polygon from test_driver) 15 // May.2009 - Matt Leotta - added a function to find self-intersections 16 // \endverbatim 17 18 #include <iosfwd> 19 #include <utility> 20 #include <vector> 21 #ifdef _MSC_VER 22 # include <vcl_msvc_warnings.h> 23 #endif 24 #include "vgl_point_2d.h" // needed for std::vector instantiations 25 26 //: Store a polygon. 27 // May have holes or multiple sections. The polygon is stored as a list 28 // of "sheets", each sheet is a list of 2d points. 29 // Iterate through all points using 30 // 31 // for (unsigned int s = 0; s < polygon.num_sheets(); ++s) 32 // for (unsigned int p = 0; p < polygon[s].size(); ++p) 33 // do_something(polygon[s][p].x(), polygon[s][p].y()); 34 // 35 // Note: area is not defined on the polygon class to keep a clean interface 36 // see vgl_area<T> 37 template <class T> 38 class vgl_polygon 39 { 40 public: 41 typedef vgl_point_2d<T> point_t; 42 43 typedef std::vector<point_t> sheet_t; 44 45 // Constructors/Destructor--------------------------------------------------- 46 47 //: Default constructor - constructs an empty polygon with no sheets 48 vgl_polygon() = default; 49 50 //: Construct an empty polygon, setting the number of (empty) sheets vgl_polygon(unsigned int nr_sheets)51 explicit vgl_polygon(unsigned int nr_sheets) : sheets_(nr_sheets) {} 52 53 //: Construct a single-sheet polygon from a list of n points. 54 // More sheets can be added later with the add_contour method. 55 vgl_polygon(point_t const p[], int n); 56 57 //: Construct a single-sheet polygon from a list of n points. 58 // More sheets can be added later with the add_contour method. 59 vgl_polygon(T const* x, T const* y, int n); 60 61 //: Construct a single-sheet polygon from a list of n points, given in (x,y) pairs. 62 // The x_y array should thus be of size 2*n ! 63 // More sheets can be added later with the add_contour method. 64 vgl_polygon(T const x_y[], int n); 65 66 //: Construct a single-sheet polygon from a sheet, i.e., a vector of 2D points. 67 // Note: n_sheets is only there to distinguish this from the next constructor for VC6 68 // which seems to have a problem. sheets_(n_sheets,points)69 explicit vgl_polygon(sheet_t const& points, unsigned n_sheets=1) : sheets_(n_sheets,points) {} 70 71 //: Construct by specifying all of its sheets vgl_polygon(std::vector<sheet_t> sheets)72 explicit vgl_polygon(std::vector<sheet_t> sheets) : sheets_(std::move(sheets)) {} 73 74 // Copy constructor vgl_polygon(vgl_polygon const & a)75 vgl_polygon(vgl_polygon const& a) : sheets_(a.sheets_) {} 76 77 // Destructor 78 ~vgl_polygon() = default; 79 80 //: Returns true if \a p(x,y) is inside the polygon, else false contains(point_t const & p)81 bool contains(point_t const& p) const { return contains(p.x(),p.y()); } 82 83 bool contains(T x, T y) const; 84 85 // creation 86 87 //: Add a single sheet to this polygon, specified by the given list of n points. 88 // This increments the number of sheets by one. 89 void add_contour(point_t const p[], int n); 90 91 //: Add a single sheet to this polygon, specified by the given list of n points. 92 // This increments the number of sheets by one. 93 void add_contour(T const* x, T const* y, int n); 94 95 //: Add a single sheet to this polygon, specified by the given list of n (x,y) pairs. 96 // The x_y array should thus be of size 2*n ! 97 // This increments the number of sheets by one. 98 void add_contour(T const x_y[], int n); 99 100 //: Set the number of sheets to zero, so the polygon becomes empty clear()101 void clear() { sheets_.resize(0); } 102 103 //: Add a new (empty) sheet to the polygon. 104 // This increments the number of sheets by one. new_sheet()105 void new_sheet() { sheets_.push_back(sheet_t()); } 106 107 //: Add a new point to the last sheet 108 void push_back(T x, T y); 109 110 //: Add a new point to the last sheet 111 void push_back(point_t const&); 112 113 //: Add a pre-existing sheet to the polygon push_back(sheet_t const & s)114 void push_back(sheet_t const& s) { sheets_.push_back(s); } 115 num_sheets()116 inline unsigned int num_sheets() const { return (unsigned int)(sheets_.size()); } 117 num_vertices()118 inline unsigned int num_vertices() const { 119 unsigned int c=0; 120 for (unsigned int i=0;i<num_sheets();++i) c += (unsigned int)(sheets_[i].size()); 121 return c; 122 } 123 //: Get the ith sheet 124 inline sheet_t& operator[](int i) { return sheets_[i]; } 125 126 //: Get the ith sheet 127 inline sheet_t const& operator[](int i) const { return sheets_[i]; } 128 129 //: Pretty print 130 std::ostream& print(std::ostream&) const; 131 132 //: read this polygon from ascii stream 133 std::istream& read(std::istream&); 134 protected: 135 136 // Data Members-------------------------------------------------------------- 137 std::vector<sheet_t> sheets_; 138 }; 139 140 //: A commonly required (single-sheet) polygon representation. 141 template <class T> 142 struct vgl_polygon_sheet_as_array 143 { 144 int n; 145 T* x; 146 T* y; 147 148 //: Automatic constructor from a single-sheet polygon 149 vgl_polygon_sheet_as_array(vgl_polygon<T> const& p); 150 151 //: Automatic constructor from a polygon sheet 152 vgl_polygon_sheet_as_array(typename vgl_polygon<T>::sheet_t const& p); 153 154 //: Destructor 155 ~vgl_polygon_sheet_as_array(); 156 }; 157 158 //: Compute all self-intersections between all edges on all sheets. 159 // \returns three arrays \a e1, \a e2, and \a ip of equal size. 160 // Corresponding elements from these arrays describe an intersection. 161 // e1[k].first is the sheet index containing edge (e1[k].second, e1[k].second+1) 162 // involved in the k-th intersection. Similarly, e2[k] indexes the other 163 // edge involved in the k-th intersection. The corresponding intersection 164 // point is returned in ip[k]. 165 template <class T> 166 void vgl_selfintersections(vgl_polygon<T> const& p, 167 std::vector<std::pair<unsigned,unsigned> >& e1, 168 std::vector<std::pair<unsigned,unsigned> >& e2, 169 std::vector<vgl_point_2d<T> >& ip); 170 171 // turn the first sheet into counterclockwise polygon 172 template <class T> 173 vgl_polygon<T> vgl_reorient_polygon(vgl_polygon<T> const &p); 174 175 template <class T> 176 bool vgl_polygon_sheet_is_counter_clockwise(std::vector<vgl_point_2d<T> > verts); 177 178 179 // \relatesalso vgl_polygon 180 template <class T> 181 std::ostream& operator<< (std::ostream& os, vgl_polygon<T> const& p) { return p.print(os); } 182 183 template <class T> 184 std::istream& operator>> (std::istream& is, vgl_polygon<T>& p) { return p.read(is); } 185 186 #define VGL_POLYGON_INSTANTIATE(T) extern "please include vgl/vgl_polygon.hxx instead" 187 188 #endif // vgl_polygon_h_ 189