pinside.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2006-2017, Andrew W. Steiner
5 
6  This file is part of O2scl.
7 
8  O2scl is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version.
12 
13  O2scl is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with O2scl. If not, see <http://www.gnu.org/licenses/>.
20 
21  -------------------------------------------------------------------
22 */
23 #ifndef O2SCL_PINSIDE_H
24 #define O2SCL_PINSIDE_H
25 
26 /** \file pinside.h
27  \brief File defining \ref o2scl::pinside
28 */
29 
30 #include <boost/numeric/ublas/vector.hpp>
31 
32 #include <o2scl/test_mgr.h>
33 #include <o2scl/vector.h>
34 
35 #ifndef DOXYGEN_NO_O2NS
36 namespace o2scl {
37 #endif
38 
39  /** \brief Test line intersection and point inside polygon
40 
41  This is a fast and dirty implementation of the point inside
42  polygon test from Jerome L. Lewis, SIGSCE Bulletin, 34 (2002)
43  81.
44 
45  Note that an error in that article ("count-" should have been
46  "count--") has been corrected here.
47 
48  \future The inside() functions actually copy the points twice.
49  This can be made more efficient.
50 
51  \comment
52  See also
53  http://www.ecse.rpi.edu/Homepages/wrf/Research/
54  Short_Notes/pnpoly.html#Polyhedron
55  which suggests the following code
56  int pnpoly(int nvert, float *vertx, float *verty, float testx,
57  float testy) {
58  int i, j, c = 0;
59  for (i = 0, j = nvert-1; i < nvert; j = i++) {
60  if ( ((verty[i]>testy) != (verty[j]>testy)) &&
61  (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) /
62  (verty[j]-verty[i]) + vertx[i]) )
63  c = !c;
64  }
65  return c;
66  }
67  \endcomment
68 
69  */
70  class pinside {
71 
72  public:
73 
75 
76  protected:
77 
78  /// Internal point definition for \ref pinside
79  struct point {
80  double x;
81  double y;
82  };
83 
84  /// Internal line definition for \ref pinside
85  struct line {
86  point p1;
87  point p2;
88  };
89 
90  /// Test if line segments \c P and \c Q intersect
91  int intersect(line P, line Q);
92 
93  /// Test if point \c t is inside polygon \c p of size \c N
94  int inside(point t, point p[], int N);
95 
96  public:
97 
98  /** \brief Determine if two line segments intersect
99 
100  The function returns 1 if the line segment
101  determined by the endpoints \f$ (x_1,y_1) \f$
102  and \f$ (x_2,y_2) \f$ and the line segment
103  determined by the endpoints \f$ (x_3,y_3) \f$
104  and \f$ (x_4,y_4) \f$ intersect, and 0 otherwise.
105  */
106  int intersect(double x1, double y1, double x2, double y2,
107  double x3, double y3, double x4, double y4) {
108  line P={{x1,y1},{x2,y2}};
109  line Q={{x3,y3},{x4,y4}};
110  return intersect(P,Q);
111  }
112 
113  /** \brief Determine if point (x,y) is inside a polygon
114 
115  This returns 1 if the point (x,y) is inside the polygon
116  defined by \c xa and \c ya, and 0 otherwise.
117 
118  Note that if the point (x,y) is exactly on the polygon,
119  then the result of this function is not well-defined
120  and it will return either 0 or 1.
121  */
122  int inside(double x, double y, const ubvector &xa,
123  const ubvector &ya);
124 
125  /** \brief Determine if point (x,y) is inside a polygon
126 
127  This returns 1 if the point (x,y) is inside the polygon
128  defined by \c xa and \c ya, and 0 otherwise.
129 
130  The parameter \c n should be the number of polygon points
131  specified in vectors \c xa and \c ya.
132 
133  Note that if the point (x,y) is exactly on the polygon,
134  then the result of this function is not well-defined
135  and it will return either 0 or 1.
136  */
137  template<class vec_t>
138  int inside(double x, double y, size_t n, const vec_t &xa,
139  const vec_t &ya) {
140 
141  size_t ix;
142  point t, *p=new point[n+1];
143  t.x=x;
144  t.y=y;
145 
146  // We have to copy the vectors so we can rearrange them because
147  // they are const
148  ubvector xb(n), yb(n);
149  vector_copy(n,xa,xb);
150  vector_copy(n,ya,yb);
151 
152  // Ensure that (yb[0],ya[0]) is the point with the smallest x
153  // coordinate among all the points with the smallest y coordinate
154  double xmin=xb[0];
155  double ymin=yb[0];
156  ix=0;
157  for(size_t i=0;i<n;i++) {
158  if (yb[i]<ymin) {
159  ymin=yb[i];
160  ix=i;
161  }
162  }
163  for(size_t i=0;i<n;i++) {
164  if (yb[i]==ymin && xb[i]<xmin) {
165  xmin=xb[i];
166  ix=i;
167  }
168  }
169  vector_rotate<vec_t,double>(n,xb,ix);
170  vector_rotate<vec_t,double>(n,yb,ix);
171 
172  // Copy to p[]
173  for(size_t i=0;i<n;i++) {
174  p[i+1].x=xb[i];
175  p[i+1].y=yb[i];
176  }
177 
178  int ret=inside(t,p,n);
179  delete[] p;
180 
181  return ret;
182  }
183 
184  /// Perform some simple testing
185  int test(test_mgr &t);
186 
187  };
188 
189 #ifndef DOXYGEN_NO_O2NS
190 }
191 #endif
192 
193 #endif
The main O<span style=&#39;position: relative; top: 0.3em; font-size: 0.8em&#39;>2</span>scl O$_2$scl names...
Definition: anneal.h:42
Test line intersection and point inside polygon.
Definition: pinside.h:70
A class to manage testing and record success and failure.
Definition: test_mgr.h:46
int intersect(line P, line Q)
Test if line segments P and Q intersect.
void vector_copy(const vec_t &src, vec2_t &dest)
Simple vector copy.
Definition: vector.h:127
Internal line definition for pinside.
Definition: pinside.h:85
int inside(double x, double y, size_t n, const vec_t &xa, const vec_t &ya)
Determine if point (x,y) is inside a polygon.
Definition: pinside.h:138
static const double x3[11]
Definition: inte_qng_gsl.h:94
int inside(point t, point p[], int N)
Test if point t is inside polygon p of size N.
int intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
Determine if two line segments intersect.
Definition: pinside.h:106
static const double x4[22]
Definition: inte_qng_gsl.h:139
int test(test_mgr &t)
Perform some simple testing.
static const double x2[5]
Definition: inte_qng_gsl.h:66
Internal point definition for pinside.
Definition: pinside.h:79
static const double x1[5]
Definition: inte_qng_gsl.h:48

Documentation generated with Doxygen. Provided under the GNU Free Documentation License (see License Information).