JeVoisBase  1.3
JeVois Smart Embedded Machine Vision Toolkit Base Modules
Share this page:
Point2D.H
Go to the documentation of this file.
1 // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2 //
3 // JeVois Smart Embedded Machine Vision Toolkit - Copyright (C) 2016 by Laurent Itti, the University of Southern
4 // California (USC), and iLab at USC. See http://iLab.usc.edu and http://jevois.org for information about this project.
5 //
6 // This file is part of the JeVois Smart Embedded Machine Vision Toolkit. This program is free software; you can
7 // redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software
8 // Foundation, version 2. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
9 // without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
10 // License for more details. You should have received a copy of the GNU General Public License along with this program;
11 // if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
12 //
13 // Contact information: Laurent Itti - 3641 Watt Way, HNB-07A - Los Angeles, CA 90089-2520 - USA.
14 // Tel: +1 213 740 3527 - itti@pollux.usc.edu - http://iLab.usc.edu - http://jevois.org
15 // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
16 /*! \file */
17 
18 // This code adapted from:
19 
20 // //////////////////////////////////////////////////////////////////// //
21 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2001 by the //
22 // University of Southern California (USC) and the iLab at USC. //
23 // See http://iLab.usc.edu for information about this project. //
24 // //////////////////////////////////////////////////////////////////// //
25 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
26 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
27 // in Visual Environments, and Applications'' by Christof Koch and //
28 // Laurent Itti, California Institute of Technology, 2001 (patent //
29 // pending; application number 09/912,225 filed July 23, 2001; see //
30 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status). //
31 // //////////////////////////////////////////////////////////////////// //
32 // This file is part of the iLab Neuromorphic Vision C++ Toolkit. //
33 // //
34 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can //
35 // redistribute it and/or modify it under the terms of the GNU General //
36 // Public License as published by the Free Software Foundation; either //
37 // version 2 of the License, or (at your option) any later version. //
38 // //
39 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope //
40 // that it will be useful, but WITHOUT ANY WARRANTY; without even the //
41 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR //
42 // PURPOSE. See the GNU General Public License for more details. //
43 // //
44 // You should have received a copy of the GNU General Public License //
45 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write //
46 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, //
47 // Boston, MA 02111-1307 USA. //
48 // //////////////////////////////////////////////////////////////////// //
49 //
50 // Primary maintainer for this file: Laurent Itti <itti@usc.edu>
51 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/Image/Point2D.H $
52 // $Id: Point2D.H 14734 2011-04-14 18:59:24Z lior $
53 //
54 
55 #pragma once
56 
59 #include <cmath>
60 #include <string> // for string conversions
61 #include <vector>
62 
63 //! This is a basic class to encode 2D integer coordinates
64 /*! This is a completely public class whose goal is just to provide a shorthand notation for 2D integer coordinates. */
65 template <class T>
66 class Point2D
67 {
68 public:
69  //! The default constructor initializes the coordinates to (0,0)
70  inline Point2D();
71 
72  //! Initialize the Point2D from horizontal & vertical coordinates
73  inline Point2D(const T ii, const T jj);
74 
75  //! Explicit conversion from type T to another type U
76  /*! Note that this simply uses clamped_convert, so it will clamp
77  coordinates to the available range of T, and may round down. */
78  template <class U>
79  explicit inline Point2D(const Point2D<U>& a);
80 
81  //! += operator
82  inline Point2D<T>& operator+=(const Point2D<T> &p);
83  //! -= operator
84  inline Point2D<T>& operator-=(const Point2D<T> &p);
85  //! *= operator
86  inline Point2D<T>& operator*=(const Point2D<T> &p);
87  //! /= operator
88  inline Point2D<T>& operator/=(const Point2D<T> &p);
89 
90  //! + operator
91  template <class U>
93  operator+(const Point2D<U> &p) const;
94  //! - operator
95  template <class U>
97  operator-(const Point2D<U> &p) const;
98  //! * operator
99  template <class U>
101  operator*(const Point2D<U> &p) const;
102  //! / operator
103  template <class U>
105  operator/(const Point2D<U> &p) const;
106 
107  //! += operator
108  inline Point2D<T>& operator+=(const T val);
109  //! -= operator
110  inline Point2D<T>& operator-=(const T val);
111  //! *= operator
112  inline Point2D<T>& operator*=(const T val);
113  //! /= operator
114  inline Point2D<T>& operator/=(const T val);
115 
116  //! + operator
117  template <class U>
118  inline Point2D<typename promote_trait<T,U>::TP> operator+(const U val) const;
119 
120  //! - operator
121  template <class U>
122  inline Point2D<typename promote_trait<T,U>::TP> operator-(const U val) const;
123 
124  //! * operator
125  template <class U>
126  inline Point2D<typename promote_trait<T,U>::TP> operator*(const U val) const;
127 
128  //! / operator
129  template <class U>
130  inline Point2D<typename promote_trait<T,U>::TP> operator/(const U val) const;
131 
132  //! test whether i and j are both positive
133  inline bool isValid() const;
134 
135  //! the square of the euclidean distance
136  inline typename promote_trait<T,float>::TP
137  squdist(const Point2D<T>& p) const;
138 
139  //! the euclidean distance from p
140  inline typename promote_trait<T,float>::TP
141  distance(const Point2D<T>& p) const;
142 
143  //! the Magnitude
144  inline typename promote_trait<T,float>::TP
145  magnitude() const;
146 
147  //! the euclidean distance from line pq
148  inline typename promote_trait<T,float>::TP
149  distanceToLine(const Point2D<T>& p, const Point2D<T>& q,
150  const bool getsigned = false) const;
151 
152  //! the euclidean distance from segment pq
153  inline typename promote_trait<T,float>::TP
154  distanceToSegment(const Point2D<T>& p, const Point2D<T>& q) const;
155 
156  //! 2D coordinates
157  T i, j;
158 };
159 
160 
161 //! == operator
162 template <class T, class U>
163 inline bool operator==(const Point2D<T>& p1, const Point2D<U>& p2);
164 
165 //! != operator
166 template <class T, class U>
167 inline bool operator!=(const Point2D<T>& p1, const Point2D<U>& p2);
168 
169 //! > operator
170 template <class T, class U>
171 inline bool operator>(const Point2D<T>& p1, const Point2D<U>& p2);
172 
173 //! < operator
174 template <class T, class U>
175 inline bool operator<(const Point2D<T>& p1, const Point2D<U>& p2);
176 
177 
178 //! Is a point inside a polygon?
179 template <class T>
180 inline bool pnpoly(const std::vector<Point2D<T> > &polygon,
181  const Point2D<T>& p);
182 
183 //! Where is the center of mass of a polygon?
184 template <class T>
185 inline Point2D<T> centroid(const std::vector<Point2D<T> > &polygon);
186 
187 //! What is the area of a polygon?
188 template <class T>
189 inline double area(const std::vector<Point2D<T> > &polygon,
190  const bool getsigned = false);
191 
192 //! What is the measure (in radians, signed -pi to pi) of angle BAC?
193 template <class T>
194 inline double angleMeasure(const Point2D<T> & A,
195  const Point2D<T> & B,
196  const Point2D<T> & C);
197 
198 //! determine if a point P is inside a triangle with vertices A,B,C
199 template <class T>
200 inline bool pnTriangle(const Point2D<T>& A,
201  const Point2D<T>& B,
202  const Point2D<T>& C,
203  const Point2D<T>& P);
204 
205 
206 // ######################################################################
207 template <class T>
209 { i = 0; j = 0; }
210 
211 // ######################################################################
212 template <class T>
213 inline Point2D<T>::Point2D(const T ii, const T jj)
214 { i = ii; j = jj; }
215 
216 // #######################################################################
217 template <class T>
218 template <class U>
220  : i(clamped_convert<T>(a.i)), j(clamped_convert<T>(a.j))
221 { }
222 
223 // ######################################################################
224 template <class T>
226 { i += p.i; j += p.j; return *this; }
227 
228 // ######################################################################
229 template <class T>
231 { i -= p.i; j -= p.j; return *this; }
232 
233 // ######################################################################
234 template <class T>
236 { i *= p.i; j *= p.j; return *this; }
237 
238 // ######################################################################
239 template <class T>
241 { i /= p.i; j /= p.j; return *this; }
242 
243 // ######################################################################
244 template <class T>
245 template <class U>
248 { return Point2D<typename promote_trait<T,U>::TP>(i + p.i, j + p.j); }
249 
250 // ######################################################################
251 template <class T>
252 template <class U>
255 { return Point2D<typename promote_trait<T,U>::TP>(i - p.i, j - p.j); }
256 
257 // ######################################################################
258 template <class T>
259 template <class U>
262 { return Point2D<typename promote_trait<T,U>::TP>(i * p.i, j * p.j); }
263 
264 // ######################################################################
265 template <class T>
266 template <class U>
269 { return Point2D<typename promote_trait<T,U>::TP>(i / p.i, j / p.j); }
270 
271 // ######################################################################
272 template <class T>
273 inline Point2D<T>& Point2D<T>::operator+=(const T val)
274 { i += val; j += val; return *this; }
275 
276 // ######################################################################
277 template <class T>
278 inline Point2D<T>& Point2D<T>::operator-=(const T val)
279 { i -= val; j -= val; return *this; }
280 
281 // ######################################################################
282 template <class T>
283 inline Point2D<T>& Point2D<T>::operator*=(const T val)
284 { i *= val; j *= val; return *this; }
285 
286 // ######################################################################
287 template <class T>
288 inline Point2D<T>& Point2D<T>::operator/=(const T val)
289 { i /= val; j /= val; return *this; }
290 
291 // ######################################################################
292 template <class T>
293 template <class U>
295 Point2D<T>::operator+(const U val) const
296 { return Point2D<typename promote_trait<T,U>::TP>(this->i+val, this->j+val); }
297 
298 // ######################################################################
299 template <class T>
300 template <class U>
302 Point2D<T>::operator-(const U val) const
303 { return Point2D<typename promote_trait<T,U>::TP>(this->i-val, this->j-val); }
304 
305 // ######################################################################
306 template <class T>
307 template <class U>
309 Point2D<T>::operator*(const U val) const
310 { return Point2D<typename promote_trait<T,U>::TP>(this->i*val, this->j*val); }
311 
312 // ######################################################################
313 template <class T>
314 template <class U>
316 Point2D<T>::operator/(const U val) const
317 { return Point2D<typename promote_trait<T,U>::TP>(this->i/val, this->j/val); }
318 
319 // ######################################################################
320 template <class T, class U>
321 inline bool operator==(const Point2D<T>& p1, const Point2D<U>& p2)
322 { return p1.i == p2.i && p1.j == p2.j; }
323 
324 // ######################################################################
325 template <class T, class U>
326 inline bool operator!=(const Point2D<T>& p1, const Point2D<U>& p2)
327 { return p1.i != p2.i || p1.j != p2.j; }
328 
329 // ######################################################################
330 template <class T, class U>
331 inline bool operator>(const Point2D<T>& p1, const Point2D<U>& p2)
332 { return p1.i > p2.i && p1.j > p2.j; }
333 
334 // ######################################################################
335 template <class T, class U>
336 inline bool operator<(const Point2D<T>& p1, const Point2D<U>& p2)
337 { return p1.i < p2.i && p1.j < p2.j; }
338 
339 // ######################################################################
340 template <class T>
341 inline bool Point2D<T>::isValid() const
342 { return ((i >= 0) && (j >= 0)); }
343 
344 // ######################################################################
345 template <class T>
346 inline typename promote_trait<T,float>::TP
348 {
349  typedef typename promote_trait<T,float>::TP TF;
350  TF d1 = p.i - i, d2 = p.j - j;
351  return (d1 * d1 + d2 * d2);
352 }
353 
354 // ######################################################################
355 template <class T>
356 inline typename promote_trait<T,float>::TP
358 { return sqrt(squdist(p)); }
359 
360 // ######################################################################
361 template <class T>
362 inline typename promote_trait<T,float>::TP
364 { return sqrt((i*i) + (j*j)); }
365 
366 // ######################################################################
367 template <class T>
368 inline typename promote_trait<T,float>::TP
370  const bool getsigned) const
371 {
372  // standard geometry
373  typedef typename promote_trait<T,float>::TP TF;
374  TF a = q.j - p.j, b = q.i - p.i, c = q.i * p.j - q.j * p.i;
375  if (getsigned) return (a*i-b*j+c)/sqrt(a*a + b*b);
376  else return fabs(a*i-b*j+c)/sqrt(a*a + b*b);
377 }
378 
379 // ######################################################################
380 template <class T>
381 inline typename promote_trait<T,float>::TP
383 {
384  // test if point is "past" segment
385  Point2D<T> V0 = q-p, V1 = (*this)-q, V2 = (*this)-p; //vectors
386  if (V0.i*V1.i + V0.j*V1.j>0) return distance(q); // is "past" q
387  if (V0.i*V2.i + V0.j*V2.j<0) return distance(p); // is "past" p
388  return distanceToLine(p,q);
389 }
390 
391 // ######################################################################
392 // Original algo by Randolph Franklin,
393 // http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/
394 template <class T>
395 inline bool pnpoly(const std::vector<Point2D<T> > &polygon,
396  const Point2D<T>& p)
397 {
398  bool c = false; const uint ps = polygon.size();
399  for (uint i = 0, j = ps-1; i < ps; j = i++)
400  if ((((polygon[i].j <= p.j) && (p.j < polygon[j].j)) ||
401  ((polygon[j].j <= p.j) && (p.j < polygon[i].j))) &&
402  (p.i < (polygon[j].i - polygon[i].i) *
403  (p.j - polygon[i].j) / (polygon[j].j - polygon[i].j)
404  + polygon[i].i))
405  c = !c;
406 
407  return c;
408 }
409 
410 // ######################################################################
411 template <class T>
412 inline Point2D<T> centroid(const std::vector<Point2D<T> > &polygon)
413 {
414  Point2D<T> CM(0,0);
415  const uint ps = polygon.size();
416  for (uint i = 0; i < ps; i++) CM += polygon[i];
417  return CM / ps;
418 }
419 
420 // ######################################################################
421 template <class T>
422 inline double area(const std::vector<Point2D<T> > &polygon, const bool getsigned)
423 {
424  double area = 0.0;
425  const uint ps = polygon.size();
426  for (uint i = 0, j = ps-1; i < ps; j = i++)
427  area += polygon[i].i*polygon[j].j - polygon[i].j*polygon[j].i;
428  if (getsigned) return (0.5 * area);
429  else return fabs(0.5 * area);
430 }
431 
432 // ######################################################################
433 template <class T>
434 inline double angleMeasure(const Point2D<T> & A,
435  const Point2D<T> & B,
436  const Point2D<T> & C)
437 {
438  const double eps = 0.00001;
439  double Sab = A.distance(B), Sac = A.distance(C), Sbc = B.distance(C);
440 
441  if (Sab * Sac * Sbc == 0 || fabs(Sab - Sac + Sbc) < eps
442  || fabs(- Sab + Sac + Sbc) < eps) return 0;
443  else if(fabs(Sab + Sac - Sbc) < eps) return 3.1415;
444 
445  int sgn = (A.i*(B.j-C.j) + B.i*(C.j-A.j) * C.i*(A.j-B.j)) < 0 ? 1 : -1;
446  return sgn * acos((Sac*Sac+Sab*Sab-Sbc*Sbc)/(2*Sab*Sac));
447 }
448 
449 // ######################################################################
450 template <class T>
451 inline bool pnTriangle(const Point2D<T>& A,
452  const Point2D<T>& B,
453  const Point2D<T>& C,
454  const Point2D<T>& P)
455 {
456 
457 
458  T ax = C.i - B.i; T ay = C.j - B.j;
459  T bx = A.i - C.i; T by = A.j - C.j;
460  T cx = B.i - A.i; T cy = B.j - A.j;
461  T apx= P.i - A.i; T apy= P.j - A.j;
462  T bpx= P.i - B.i; T bpy= P.j - B.j;
463  T cpx= P.i - C.i; T cpy= P.j - C.j;
464 
465  T aCROSSbp = ax*bpy - ay*bpx;
466  T cCROSSap = cx*apy - cy*apx;
467  T bCROSScp = bx*cpy - by*cpx;
468 
469  return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
470 }
promote_trait< T, float >::TP squdist(const Point2D< T > &p) const
the square of the euclidean distance
Definition: Point2D.H:347
bool operator>(const Point2D< T > &p1, const Point2D< U > &p2)
operator
Definition: Point2D.H:331
bool operator==(const Point2D< T > &p1, const Point2D< U > &p2)
== operator
Definition: Point2D.H:321
unsigned int uint
Canonical unsigned int.
Definition: Types.H:134
dest_type clamped_convert(source_type source)
double angleMeasure(const Point2D< T > &A, const Point2D< T > &B, const Point2D< T > &C)
What is the measure (in radians, signed -pi to pi) of angle BAC?
Definition: Point2D.H:434
T i
2D coordinates
Definition: Point2D.H:157
Point2D< T > & operator-=(const Point2D< T > &p)
-= operator
Definition: Point2D.H:230
Point2D< T > centroid(const std::vector< Point2D< T > > &polygon)
Where is the center of mass of a polygon?
Definition: Point2D.H:412
bool pnTriangle(const Point2D< T > &A, const Point2D< T > &B, const Point2D< T > &C, const Point2D< T > &P)
determine if a point P is inside a triangle with vertices A,B,C
Definition: Point2D.H:451
bool operator!=(const Point2D< T > &p1, const Point2D< U > &p2)
!= operator
Definition: Point2D.H:326
Point2D< T > & operator/=(const Point2D< T > &p)
/= operator
Definition: Point2D.H:240
Point2D< typename promote_trait< T, U >::TP > operator+(const Point2D< U > &p) const
Definition: Point2D.H:247
Point2D< T > & operator+=(const Point2D< T > &p)
+= operator
Definition: Point2D.H:225
double area(const std::vector< Point2D< T > > &polygon, const bool getsigned=false)
What is the area of a polygon?
Definition: Point2D.H:422
promote_trait< T, float >::TP distanceToLine(const Point2D< T > &p, const Point2D< T > &q, const bool getsigned=false) const
the euclidean distance from line pq
Definition: Point2D.H:369
bool isValid() const
test whether i and j are both positive
Definition: Point2D.H:341
Point2D< typename promote_trait< T, U >::TP > operator-(const Point2D< U > &p) const
Definition: Point2D.H:254
promote_trait< T, float >::TP distanceToSegment(const Point2D< T > &p, const Point2D< T > &q) const
the euclidean distance from segment pq
Definition: Point2D.H:382
promote_trait< T, float >::TP magnitude() const
the Magnitude
Definition: Point2D.H:363
promote_trait< T, float >::TP distance(const Point2D< T > &p) const
the euclidean distance from p
Definition: Point2D.H:357
bool pnpoly(const std::vector< Point2D< T > > &polygon, const Point2D< T > &p)
Is a point inside a polygon?
Definition: Point2D.H:395
Point2D< T > & operator*=(const Point2D< T > &p)
*= operator
Definition: Point2D.H:235
Point2D< typename promote_trait< T, U >::TP > operator/(const Point2D< U > &p) const
/ operator
Definition: Point2D.H:268
This is a basic class to encode 2D integer coordinates.
Definition: Point2D.H:66
Point2D< typename promote_trait< T, U >::TP > operator*(const Point2D< U > &p) const
Definition: Point2D.H:261
Point2D()
The default constructor initializes the coordinates to (0,0)
Definition: Point2D.H:208