polygon.cpp
Go to the documentation of this file.
1 // *****************************************************************************
2 //
3 // Copyright (c) 2014, Southwest Research Institute® (SwRI®)
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of Southwest Research Institute® (SwRI®) nor the
14 // names of its contributors may be used to endorse or promote products
15 // derived from this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
21 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 //
28 // *****************************************************************************
29 
31 
32 namespace swri_geometry_util
33 {
34  //Constructor - create and undefined polygon
36  this->_nvert = 0;
37  this->_shape.x = NULL;
38  this->_shape.y = NULL;
39  }
40 
41  //Constructor - create a duplicate polygon
42  Polygon::Polygon(const Polygon & other)
43  {
44  this->_shape.x = new double[other._nvert];
45  this->_shape.y = new double[other._nvert];
46  this->_nvert = other._nvert;
47 
48  for(int i=0; i<other._nvert; i++){
49  this->_shape.x[i] = other._shape.x[i];
50  this->_shape.y[i] = other._shape.y[i];
51  }
52  }
53 
54  //Operate overload for assign a polygon
56  {
57  if(this != &other) // protect against invalid self-assignment
58  {
59  if (this->_nvert > 0)
60  {
61  delete[] this->_shape.x;
62  this->_shape.x = NULL;
63  delete[] this->_shape.y;
64  this->_shape.y = NULL;
65  }
66  this->_shape.x = new double[other._nvert];
67  this->_shape.y = new double[other._nvert];
68  this->_nvert = other._nvert;
69 
70  for(int i=0; i<other._nvert; i++){
71  this->_shape.x[i] = other._shape.x[i];
72  this->_shape.y[i] = other._shape.y[i];
73  }
74  }
75  return *this;
76  }
77 
78  //Constructor - create a polygon using a list of vertices
79  //Assumptions - vertices are in CW order
80  Polygon::Polygon(double Xs[], double Ys[], int numVertx){
81 
82  this->_shape.x = new double[numVertx];
83  this->_shape.y = new double[numVertx];
84  this->_nvert = numVertx;
85 
86  for(int i=0;i<numVertx;i++)
87  {
88  this->_shape.x[i] = Xs[i];
89  this->_shape.y[i] = Ys[i];
90  }
91  }
92 
93  //Determine if a given vertex lies within this polygon
94  //Returns: True if "vertex" is within this polygon, False otherwise
96  {
97  int i, j, c = 0;
98  for (i = 0, j = _nvert-1; i < _nvert; j = i++)
99  {
100  if (((_shape.y[i]>vertex.y) != (_shape.y[j]>vertex.y)) && (vertex.x <
101  (_shape.x[j]-_shape.x[i]) * (vertex.y-_shape.y[i]) /
102  (_shape.y[j]-_shape.y[i]) + _shape.x[i]))
103  c = !c;
104  }
105  return c;
106  }
107 
108  //Determine if a given line segment intersects with or lies within this polygon
109  //Returns: True if line segment defined by "start" and "end" intersects or
110  // lies within this polygon, False otherwise
112  {
113  Vertex pStart,pEnd, intersect;
114 
115  //check if either end point is within the polygon
116  if (VertexInPolygon(start) || VertexInPolygon(end))
117  {
118  return true;
119  }
120 
121  //check for line intersection with the polygon
122  for(int i=0;i < _nvert;i++)
123  {
124  pStart.x = _shape.x[i];
125  pStart.y = _shape.y[i];
126  pEnd.x = _shape.x[(i+1)%_nvert];
127  pEnd.y = _shape.y[(i+1)%_nvert];
128 
129  intersect = FindLineIntersectLine(pStart,pEnd,start,end);
130  if(intersect.x != -999.0 && intersect.y != -999.0)//intersection found
131  {
132  return true;
133  }
134  }
135 
136  return false;
137  }
138 
139  //Private Function
140  //Determines if two line segments intersect
141  //Returns: True if line segments intersect, False otherwise
143  Vertex start2, Vertex end2)
144  {
145  Vertex result;
146  result.x = -999.0;
147  result.y = -999.0;
148 
149  double denom = ((end1.x - start1.x) * (end2.y - start2.y)) -
150  ((end1.y - start1.y) * (end2.x - start2.x));
151 
152  //no intersection (lines are parallel)
153  if (denom == 0)
154  return result;
155 
156  double numer = ((start1.y - start2.y) * (end2.x - start2.x)) -
157  ((start1.x - start2.x) * (end2.y - start2.y));
158 
159  double r = numer / denom;
160 
161  double numer2 = ((start1.y - start2.y) * (end1.x - start1.x)) -
162  ((start1.x - start2.x) * (end1.y - start1.y));
163 
164  double s = numer2 / denom;
165 
166  //no intersection
167  if ((r < 0 || r > 1) || (s < 0 || s > 1))
168  return result;
169 
170  // Find intersection point
171  result.x = start1.x + (r * (end1.x - start1.x));
172  result.y = start1.y + (r * (end1.y - start1.y));
173 
174  return result;
175  }
176 
177  //returns all x vertices for this polygon
179  {
180  return this->_shape.x;
181  }
182 
183  //returns all y vertices for this polygon
185  {
186  return this->_shape.y;
187  }
188 
189  //returns a specific x vertex
190  double Polygon::GetXVerticie(int num)
191  {
192  return this->_shape.x[num];
193  }
194 
195  //returns a specific y vertex
196  double Polygon::GetYVerticie(int num)
197  {
198  return this->_shape.y[num];
199  }
200 
202  {
203  return this->_nvert;
204  }
205 
206  //Destructor
208  if(_shape.x){
209  delete[] _shape.x;
210  _shape.x = NULL;
211  }
212  if(_shape.y){
213  delete[] _shape.y;
214  _shape.y = NULL;
215  }
216  }
217 } // end namespace swri_geometry_util
double GetXVerticie(int num)
Definition: polygon.cpp:190
XmlRpcServer s
bool VertexInPolygon(Vertex vertex)
Definition: polygon.cpp:95
double GetYVerticie(int num)
Definition: polygon.cpp:196
Polygon & operator=(const Polygon &other)
Definition: polygon.cpp:55
Vertex FindLineIntersectLine(Vertex start1, Vertex end1, Vertex start2, Vertex end2)
Definition: polygon.cpp:142
bool LineOverlapsPolygon(Vertex start, Vertex end)
Definition: polygon.cpp:111


swri_geometry_util
Author(s): Marc Alban
autogenerated on Tue Apr 6 2021 02:50:29