KJB
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pixpath.h
Go to the documentation of this file.
1 
6 /*
7  * $Id: pixpath.h 18278 2014-11-25 01:42:10Z ksimek $
8  */
9 
10 #ifndef PIXPATH_H_UOFARIZONAVISION
11 #define PIXPATH_H_UOFARIZONAVISION 1
12 
13 #include <l/l_error.h>
14 #include <l/l_global.h>
15 #include <l_cpp/l_util.h>
16 #include <m_cpp/m_vector_d.h>
17 #include <i_cpp/i_pixel.h>
18 #include <qd_cpp/pixpoint.h>
19 
20 #include <limits>
21 #include <vector>
22 #include <string>
23 #include <sstream>
24 #include <map>
25 #include <algorithm>
26 
27 
28 namespace kjb
29 {
30 namespace qd
31 {
32 
33 
34 
35 
36 
117 class PixPath
118 {
123  typedef std::vector< PixPoint > VecPP;
124 
126  VecPP my_vpp;
127 
128 
129  typedef std::map< PixPoint, unsigned > PPMap;
130 
131 
161  PPMap ppmap;
162 
163  // A private class used for some ugly skulduggery
164  struct D2_endpoints;
165 
166 
167  float hausdorff_dist_1side( const PixPath& ) const;
168 
169 #if 0
170 
191  int add_a_point_along_longest_segment();
192 
193  int untangle_recursive( int depth ); // disabled bc it is sick
194 #endif
195 
196 protected:
198  PixPath() {}
199 
201  PixPath( size_t potential_size )
202  {
203  my_vpp.reserve( potential_size );
204  }
205 
207  PixPath( const std::string& );
208 
210  PixPath( const PixPoint&, const PixPoint&, size_t );
211 
213  PixPath( const std::string&, int );
214 
215 public:
216  // default copy ctor is just fine, and is (properly) public.
217 
219  typedef const PixPoint& const_reference;
220 
223 
224 #if 0
225  struct Some_error : public kjb::Exception
227  {
228  Some_error( const std::string& m, const char* f, int l )
229  : kjb::Exception( m, f, l )
230  {}
231  };
232 #endif
233 
235  typedef VecPP::const_iterator const_iterator;
236 
238  typedef VecPP::const_reverse_iterator const_reverse_iterator;
239 
241  virtual ~PixPath() {}
242 
244  static PixPath reserve( size_t potential_size = 0 )
245  {
246  return PixPath( potential_size );
247  }
248 
250  static PixPath load( const std::string& filename )
251  {
252  return PixPath( filename );
253  }
254 
274  const PixPoint& pt_a,
275  const PixPoint& pt_b,
276  size_t sz
277  )
278  {
279  return PixPath( pt_a, pt_b, sz );
280  }
281 
283  static PixPath parse( const std::string& coords )
284  {
285  return PixPath( coords, 0 );
286  }
287 
299  virtual PixPath& assign( unsigned index, const PixPoint& newp )
300  {
301  // update the vector
302  PixPoint oldp = my_vpp.at( index );
303  my_vpp.at( index ) = newp;
304 
305  /*
306  * Now update the map.
307  * We could, but do not, delete zero-valued entries. That is because
308  * we expect that in the typical use case, there won't be very many.
309  * It could be done similarly to the following:
310  * if ( 0 == ppmap[ oldp ] ) ppmap.erase( oldp );
311  */
312  if ( ppmap[ oldp ] <= 0 )
313  {
314  KJB_THROW_2(Cant_happen, "Internal corruption in PixPath::ppmap");
315  }
316  ppmap[ oldp ] -= 1;
317  ppmap[ newp ] += 1;
318 
319  return *this;
320  }
321 
323  const PixPoint& operator[]( unsigned index ) const
324  {
325  return my_vpp[ index ];
326  }
327 
329  virtual void push_back( const PixPoint& pp )
330  {
331  my_vpp.push_back( pp );
332  ppmap[ pp ] += 1;
333  }
334 
335  virtual void pop_back();
336 
338  size_t size() const
339  {
340  return my_vpp.size();
341  }
342 
344  virtual void swap( PixPath& vpp )
345  {
346  my_vpp.swap( vpp.my_vpp ); // swap vectors of PixPoints
347  ppmap.swap( vpp.ppmap ); // swap map of duplicates
348  }
349 
351  virtual void clear()
352  {
353  my_vpp.clear();
354  ppmap.clear();
355  }
356 
359  {
360  return my_vpp.begin();
361  }
362 
365  {
366  return my_vpp.end();
367  }
368 
371  {
372  return my_vpp.rbegin();
373  }
374 
377  {
378  return my_vpp.rend();
379  }
380 
395 
409  virtual PixPath& append( const PixPath& suffix );
410 
431  virtual int append_no_overlap( const PixPath& suffix );
432 
433  // Return a new path that is copy of a subrange of this path, [begin,end[
434  PixPath subrange( unsigned, unsigned ) const;
435 
436 
438  PixPath prefix( unsigned postlast ) const
439  {
440  return subrange( 0, postlast );
441  }
442 
456  PixPath suffix( unsigned first ) const
457  {
458  return subrange( first, my_vpp.size() );
459  }
460 
474  bool self_intersect( PixPoint* where = 00 ) const;
475 
477  bool connected8( bool emit_verbose_debug_output = false ) const;
478 
479 
481  PixPoint front() const
482  {
483  return my_vpp.front();
484  }
485 
487  PixPoint back() const
488  {
489  return my_vpp.back();
490  }
491 
503  virtual int arclength( std::vector< float >* ) const;
504 
515  virtual float arclength() const;
516 
518  std::string str( const std::string& separator = "\n" ) const;
519 
521  int save( const std::string& filename ) const;
522 
524  bool operator==( const PixPath& ) const;
525 
527  bool operator!=( const PixPath& other ) const
528  {
529  return ! operator==( other );
530  }
531 
546  PixPath operator+( const PixPath& ) const;
547 
564  virtual PixPoint boundbox_min_min() const;
565 
567  virtual PixPoint boundbox_max_max() const;
568 
580  bool boundbox_within_boundbox( const PixPath& outer ) const
581  {
582  return (boundbox_min_min() - outer.boundbox_min_min()).in_quadrant_I()
583  && (outer.boundbox_max_max() - boundbox_max_max()).in_quadrant_I();
584  }
585 
600  bool so_boundbox_holds_within( const PixPoint& q ) const
601  {
602  return ( q - boundbox_min_min() ).in_quadrant_I()
603  && ( boundbox_max_max() - q ).is_poz_poz();
604  }
605 
619  unsigned hits( const PixPoint& query_point ) const
620  {
621  // You'd think the following is all you need, but no, it breaks const:
622  // return ppmap[ query_point ];
623  // Instead you have to do something like this:
624  PPMap::const_iterator pn = ppmap.find( query_point );
625  return ( ppmap.end() == pn ) ? 0 : pn -> second;
626  }
627 
629  unsigned hits( const PixPath& query_path ) const;
630 
631 
632  PixPoint nearest( const PixPoint&, const_iterator* q = 00 ) const;
633 
634  PixPoint nearest( const kjb::Vector2&, const_iterator* q = 00 ) const;
635 
636 
647  PixPath& ow_reverse();
648 
649 
651  PixPath reverse() const
652  {
653  PixPath ppp( *this );
654  return ppp.ow_reverse();
655  }
656 
657 
666  int cubic_fit( std::vector<float>* x, std::vector<float>* y,
667  int ref = 0) const;
668 
669  PixPath interpolate( bool forbid_self_intersection = false ) const;
670 
672 
674 
676  PixPath expel( const_iterator ) const;
677 
678 
680  PixPath expel( size_t index_of_unwanted_point ) const
681  {
682  return expel( begin() + index_of_unwanted_point );
683  }
684 
685 
694  virtual float hausdorff_distance( const PixPath& that ) const
695  {
696  return std::max( hausdorff_dist_1side( that ),
697  that.hausdorff_dist_1side( *this ) );
698  }
699 
700  // Find the closest pair of points, ignoring adjacency, time is O(N log N).
701  float closest_pair( const_iterator* pa = 0, const_iterator* pb = 0) const;
702 
717  float closest_adjacent_pair( const_iterator* pa = 0 ) const;
718 
720  bool has_subsequence( const PixPath& subseq ) const;
721 
722  double angle_at( unsigned ) const;
723 
724 
741  PixPoint::Integer bracket_cross_at( unsigned index ) const
742  {
743  PixPoint bracket = my_vpp.at( index + 1 ) - my_vpp.at( index - 1 ),
744  here = my_vpp.at( index + 1 ) - my_vpp.at( index );
745  return bracket.cross( here );
746  }
747 
748 
764  double heading_shift_at( unsigned index ) const
765  {
766  double theta = M_PI - angle_at( index );
767  return bracket_cross_at( index ) < 0 ? -theta : theta;
768  }
769 
770 
771 
802  bool intersect_at_with(
803  unsigned preindex1,
804  unsigned preindex2,
805  unsigned* endpoint_intersector_index = 00
806  ) const;
807 
808 
862  unsigned* s1 = 00,
863  unsigned* s2 = 00,
864  unsigned* count = 00
865  ) const;
866 
881  unsigned longest_segment( float* length = 00 ) const;
882 
883 
884 #if 0
885  // something is wrong with this method.
980  int untangle_segments()
981  {
982 #ifdef DEBUGGING
983  assert( ! self_intersect() );
984 #endif
985  return untangle_recursive( 0 );
986  }
987 #endif
988 
989 
991  kjb::Vector2 centroid() const;
992 
994  unsigned member_near_centroid() const;
995 
996 }; // end class PixPath
997 
998 
999 
1000 PixPath bresenham_line( const PixPoint&, const PixPoint& );
1001 
1002 
1003 
1004 PixPath append_trying_not_to_overlap( PixPath, const PixPath& );
1005 
1006 
1007 
1009 template< typename Ran >
1010 inline PixPath copy_pixpoint_array( Ran begin, Ran end )
1011 {
1012  PixPath result( PixPath::reserve( end-begin ) );
1013  std::copy( begin, end, std::back_inserter( result ) );
1014  return result;
1015 }
1016 
1017 
1018 
1019 
1020 }
1021 }
1022 
1023 namespace std
1024 {
1025 
1029  template<>
1030  inline void swap(
1031  kjb::qd::PixPath& p1,
1032  kjb::qd::PixPath& p2
1033  )
1034  {
1035  p1.swap( p2 );
1036  }
1037 
1038 
1039 
1040  /*
1041  * I trust that I don't need to write the same specialization for PixPathAc
1042  * since swap is virtual in PixPath. Not sure.
1043  */
1044 }
1045 
1046 
1047 
1048 #endif
Base class of all exceptions in the jwsc++ library.
Definition: l_exception.h:132
PixPath expel(const_iterator) const
Duplicate this path, except that we omit the indicated point.
Definition: pixpath.cpp:950
double angle_at(unsigned) const
Compute included angle at some interior point in a path.
Definition: pixpath.cpp:1098
Int_matrix::Value_type max(const Int_matrix &mat)
Return the maximum value in this matrix.
Definition: l_int_matrix.h:1397
PixPath merge_redundant_slopes() const
return a path with interior points removed but preserve all slopes.
Definition: pixpath.cpp:1450
VecPP::const_iterator const_iterator
constant iterator through PixPath points
Definition: pixpath.h:235
bool operator==(const PixPath &) const
Compare PixPaths; true iff the sequence of points is identical.
Definition: pixpath.cpp:750
PixPath(size_t potential_size)
ctor receives the size to reserve
Definition: pixpath.h:201
int save(const std::string &filename) const
Saves the path to an ASCII file, returns NO_ERROR or ERROR.
Definition: pixpath.cpp:407
PixPath cull_redundant_points() const
Remove "unnecessary" points (ones that can be bresenham interpolated)
Definition: pixpath.cpp:914
PixPoint front() const
Return (by value) the first point in the path.
Definition: pixpath.h:481
unsigned longest_segment(float *length=00) const
return index of first point of longest segment
Definition: pixpath.cpp:1298
theta
Definition: APPgetLargeConnectedEdges.m:108
const PixPoint & const_reference
Reference to an element – required to use std::back_inserter().
Definition: pixpath.h:219
virtual float hausdorff_distance(const PixPath &that) const
Compute the Hausdorff metric between two sets of points.
Definition: pixpath.h:694
virtual void pop_back()
Definition: pixpath.cpp:1668
virtual PixPath & append(const_iterator begin, const_iterator end)
Append a range from a given other path to the end of this path.
Definition: pixpath.cpp:152
virtual void push_back(const PixPoint &pp)
Vector-like appending a new PixPoint on the end of the object.
Definition: pixpath.h:329
bool operator!=(const PixPath &other) const
Compare PixPaths; true iff the sequence of points differs.
Definition: pixpath.h:527
static PixPath reserve(size_t potential_size=0)
named ctor creates an empty path but reserves some memory for it
Definition: pixpath.h:244
static PixPath fenceposts(const PixPoint &pt_a, const PixPoint &pt_b, size_t sz)
named ctor makes a path of evenly spaced points from a to b
Definition: pixpath.h:273
size_t length(const C &cner)
Counts the total number of elements in a 2D STL-style container.
Definition: l_util.h:17
Integer cross(const PixPoint &pp) const
return cross product of two PixPoints interpreted as 2-vectors.
Definition: pixpoint.h:327
unsigned member_near_centroid() const
return index of a member point nearest centroid() (qv)
Definition: pixpath.cpp:1382
virtual float arclength() const
compute and return polygonal path length of this path
Definition: pixpath.cpp:1637
static PixPath load(const std::string &filename)
named ctor loads path coordinates from an ASCII file
Definition: pixpath.h:250
const_reverse_iterator rend() const
return one-before-first iterator, in symmetry with end().
Definition: pixpath.h:376
Representation of a sequence of pixel coordinates.
Definition: pixpath.h:117
size_t size() const
Number of points in the path (not the same as its length).
Definition: pixpath.h:338
PixPath reverse() const
return a copy of this list after reversing the front-back order.
Definition: pixpath.h:651
const_iterator end() const
Rtn iterator pointing to just beyond the last point in the path.
Definition: pixpath.h:364
virtual int append_no_overlap(const PixPath &suffix)
Like append(), with extra avoid-the-duplicates fuss; overwrites.
Definition: pixpath.cpp:177
std::string str(const std::string &separator="\n") const
Return the path as an ASCII string.
Definition: pixpath.cpp:396
PixPath interpolate(bool forbid_self_intersection=false) const
This interpolates pixels between unconnected pixels.
Definition: pixpath.cpp:792
PixPoint::Integer bracket_cross_at(unsigned index) const
cross product of line segs (index-1,index+1) x (index,index+1)
Definition: pixpath.h:741
const_iterator begin() const
Return an iterator pointing to the first point in the path.
Definition: pixpath.h:358
PixPath append_trying_not_to_overlap(PixPath aaa, const PixPath &bbb)
apppend first to second, without duplicating aaa.back(), bbb.front()
Definition: pixpath.cpp:1661
int cubic_fit(std::vector< float > *x, std::vector< float > *y, int ref=0) const
Fit a cubic polynomial to the given list of x and y points.
Definition: pixpath.cpp:643
const_reverse_iterator rbegin() const
return a reverse-moving iterator to the last point in path
Definition: pixpath.h:370
x
Definition: APPgetLargeConnectedEdges.m:100
unsigned hits(const PixPoint &query_point) const
Return number of times (maybe 0) the path hits a query point.
Definition: pixpath.h:619
PixPath subrange(unsigned, unsigned) const
Returns a subrange of this PixPath object.
Definition: pixpath.cpp:223
Code for a wrapper class around the C struct Pixel.
float closest_adjacent_pair(const_iterator *pa=0) const
Find a pair of adjacent points at least as close as any other.
Definition: pixpath.cpp:1003
PixPath suffix(unsigned first) const
Variation on subrange: return a suffix of this path (by value)
Definition: pixpath.h:456
PixPath copy_pixpoint_array(Ran begin, Ran end)
build a PixPath from a range of PixPoints, using random iterators
Definition: pixpath.h:1010
bool has_subsequence(const PixPath &subseq) const
tests whether a given path is a subsequence of this path
Definition: pixpath.cpp:1033
PixPoint nearest(const PixPoint &, const_iterator *q=00) const
Return the PixPath member closest to a given query point.
Definition: pixpath.cpp:548
bool boundbox_within_boundbox(const PixPath &outer) const
Test whether the axis-aligned bounding box of this path lies within the axis-aligned bounding box of ...
Definition: pixpath.h:580
#define KJB_THROW_2(ex, msg)
Definition: l_exception.h:48
count
Definition: APPgetLargeConnectedEdges.m:71
void swap(kjb::Gsl_Multimin_fdf &m1, kjb::Gsl_Multimin_fdf &m2)
Swap two wrapped multimin objects.
Definition: gsl_multimin.h:693
PixPath operator+(const PixPath &) const
Add, element-by-element, two PixPaths of the same length.
Definition: pixpath.cpp:134
const PixPoint & operator[](unsigned index) const
Vector-like access to points (returning an rvalue).
Definition: pixpath.h:323
#define M_PI
Definition: fft.cpp:206
bool so_boundbox_holds_within(const PixPoint &q) const
sort of like boundbox_within_boundbox but works on a single point
Definition: pixpath.h:600
virtual ~PixPath()
obligatory dtor
Definition: pixpath.h:241
float closest_pair(const_iterator *pa=0, const_iterator *pb=0) const
Find the distance between closest pair of points, ignoring adjacency.
Definition: pixpath.cpp:1521
PixPoint back() const
Return (by value) the last point in the path.
Definition: pixpath.h:487
PixPath bresenham_line(const PixPoint &ca, const PixPoint &b)
ctor builds a sequence of points as a Bresenham straight line.
Definition: pixpath.cpp:262
virtual void swap(PixPath &vpp)
Swap the contents of two PixPaths.
Definition: pixpath.h:344
bool self_intersect(PixPoint *where=00) const
Reveal whether the path has any self-intersections.
Definition: pixpath.cpp:324
bool intersect_at_with(unsigned preindex1, unsigned preindex2, unsigned *endpoint_intersector_index=00) const
Test whether two segments of this path intersect.
Definition: pixpath.cpp:1118
Object thrown when the program does something thought impossible.
Definition: l_exception.h:358
virtual PixPoint boundbox_min_min() const
Return the corner point of a bounding box, with min x and y.
Definition: pixpath.cpp:492
bool do_segments_intersect(unsigned *s1=00, unsigned *s2=00, unsigned *count=00) const
quadratic time test whether any 2 path segments cross each other
Definition: pixpath.cpp:1230
Representation of an (x,y) pair of pixel coordinates.
Definition: pixpoint.h:57
bool connected8(bool emit_verbose_debug_output=false) const
Is the path all connected, using 8-connectivity?
Definition: pixpath.cpp:338
PixPath prefix(unsigned postlast) const
Variation on subrange: return a prefix of this path (by value)
Definition: pixpath.h:438
virtual void clear()
Discard all points.
Definition: pixpath.h:351
kjb::Vector2 centroid() const
return the "mean" of the points (nonempty, none may be unused)
Definition: pixpath.cpp:1362
for m
Definition: APPgetLargeConnectedEdges.m:64
static PixPath parse(const std::string &coords)
named ctor builds from string-format list of coordinates
Definition: pixpath.h:283
PixPath & ow_reverse()
Reverse the order of the points in the path (overwriting!)
Definition: pixpath.cpp:613
PixPath expel(size_t index_of_unwanted_point) const
Duplicate this path, except we omit the point with given index.
Definition: pixpath.h:680
VecPP::const_reverse_iterator const_reverse_iterator
constant reverse iterator through PixPath points
Definition: pixpath.h:238
double heading_shift_at(unsigned index) const
compute shift in "heading" angle at an interior point
Definition: pixpath.h:764
virtual PixPoint boundbox_max_max() const
Similar to boundbox_min_min() but returns maximum x, y coords.
Definition: pixpath.cpp:509
virtual PixPath & assign(unsigned index, const PixPoint &newp)
Change a member of the path to a new PixPoint.
Definition: pixpath.h:299
Contains definition for classes PixPath, PixPathAc, DoubleCircle.
PixPath()
Default ctor starts as empty, and you can push points onto it.
Definition: pixpath.h:198
int Integer
any signed integer valued type is fine
Definition: pixpoint.h:60
PixPoint value_type
Element type – required to use std::back_inserter() in c++11.
Definition: pixpath.h:222