All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Private Attributes | List of all members
Polygon2D Class Reference

#include <Polygon2D.h>

Public Member Functions

 Polygon2D ()
 
 Polygon2D (const std::vector< std::pair< float, float > > &points)
 
 Polygon2D (const Polygon2D &poly1, const Polygon2D &poly2)
 
unsigned int Size () const
 Create Intersection Polygon. More...
 
const std::pair< float, float > & Point (unsigned int p) const
 
std::pair< float, float > Project (const std::pair< float, float > &, float) const
 
float Area () const
 
float Perimeter () const
 
bool Overlap (float slope, const Polygon2D &poly2, const std::pair< float, float > &origin) const
 
bool PolyOverlap (const Polygon2D &poly2) const
 
bool PolyOverlapSegments (const Polygon2D &poly2) const
 
bool PointInside (const std::pair< float, float > &point) const
 
bool Contained (const Polygon2D &poly2) const
 
void UntanglePolygon ()
 check if poly2 is inside poly1 More...
 

Private Attributes

std::vector< std::pair< float,
float > > 
vertices
 

Detailed Description

Definition at line 32 of file Polygon2D.h.

Constructor & Destructor Documentation

Polygon2D::Polygon2D ( )
inline

Definition at line 39 of file Polygon2D.h.

39 { }
Polygon2D::Polygon2D ( const std::vector< std::pair< float, float > > &  points)
inline

Definition at line 40 of file Polygon2D.h.

40 { vertices = points; }
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
Polygon2D::Polygon2D ( const Polygon2D poly1,
const Polygon2D poly2 
)

Definition at line 52 of file Polygon2D.cxx.

53 {
54 
55  //figure out if the two polygons overlap at all
56  if ( !(poly1.PolyOverlap(poly2)) ){
57  std::vector< std::pair<float,float> > nullpoint;
58  vertices = nullpoint;
59  return;
60  }
61 
62  //The overlap polygon is made up by:
63  //1) all points of poly1 in poly2
64  //2) all points of poly2 in poly1
65  //3) all intersection points between segments
66 
67  //make a new set of points and add points
68  //as listed above, if found.
69  std::vector<std::pair<float,float> > IntersectionPoints;
70  //1)
71  for (unsigned int p1=0; p1 < poly1.Size(); p1++){
72  if ( poly2.PointInside( poly1.Point(p1) ) ) { IntersectionPoints.push_back( poly1.Point(p1) ); }
73  }
74  //2)
75  for (unsigned int p2=0; p2 < poly2.Size(); p2++){
76  if ( poly1.PointInside( poly2.Point(p2) ) ) { IntersectionPoints.push_back( poly2.Point(p2) ); }
77  }
78  //3)
79  //FIND SEGMENT INTERSECTIONS
80  for (unsigned int i=0; i < poly1.Size(); i++){
81  for (unsigned int j=0; j < poly2.Size(); j++){
82  if (SegmentOverlap( poly1.Point(i).first, poly1.Point(i).second,
83  poly1.Point(i+1).first, poly1.Point(i+1).second,
84  poly2.Point(j).first, poly2.Point(j).second,
85  poly2.Point(j+1).first, poly2.Point(j+1).second) )
86  //segments overlap...add intersection to list
87  IntersectionPoints.push_back( GetIntersection( poly1.Point(i).first, poly1.Point(i).second,
88  poly1.Point(i+1).first, poly1.Point(i+1).second,
89  poly2.Point(j).first, poly2.Point(j).second,
90  poly2.Point(j+1).first, poly2.Point(j+1).second) );
91  }//for all segments in poly2
92  }//for all segments in poly1
93 
94  vertices = IntersectionPoints;
95  return;
96 }
const std::pair< float, float > & Point(unsigned int p) const
Definition: Polygon2D.cxx:138
unsigned int Size() const
Create Intersection Polygon.
Definition: Polygon2D.h:42
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
std::pair< float, float > GetIntersection(double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy)
Definition: Polygon2D.cxx:31
bool SegmentOverlap(double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy)
Definition: Polygon2D.cxx:21
bool PointInside(const std::pair< float, float > &point) const
Definition: Polygon2D.cxx:252
bool PolyOverlap(const Polygon2D &poly2) const
Definition: Polygon2D.cxx:202
physics associatedGroupsWithLeft p1

Member Function Documentation

float Polygon2D::Area ( ) const

Definition at line 99 of file Polygon2D.cxx.

100 {
101  //how? here:
102  //http://www.mathsisfun.com/geometry/area-irregular-polygons.html
103  float area = 0;
104  for (unsigned int i=0; i<vertices.size(); i++){
105  if ( i < (vertices.size()-1) )
106  area += (((vertices.at(i)).second)+((vertices.at(i+1)).second))*(((vertices.at(i)).first)-((vertices.at(i+1)).first))*0.5;
107  if ( i == (vertices.size()-1) )
108  area += (((vertices.at(i)).second)+((vertices.at(0)).second))*(((vertices.at(i)).first)-((vertices.at(0)).first))*0.5;
109  }
110  if (area<0.0)
111  area = -area;
112  return area;
113 }
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
bool Polygon2D::Contained ( const Polygon2D poly2) const

Definition at line 274 of file Polygon2D.cxx.

275 {
276 
277  //loop over poly2 checking wehther
278  //points of poly2 all inside poly1
279  for (unsigned int i=0; i<poly2.Size(); i++){
280  if ( !(this->PointInside( poly2.Point(i)) ) )
281  return false;
282  }
283 
284  return true;
285 
286 }
const std::pair< float, float > & Point(unsigned int p) const
Definition: Polygon2D.cxx:138
unsigned int Size() const
Create Intersection Polygon.
Definition: Polygon2D.h:42
bool PointInside(const std::pair< float, float > &point) const
Definition: Polygon2D.cxx:252
bool Polygon2D::Overlap ( float  slope,
const Polygon2D poly2,
const std::pair< float, float > &  origin 
) const

Definition at line 183 of file Polygon2D.cxx.

186 {
187  //translate and rotate both polygons
188  float theta = tan(slope);
189  //here we translate origin, rotate and find x-coordinates and find range of projection on edge line
190  std::pair<float,float> range1 = this->Project(origin,theta);
191  std::pair<float,float> range2 = poly2.Project(origin,theta);
192  //std::cout << "range 1: " << range1.first << " " << range1.second << std::endl;
193  //std::cout << "range 2: " << range2.first << " " << range2.second << std::endl;
194  //if the two projections don't overlap --> no overlap!
195  if ( ( ((range1.first <= range2.second) and ( range1.first >= range2.first )) or ((range1.second <= range2.second) and ( range1.second >= range2.first )) ) or ( ((range2.first <= range1.second) and ( range2.first >= range1.first )) or ((range2.second <= range1.second) and ( range2.second >= range1.first )) ) )
196  return true; //yes...they overlap
197  else
198  return false; //no....they do not overlap
199 }
std::pair< float, float > Project(const std::pair< float, float > &, float) const
Definition: Polygon2D.cxx:156
return match has_match and(match.match_pdg==11 or match.match_pdg==-11)
constexpr Point origin()
Returns a origin position with a point of the specified type.
Definition: geo_vectors.h:227
float Polygon2D::Perimeter ( ) const

Definition at line 116 of file Polygon2D.cxx.

117 {
118 
119  float perimeter = 0.;
120 
121  for (unsigned int i=0; i<vertices.size(); i++){
122  if ( i < (vertices.size()-1) )
123  perimeter += ( (vertices.at(i).second-vertices.at(i+1).second)*
124  (vertices.at(i).second-vertices.at(i+1).second) +
125  (vertices.at(i).first-vertices.at(i+1).first)*
126  (vertices.at(i).first-vertices.at(i+1).first) );
127  if ( i == (vertices.size()-1) )
128  perimeter += ( (vertices.at(i).second-vertices.at(0).second)*
129  (vertices.at(i).second-vertices.at(0).second) +
130  (vertices.at(i).first-vertices.at(0).first)*
131  (vertices.at(i).first-vertices.at(0).first) );
132  }
133 
134  return sqrt(perimeter);
135 }
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
const std::pair< float, float > & Polygon2D::Point ( unsigned int  p) const

Definition at line 138 of file Polygon2D.cxx.

139 {
140  //This function returns the vertex under consideration
141  //as a std::pair<float,float> Returns vertex for argument
142  //from 0 to N-1. For input N = number of sides then
143  //the first vertex is returned
144  if (p<vertices.size())
145  return vertices.at(p);
146  else if (p==vertices.size())
147  return vertices.at(0);
148  else{
149  std::cout << "Out of bounds of Polygon!" <<std::endl;
150  return vertices.at(0);
151  }
152 
153 }
pdgs p
Definition: selectors.fcl:22
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
BEGIN_PROLOG could also be cout
bool Polygon2D::PointInside ( const std::pair< float, float > &  point) const

Definition at line 252 of file Polygon2D.cxx.

253 {
254 
255  //any ray originating at point will cross polygon
256  //even number of times if point outside
257  //odd number of times if point inside
258  int intersections = 0;
259  for (unsigned int i=0; i<this->Size(); i++){
260  if ( SegmentOverlap( this->Point(i).first, this->Point(i).second,
261  this->Point(i+1).first, this->Point(i+1).second,
262  10000.0, 10000.0,
263  point.first, point.second) )
264  intersections += 1;
265  }
266  if ( (intersections%2) == 0 )
267  return false;
268  else
269  return true;
270 
271 }
const std::pair< float, float > & Point(unsigned int p) const
Definition: Polygon2D.cxx:138
unsigned int Size() const
Create Intersection Polygon.
Definition: Polygon2D.h:42
bool SegmentOverlap(double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy)
Definition: Polygon2D.cxx:21
bool Polygon2D::PolyOverlap ( const Polygon2D poly2) const

Definition at line 202 of file Polygon2D.cxx.

203 {
204 
205  //start from first pair in vector then check all edges.
206  //edges are (0,1), (1,2), ..., (N,N-1) each pair a pair
207  //of vertexes
208  for (unsigned int i=0; i<this->Size(); i++){//loop over first polygon's vertices
209  //find projection line's slope
210  //line: y=ax+b --- slope is a variable
211  float slope;
212  slope = FindSlope( this->Point(i) , this->Point(i+1) );
213  //if there is even one no-overlap
214  //need to exit and return no overlap!
215  if (! (this->Overlap( slope, poly2, this->Point(i) )) )
216  return false;
217  }//loop over first polygon vertices
218 
219  //do the exact same thing but reversing polygon role
220  for (unsigned int i=0; i<poly2.Size(); i++){//loop over first polygon
221  float slope;
222  slope = FindSlope( poly2.Point(i) , poly2.Point(i+1) );
223  if (!(poly2.Overlap( slope, *this, poly2.Point(i) )) )
224  return false;
225  }//loop over second polygon vertices
226  return true;
227 }
const std::pair< float, float > & Point(unsigned int p) const
Definition: Polygon2D.cxx:138
unsigned int Size() const
Create Intersection Polygon.
Definition: Polygon2D.h:42
bool Overlap(float slope, const Polygon2D &poly2, const std::pair< float, float > &origin) const
Definition: Polygon2D.cxx:183
float FindSlope(const std::pair< float, float > &p1, const std::pair< float, float > &p2)
Definition: Polygon2D.cxx:7
bool Polygon2D::PolyOverlapSegments ( const Polygon2D poly2) const

Definition at line 230 of file Polygon2D.cxx.

231 {
232  //if contained in one another then they also overlap:
233  if ( (this->Contained(poly2)) or (poly2.Contained(*this)) ){
234  return true;
235  }
236  //loop over the two polygons checking wehther
237  //two segments ever intersect
238  for (unsigned int i=0; i<this->Size(); i++){
239  for (unsigned int j=0; j<poly2.Size(); j++){
240  if (SegmentOverlap( this->Point(i).first, this->Point(i).second,
241  this->Point(i+1).first, this->Point(i+1).second,
242  poly2.Point(j).first, poly2.Point(j).second,
243  poly2.Point(j+1).first, poly2.Point(j+1).second) ){
244  return true;
245  }
246  }
247  }
248  return false;
249 }
bool Contained(const Polygon2D &poly2) const
Definition: Polygon2D.cxx:274
const std::pair< float, float > & Point(unsigned int p) const
Definition: Polygon2D.cxx:138
unsigned int Size() const
Create Intersection Polygon.
Definition: Polygon2D.h:42
bool SegmentOverlap(double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy)
Definition: Polygon2D.cxx:21
std::pair< float, float > Polygon2D::Project ( const std::pair< float, float > &  p,
float  theta 
) const

Definition at line 156 of file Polygon2D.cxx.

158 {
159 
160  std::pair<float,float> range(10000,0);
161  std::pair<float,float> ptmp;
162 
163  for (unsigned int i=0; i<vertices.size(); i++){
164  //Translation
165  //translating each vertex so that origin is on first vertex on polygon's edge being considered
166  ptmp = std::make_pair( (vertices.at(i)).first - p.first , (vertices.at(i)).second - p.second );
167  //Rotation
168  //instead of rotating each (x,y) edge (slow) just find nex x-position which gives us information
169  //on the projection of that vertex on the line we are considering
170  // +x direction is from vertex in consideration (vertex 'i' in loop) to next vertex
171  //now find the x-coordinate of that vertex after it is rotated such that edge is now + x axis
172  float xnew = (ptmp.first)*cos(theta) + (ptmp.second)*sin(theta);
173  //finally calculate range of projection on x-axis: look at every x position and compare it to range
174  if ( xnew < range.first )
175  range.first = xnew;
176  if ( xnew > range.second )
177  range.second = xnew;
178  }
179  return range;
180 }
pdgs p
Definition: selectors.fcl:22
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
unsigned int Polygon2D::Size ( ) const
inline

Create Intersection Polygon.

Definition at line 42 of file Polygon2D.h.

42 { return vertices.size(); }
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
void Polygon2D::UntanglePolygon ( )

check if poly2 is inside poly1

Definition at line 289 of file Polygon2D.cxx.

290 {
291 
292  //loop over edges
293  for ( unsigned int i=0; i < vertices.size()-1; i++){
294  double Ax = vertices.at(i).first;
295  double Ay = vertices.at(i).second;
296  double Bx = vertices.at(i+1).first;
297  double By = vertices.at(i+1).second;
298  //loop over edges that have not been checked yet
299  for (unsigned int j=i+2; j < vertices.size()-1; j++){
300  //avoid consecutive segments
301  if ( vertices.at(i) == vertices.at(j+1) )
302  continue;
303  else{
304  double Cx = vertices.at(j).first;
305  double Cy = vertices.at(j).second;
306  double Dx = vertices.at(j+1).first;
307  double Dy = vertices.at(j+1).second;
308 
309  if ( SegmentOverlap( Ax, Ay, Bx, By, Cx, Cy, Dx, Dy ) ){
310  std::pair<float, float> tmp = vertices.at(i+1);
311  vertices.at(i+1) = vertices.at(j);
312  vertices.at(j) = tmp;
313  //swapped polygon, now do recursion to make sure
314  this->UntanglePolygon();
315  }//if crossing
316  }
317  }//second loop
318  }//first loop
319 
320 }
std::vector< std::pair< float, float > > vertices
Definition: Polygon2D.h:35
bool SegmentOverlap(double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy)
Definition: Polygon2D.cxx:21
void UntanglePolygon()
check if poly2 is inside poly1
Definition: Polygon2D.cxx:289

Member Data Documentation

std::vector< std::pair<float,float> > Polygon2D::vertices
private

Definition at line 35 of file Polygon2D.h.


The documentation for this class was generated from the following files: