Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bbgrid.h
Go to the documentation of this file.
1 
2 // File: bbgrid.h
3 // Description: Class to hold BLOBNBOXs in a grid for fast access
4 // to neighbours.
5 // Author: Ray Smith
6 // Created: Wed Jun 06 17:22:01 PDT 2007
7 //
8 // (C) Copyright 2007, Google Inc.
9 // Licensed under the Apache License, Version 2.0 (the "License");
10 // you may not use this file except in compliance with the License.
11 // You may obtain a copy of the License at
12 // http://www.apache.org/licenses/LICENSE-2.0
13 // Unless required by applicable law or agreed to in writing, software
14 // distributed under the License is distributed on an "AS IS" BASIS,
15 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 // See the License for the specific language governing permissions and
17 // limitations under the License.
18 //
20 
21 #ifndef TESSERACT_TEXTORD_BBGRID_H__
22 #define TESSERACT_TEXTORD_BBGRID_H__
23 
24 #include "clst.h"
25 #include "coutln.h"
26 #include "rect.h"
27 #include "scrollview.h"
28 
29 // Some code is dependent upon leptonica. If you don't have it,
30 // you don't get this functionality.
31 #ifdef HAVE_CONFIG_H
32 #include "config_auto.h"
33 #endif
34 
35 #include "allheaders.h"
36 
37 class BLOCK;
38 
39 namespace tesseract {
40 
41 // Helper function to return a scaled Pix with one pixel per grid cell,
42 // set (black) where the given outline enters the corresponding grid cell,
43 // and clear where the outline does not touch the grid cell.
44 // Also returns the grid coords of the bottom-left of the Pix, in *left
45 // and *bottom, which corresponds to (0, 0) on the Pix.
46 // Note that the Pix is used upside-down, with (0, 0) being the bottom-left.
47 Pix* TraceOutlineOnReducedPix(C_OUTLINE* outline, int gridsize,
48  ICOORD bleft, int* left, int* bottom);
49 // As TraceOutlineOnReducedPix above, but on a BLOCK instead of a C_OUTLINE.
50 Pix* TraceBlockOnReducedPix(BLOCK* block, int gridsize,
51  ICOORD bleft, int* left, int* bottom);
52 
53 template<class BBC, class BBC_CLIST, class BBC_C_IT> class GridSearch;
54 
55 // The GridBase class is the base class for BBGrid and IntGrid.
56 // It holds the geometry and scale of the grid.
57 class GridBase {
58  public:
59  GridBase();
60  GridBase(int gridsize, const ICOORD& bleft, const ICOORD& tright);
61  virtual ~GridBase();
62 
63  // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
64  // and bleft, tright are the bounding box of everything to go in it.
65  void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
66 
67  // Simple accessors.
68  int gridsize() const {
69  return gridsize_;
70  }
71  int gridwidth() const {
72  return gridwidth_;
73  }
74  int gridheight() const {
75  return gridheight_;
76  }
77  const ICOORD& bleft() const {
78  return bleft_;
79  }
80  const ICOORD& tright() const {
81  return tright_;
82  }
83  // Compute the given grid coordinates from image coords.
84  void GridCoords(int x, int y, int* grid_x, int* grid_y) const;
85 
86  // Clip the given grid coordinates to fit within the grid.
87  void ClipGridCoords(int* x, int* y) const;
88 
89  protected:
90  // TODO(rays) Make these private and migrate to the accessors in subclasses.
91  int gridsize_; // Pixel size of each grid cell.
92  int gridwidth_; // Size of the grid in cells.
94  int gridbuckets_; // Total cells in grid.
95  ICOORD bleft_; // Pixel coords of bottom-left of grid.
96  ICOORD tright_; // Pixel coords of top-right of grid.
97 
98  private:
99 };
100 
101 // The IntGrid maintains a single int for each cell in a grid.
102 class IntGrid : public GridBase {
103  public:
104  IntGrid();
105  IntGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
106  virtual ~IntGrid();
107 
108  // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
109  // and bleft, tright are the bounding box of everything to go in it.
110  void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
111 
112  // Clear all the ints in the grid to zero.
113  void Clear();
114 
115  // Rotate the grid by rotation, keeping cell contents.
116  // rotation must be a multiple of 90 degrees.
117  // NOTE: due to partial cells, cell coverage in the rotated grid will be
118  // inexact. This is why there is no Rotate for the generic BBGrid.
119  void Rotate(const FCOORD& rotation);
120 
121  // Returns a new IntGrid containing values equal to the sum of all the
122  // neighbouring cells. The returned grid must be deleted after use.
123  IntGrid* NeighbourhoodSum() const;
124 
125  int GridCellValue(int grid_x, int grid_y) const {
126  ClipGridCoords(&grid_x, &grid_y);
127  return grid_[grid_y * gridwidth_ + grid_x];
128  }
129  void SetGridCell(int grid_x, int grid_y, int value) {
130  ASSERT_HOST(grid_x >= 0 && grid_x < gridwidth());
131  ASSERT_HOST(grid_y >= 0 && grid_y < gridheight());
132  grid_[grid_y * gridwidth_ + grid_x] = value;
133  }
134  // Returns true if more than half the area of the rect is covered by grid
135  // cells that are over the theshold.
136  bool RectMostlyOverThreshold(const TBOX& rect, int threshold) const;
137 
138  // Returns true if any cell value in the given rectangle is zero.
139  bool AnyZeroInRect(const TBOX& rect) const;
140 
141  // Returns a full-resolution binary pix in which each cell over the given
142  // threshold is filled as a black square. pixDestroy after use.
143  Pix* ThresholdToPix(int threshold) const;
144 
145  private:
146  int* grid_; // 2-d array of ints.
147 };
148 
149 // The BBGrid class holds C_LISTs of template classes BBC (bounding box class)
150 // in a grid for fast neighbour access.
151 // The BBC class must have a member const TBOX& bounding_box() const.
152 // The BBC class must have been CLISTIZEH'ed elsewhere to make the
153 // list class BBC_CLIST and the iterator BBC_C_IT.
154 // Use of C_LISTs enables BBCs to exist in multiple cells simultaneously.
155 // As a consequence, ownership of BBCs is assumed to be elsewhere and
156 // persistent for at least the life of the BBGrid, or at least until Clear is
157 // called which removes all references to inserted objects without actually
158 // deleting them.
159 // Most uses derive a class from a specific instantiation of BBGrid,
160 // thereby making most of the ugly template notation go away.
161 // The friend class GridSearch, with the same template arguments, is
162 // used to search a grid efficiently in one of several search patterns.
163 template<class BBC, class BBC_CLIST, class BBC_C_IT> class BBGrid
164  : public GridBase {
165  friend class GridSearch<BBC, BBC_CLIST, BBC_C_IT>;
166  public:
167  BBGrid();
168  BBGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
169  virtual ~BBGrid();
170 
171  // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
172  // and bleft, tright are the bounding box of everything to go in it.
173  void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
174 
175  // Empty all the lists but leave the grid itself intact.
176  void Clear();
177  // Deallocate the data in the lists but otherwise leave the lists and the grid
178  // intact.
179  void ClearGridData(void (*free_method)(BBC*));
180 
181  // Insert a bbox into the appropriate place in the grid.
182  // If h_spread, then all cells covered horizontally by the box are
183  // used, otherwise, just the bottom-left. Similarly for v_spread.
184  // WARNING: InsertBBox may invalidate an active GridSearch. Call
185  // RepositionIterator() on any GridSearches that are active on this grid.
186  void InsertBBox(bool h_spread, bool v_spread, BBC* bbox);
187 
188  // Using a pix from TraceOutlineOnReducedPix or TraceBlockOnReducedPix, in
189  // which each pixel corresponds to a grid cell, insert a bbox into every
190  // place in the grid where the corresponding pixel is 1. The Pix is handled
191  // upside-down to match the Tesseract coordinate system. (As created by
192  // TraceOutlineOnReducedPix or TraceBlockOnReducedPix.)
193  // (0, 0) in the pix corresponds to (left, bottom) in the
194  // grid (in grid coords), and the pix works up the grid from there.
195  // WARNING: InsertPixPtBBox may invalidate an active GridSearch. Call
196  // RepositionIterator() on any GridSearches that are active on this grid.
197  void InsertPixPtBBox(int left, int bottom, Pix* pix, BBC* bbox);
198 
199  // Remove the bbox from the grid.
200  // WARNING: Any GridSearch operating on this grid could be invalidated!
201  // If a GridSearch is operating, call GridSearch::RemoveBBox() instead.
202  void RemoveBBox(BBC* bbox);
203 
204  // Returns true if the given rectangle has no overlapping elements.
205  bool RectangleEmpty(const TBOX& rect);
206 
207  // Returns an IntGrid showing the number of elements in each cell.
208  // Returned IntGrid must be deleted after use.
210 
211  // Make a window of an appropriate size to display things in the grid.
212  ScrollView* MakeWindow(int x, int y, const char* window_name);
213 
214  // Display the bounding boxes of the BLOBNBOXes in this grid.
215  // Use of this function requires an additional member of the BBC class:
216  // ScrollView::Color BBC::BoxColor() const.
217  void DisplayBoxes(ScrollView* window);
218 
219  // ASSERT_HOST that every cell contains no more than one copy of each entry.
220  void AssertNoDuplicates();
221 
222  // Handle a click event in a display window.
223  virtual void HandleClick(int x, int y);
224 
225  protected:
226  BBC_CLIST* grid_; // 2-d array of CLISTS of BBC elements.
227 
228  private:
229 };
230 
231 // The GridSearch class enables neighbourhood searching on a BBGrid.
232 template<class BBC, class BBC_CLIST, class BBC_C_IT> class GridSearch {
233  public:
235  : grid_(grid), unique_mode_(false),
236  previous_return_(NULL), next_return_(NULL) {
237  }
238 
239  // Get the grid x, y coords of the most recently returned BBC.
240  int GridX() const {
241  return x_;
242  }
243  int GridY() const {
244  return y_;
245  }
246 
247  // Sets the search mode to return a box only once.
248  // Efficiency warning: Implementation currently uses a squared-order
249  // search in the number of returned elements. Use only where a small
250  // number of elements are spread over a wide area, eg ColPartitions.
251  void SetUniqueMode(bool mode) {
252  unique_mode_ = mode;
253  }
254  // TODO(rays) Replace calls to ReturnedSeedElement with SetUniqueMode.
255  // It only works if the search includes the bottom-left corner.
256  // Apart from full search, all other searches return a box several
257  // times if the box is inserted with h_spread or v_spread.
258  // This method will return true for only one occurrence of each box
259  // that was inserted with both h_spread and v_spread as true.
260  // It will usually return false for boxes that were not inserted with
261  // both h_spread=true and v_spread=true
262  bool ReturnedSeedElement() const {
263  TBOX box = previous_return_->bounding_box();
264  int x_center = (box.left()+box.right())/2;
265  int y_center = (box.top()+box.bottom())/2;
266  int grid_x, grid_y;
267  grid_->GridCoords(x_center, y_center, &grid_x, &grid_y);
268  return (x_ == grid_x) && (y_ == grid_y);
269  }
270 
271  // Various searching iterations... Note that these iterations
272  // all share data members, so you can't run more than one iteration
273  // in parallel in a single GridSearch instance, but multiple instances
274  // can search the same BBGrid in parallel.
275  // Note that all the searches can return blobs that may not exactly
276  // match the search conditions, since they return everything in the
277  // covered grid cells. It is up to the caller to check for
278  // appropriateness.
279  // TODO(rays) NextRectSearch only returns valid elements. Make the other
280  // searches test before return also and remove the tests from code
281  // that uses GridSearch.
282 
283  // Start a new full search. Will iterate all stored blobs, from the top.
284  // If the blobs have been inserted using InsertBBox, (not InsertPixPtBBox)
285  // then the full search guarantees to return each blob in the grid once.
286  // Other searches may return a blob more than once if they have been
287  // inserted using h_spread or v_spread.
288  void StartFullSearch();
289  // Return the next bbox in the search or NULL if done.
290  BBC* NextFullSearch();
291 
292  // Start a new radius search. Will search in a spiral upto a
293  // given maximum radius in grid cells from the given center in pixels.
294  void StartRadSearch(int x, int y, int max_radius);
295  // Return the next bbox in the radius search or NULL if the
296  // maximum radius has been reached.
297  BBC* NextRadSearch();
298 
299  // Start a new left or right-looking search. Will search to the side
300  // for a box that vertically overlaps the given vertical line segment.
301  // CAVEAT: This search returns all blobs from the cells to the side
302  // of the start, and somewhat below, since there is no guarantee
303  // that there may not be a taller object in a lower cell. The
304  // blobs returned will include all those that vertically overlap and
305  // are no more than twice as high, but may also include some that do
306  // not overlap and some that are more than twice as high.
307  void StartSideSearch(int x, int ymin, int ymax);
308  // Return the next bbox in the side search or NULL if the
309  // edge has been reached. Searches left to right or right to left
310  // according to the flag.
311  BBC* NextSideSearch(bool right_to_left);
312 
313  // Start a vertical-looking search. Will search up or down
314  // for a box that horizontally overlaps the given line segment.
315  void StartVerticalSearch(int xmin, int xmax, int y);
316  // Return the next bbox in the vertical search or NULL if the
317  // edge has been reached. Searches top to bottom or bottom to top
318  // according to the flag.
319  BBC* NextVerticalSearch(bool top_to_bottom);
320 
321  // Start a rectangular search. Will search for a box that overlaps the
322  // given rectangle.
323  void StartRectSearch(const TBOX& rect);
324  // Return the next bbox in the rectangular search or NULL if complete.
325  BBC* NextRectSearch();
326 
327  // Remove the last returned BBC. Will not invalidate this. May invalidate
328  // any other concurrent GridSearch on the same grid. If any others are
329  // in use, call RepositionIterator on those, to continue without harm.
330  void RemoveBBox();
331  void RepositionIterator();
332 
333  private:
334  // Factored out helper to start a search.
335  void CommonStart(int x, int y);
336  // Factored out helper to complete a next search.
337  BBC* CommonNext();
338  // Factored out final return when search is exhausted.
339  BBC* CommonEnd();
340  // Factored out function to set the iterator to the current x_, y_
341  // grid coords and mark the cycle pt.
342  void SetIterator();
343 
344  private:
345  // The grid we are searching.
347  // For executing a search. The different search algorithms use these in
348  // different ways, but most use x_origin_ and y_origin_ as the start position.
349  int x_origin_;
350  int y_origin_;
351  int max_radius_;
352  int radius_;
353  int rad_index_;
354  int rad_dir_;
355  TBOX rect_;
356  int x_; // The current location in grid coords, of the current search.
357  int y_;
358  bool unique_mode_;
359  BBC* previous_return_; // Previous return from Next*.
360  BBC* next_return_; // Current value of it_.data() used for repositioning.
361  // An iterator over the list at (x_, y_) in the grid_.
362  BBC_C_IT it_;
363  // List of unique returned elements used when unique_mode_ is true.
364  BBC_CLIST returns_;
365 };
366 
367 // Sort function to sort a BBC by bounding_box().left().
368 template<class BBC>
369 int SortByBoxLeft(const void* void1, const void* void2) {
370  // The void*s are actually doubly indirected, so get rid of one level.
371  const BBC* p1 = *reinterpret_cast<const BBC* const *>(void1);
372  const BBC* p2 = *reinterpret_cast<const BBC* const *>(void2);
373  int result = p1->bounding_box().left() - p2->bounding_box().left();
374  if (result != 0)
375  return result;
376  result = p1->bounding_box().right() - p2->bounding_box().right();
377  if (result != 0)
378  return result;
379  result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
380  if (result != 0)
381  return result;
382  return p1->bounding_box().top() - p2->bounding_box().top();
383 }
384 
385 // Sort function to sort a BBC by bounding_box().right() in right-to-left order.
386 template<class BBC>
387 int SortRightToLeft(const void* void1, const void* void2) {
388  // The void*s are actually doubly indirected, so get rid of one level.
389  const BBC* p1 = *reinterpret_cast<const BBC* const *>(void1);
390  const BBC* p2 = *reinterpret_cast<const BBC* const *>(void2);
391  int result = p2->bounding_box().right() - p1->bounding_box().right();
392  if (result != 0)
393  return result;
394  result = p2->bounding_box().left() - p1->bounding_box().left();
395  if (result != 0)
396  return result;
397  result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
398  if (result != 0)
399  return result;
400  return p1->bounding_box().top() - p2->bounding_box().top();
401 }
402 
403 // Sort function to sort a BBC by bounding_box().bottom().
404 template<class BBC>
405 int SortByBoxBottom(const void* void1, const void* void2) {
406  // The void*s are actually doubly indirected, so get rid of one level.
407  const BBC* p1 = *reinterpret_cast<const BBC* const *>(void1);
408  const BBC* p2 = *reinterpret_cast<const BBC* const *>(void2);
409  int result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
410  if (result != 0)
411  return result;
412  result = p1->bounding_box().top() - p2->bounding_box().top();
413  if (result != 0)
414  return result;
415  result = p1->bounding_box().left() - p2->bounding_box().left();
416  if (result != 0)
417  return result;
418  return p1->bounding_box().right() - p2->bounding_box().right();
419 }
420 
422 // BBGrid IMPLEMENTATION.
424 template<class BBC, class BBC_CLIST, class BBC_C_IT>
426 }
427 
428 template<class BBC, class BBC_CLIST, class BBC_C_IT>
430  int gridsize, const ICOORD& bleft, const ICOORD& tright)
431  : grid_(NULL) {
432  Init(gridsize, bleft, tright);
433 }
434 
435 template<class BBC, class BBC_CLIST, class BBC_C_IT>
437  if (grid_ != NULL)
438  delete [] grid_;
439 }
440 
441 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
442 // and bleft, tright are the bounding box of everything to go in it.
443 template<class BBC, class BBC_CLIST, class BBC_C_IT>
445  const ICOORD& bleft,
446  const ICOORD& tright) {
447  GridBase::Init(gridsize, bleft, tright);
448  if (grid_ != NULL)
449  delete [] grid_;
450  grid_ = new BBC_CLIST[gridbuckets_];
451 }
452 
453 // Clear all lists, but leave the array of lists present.
454 template<class BBC, class BBC_CLIST, class BBC_C_IT>
456  for (int i = 0; i < gridbuckets_; ++i) {
457  grid_[i].shallow_clear();
458  }
459 }
460 
461 // Deallocate the data in the lists but otherwise leave the lists and the grid
462 // intact.
463 template<class BBC, class BBC_CLIST, class BBC_C_IT>
465  void (*free_method)(BBC*)) {
466  if (grid_ == NULL) return;
468  search.StartFullSearch();
469  BBC* bb;
470  BBC_CLIST bb_list;
471  BBC_C_IT it(&bb_list);
472  while ((bb = search.NextFullSearch()) != NULL) {
473  it.add_after_then_move(bb);
474  }
475  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
476  free_method(it.data());
477  }
478 }
479 
480 // Insert a bbox into the appropriate place in the grid.
481 // If h_spread, then all cells covered horizontally by the box are
482 // used, otherwise, just the bottom-left. Similarly for v_spread.
483 // WARNING: InsertBBox may invalidate an active GridSearch. Call
484 // RepositionIterator() on any GridSearches that are active on this grid.
485 template<class BBC, class BBC_CLIST, class BBC_C_IT>
486 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::InsertBBox(bool h_spread, bool v_spread,
487  BBC* bbox) {
488  TBOX box = bbox->bounding_box();
489  int start_x, start_y, end_x, end_y;
490  GridCoords(box.left(), box.bottom(), &start_x, &start_y);
491  GridCoords(box.right(), box.top(), &end_x, &end_y);
492  if (!h_spread)
493  end_x = start_x;
494  if (!v_spread)
495  end_y = start_y;
496  int grid_index = start_y * gridwidth_;
497  for (int y = start_y; y <= end_y; ++y, grid_index += gridwidth_) {
498  for (int x = start_x; x <= end_x; ++x) {
499  grid_[grid_index + x].add_sorted(SortByBoxLeft<BBC>, true, bbox);
500  }
501  }
502 }
503 
504 // Using a pix from TraceOutlineOnReducedPix or TraceBlockOnReducedPix, in
505 // which each pixel corresponds to a grid cell, insert a bbox into every
506 // place in the grid where the corresponding pixel is 1. The Pix is handled
507 // upside-down to match the Tesseract coordinate system. (As created by
508 // TraceOutlineOnReducedPix or TraceBlockOnReducedPix.)
509 // (0, 0) in the pix corresponds to (left, bottom) in the
510 // grid (in grid coords), and the pix works up the grid from there.
511 // WARNING: InsertPixPtBBox may invalidate an active GridSearch. Call
512 // RepositionIterator() on any GridSearches that are active on this grid.
513 template<class BBC, class BBC_CLIST, class BBC_C_IT>
515  Pix* pix, BBC* bbox) {
516  int width = pixGetWidth(pix);
517  int height = pixGetHeight(pix);
518  for (int y = 0; y < height; ++y) {
519  l_uint32* data = pixGetData(pix) + y * pixGetWpl(pix);
520  for (int x = 0; x < width; ++x) {
521  if (GET_DATA_BIT(data, x)) {
522  grid_[(bottom + y) * gridwidth_ + x + left].
523  add_sorted(SortByBoxLeft<BBC>, true, bbox);
524  }
525  }
526  }
527 }
528 
529 // Remove the bbox from the grid.
530 // WARNING: Any GridSearch operating on this grid could be invalidated!
531 // If a GridSearch is operating, call GridSearch::RemoveBBox() instead.
532 template<class BBC, class BBC_CLIST, class BBC_C_IT>
534  TBOX box = bbox->bounding_box();
535  int start_x, start_y, end_x, end_y;
536  GridCoords(box.left(), box.bottom(), &start_x, &start_y);
537  GridCoords(box.right(), box.top(), &end_x, &end_y);
538  int grid_index = start_y * gridwidth_;
539  for (int y = start_y; y <= end_y; ++y, grid_index += gridwidth_) {
540  for (int x = start_x; x <= end_x; ++x) {
541  BBC_C_IT it(&grid_[grid_index + x]);
542  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
543  if (it.data() == bbox)
544  it.extract();
545  }
546  }
547  }
548 }
549 
550 // Returns true if the given rectangle has no overlapping elements.
551 template<class BBC, class BBC_CLIST, class BBC_C_IT>
554  rsearch.StartRectSearch(rect);
555  return rsearch.NextRectSearch() == NULL;
556 }
557 
558 // Returns an IntGrid showing the number of elements in each cell.
559 // Returned IntGrid must be deleted after use.
560 template<class BBC, class BBC_CLIST, class BBC_C_IT>
562  IntGrid* intgrid = new IntGrid(gridsize(), bleft(), tright());
563  for (int y = 0; y < gridheight(); ++y) {
564  for (int x = 0; x < gridwidth(); ++x) {
565  int cell_count = grid_[y * gridwidth() + x].length();
566  intgrid->SetGridCell(x, y, cell_count);
567  }
568  }
569  return intgrid;
570 }
571 
572 
573 template<class G> class TabEventHandler : public SVEventHandler {
574  public:
575  explicit TabEventHandler(G* grid) : grid_(grid) {
576  }
577  void Notify(const SVEvent* sv_event) {
578  if (sv_event->type == SVET_CLICK) {
579  grid_->HandleClick(sv_event->x, sv_event->y);
580  }
581  }
582  private:
583  G* grid_;
584 };
585 
586 // Make a window of an appropriate size to display things in the grid.
587 // Position the window at the given x,y.
588 template<class BBC, class BBC_CLIST, class BBC_C_IT>
590  int x, int y, const char* window_name) {
591  ScrollView* tab_win = NULL;
592 #ifndef GRAPHICS_DISABLED
593  tab_win = new ScrollView(window_name, x, y,
594  tright_.x() - bleft_.x(),
595  tright_.y() - bleft_.y(),
596  tright_.x() - bleft_.x(),
597  tright_.y() - bleft_.y(),
598  true);
601  tab_win->AddEventHandler(handler);
602  tab_win->Pen(ScrollView::GREY);
603  tab_win->Rectangle(0, 0, tright_.x() - bleft_.x(), tright_.y() - bleft_.y());
604 #endif
605  return tab_win;
606 }
607 
608 // Create a window at (x,y) and display the bounding boxes of the
609 // BLOBNBOXes in this grid.
610 // Use of this function requires an additional member of the BBC class:
611 // ScrollView::Color BBC::BoxColor() const.
612 template<class BBC, class BBC_CLIST, class BBC_C_IT>
614 #ifndef GRAPHICS_DISABLED
615  tab_win->Pen(ScrollView::BLUE);
616  tab_win->Brush(ScrollView::NONE);
617 
618  // For every bbox in the grid, display it.
620  gsearch.StartFullSearch();
621  BBC* bbox;
622  while ((bbox = gsearch.NextFullSearch()) != NULL) {
623  TBOX box = bbox->bounding_box();
624  int left_x = box.left();
625  int right_x = box.right();
626  int top_y = box.top();
627  int bottom_y = box.bottom();
628  ScrollView::Color box_color = bbox->BoxColor();
629  tab_win->Pen(box_color);
630  tab_win->Rectangle(left_x, bottom_y, right_x, top_y);
631  }
632  tab_win->Update();
633 #endif
634 }
635 
636 // ASSERT_HOST that every cell contains no more than one copy of each entry.
637 template<class BBC, class BBC_CLIST, class BBC_C_IT>
639  // Process all grid cells.
640  for (int i = gridwidth_ * gridheight_ - 1; i >= 0; --i) {
641  // Iterate over all elements excent the last.
642  for (BBC_C_IT it(&grid_[i]); !it.at_last(); it.forward()) {
643  BBC* ptr = it.data();
644  BBC_C_IT it2(it);
645  // None of the rest of the elements in the list should equal ptr.
646  for (it2.forward(); !it2.at_first(); it2.forward()) {
647  ASSERT_HOST(it2.data() != ptr);
648  }
649  }
650  }
651 }
652 
653 // Handle a click event in a display window.
654 template<class BBC, class BBC_CLIST, class BBC_C_IT>
656  tprintf("Click at (%d, %d)\n", x, y);
657 }
658 
660 // GridSearch IMPLEMENTATION.
662 
663 // Start a new full search. Will iterate all stored blobs.
664 template<class BBC, class BBC_CLIST, class BBC_C_IT>
666  // Full search uses x_ and y_ as the current grid
667  // cell being searched.
668  CommonStart(grid_->bleft_.x(), grid_->tright_.y());
669 }
670 
671 // Return the next bbox in the search or NULL if done.
672 // The other searches will return a box that overlaps the grid cell
673 // thereby duplicating boxes, but NextFullSearch only returns each box once.
674 template<class BBC, class BBC_CLIST, class BBC_C_IT>
676  int x;
677  int y;
678  do {
679  while (it_.cycled_list()) {
680  ++x_;
681  if (x_ >= grid_->gridwidth_) {
682  --y_;
683  if (y_ < 0)
684  return CommonEnd();
685  x_ = 0;
686  }
687  SetIterator();
688  }
689  CommonNext();
690  TBOX box = previous_return_->bounding_box();
691  grid_->GridCoords(box.left(), box.bottom(), &x, &y);
692  } while (x != x_ || y != y_);
693  return previous_return_;
694 }
695 
696 // Start a new radius search.
697 template<class BBC, class BBC_CLIST, class BBC_C_IT>
699  int max_radius) {
700  // Rad search uses x_origin_ and y_origin_ as the center of the circle.
701  // The radius_ is the radius of the (diamond-shaped) circle and
702  // rad_index/rad_dir_ combine to determine the position around it.
703  max_radius_ = max_radius;
704  radius_ = 0;
705  rad_index_ = 0;
706  rad_dir_ = 3;
707  CommonStart(x, y);
708 }
709 
710 // Return the next bbox in the radius search or NULL if the
711 // maximum radius has been reached.
712 template<class BBC, class BBC_CLIST, class BBC_C_IT>
714  do {
715  while (it_.cycled_list()) {
716  ++rad_index_;
717  if (rad_index_ >= radius_) {
718  ++rad_dir_;
719  rad_index_ = 0;
720  if (rad_dir_ >= 4) {
721  ++radius_;
722  if (radius_ > max_radius_)
723  return CommonEnd();
724  rad_dir_ = 0;
725  }
726  }
727  ICOORD offset = C_OUTLINE::chain_step(rad_dir_);
728  offset *= radius_ - rad_index_;
729  offset += C_OUTLINE::chain_step(rad_dir_ + 1) * rad_index_;
730  x_ = x_origin_ + offset.x();
731  y_ = y_origin_ + offset.y();
732  if (x_ >= 0 && x_ < grid_->gridwidth_ &&
733  y_ >= 0 && y_ < grid_->gridheight_)
734  SetIterator();
735  }
736  CommonNext();
737  } while (unique_mode_ &&
738  !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_));
739  return previous_return_;
740 }
741 
742 // Start a new left or right-looking search. Will search to the side
743 // for a box that vertically overlaps the given vertical line segment.
744 template<class BBC, class BBC_CLIST, class BBC_C_IT>
746  int ymin, int ymax) {
747  // Right search records the x in x_origin_, the ymax in y_origin_
748  // and the size of the vertical strip to search in radius_.
749  // To guarantee finding overlapping objects of upto twice the
750  // given size, double the height.
751  radius_ = ((ymax - ymin) * 2 + grid_->gridsize_ - 1) / grid_->gridsize_;
752  rad_index_ = 0;
753  CommonStart(x, ymax);
754 }
755 
756 // Return the next bbox in the side search or NULL if the
757 // edge has been reached. Searches left to right or right to left
758 // according to the flag.
759 template<class BBC, class BBC_CLIST, class BBC_C_IT>
761  do {
762  while (it_.cycled_list()) {
763  ++rad_index_;
764  if (rad_index_ > radius_) {
765  if (right_to_left)
766  --x_;
767  else
768  ++x_;
769  rad_index_ = 0;
770  if (x_ < 0 || x_ >= grid_->gridwidth_)
771  return CommonEnd();
772  }
773  y_ = y_origin_ - rad_index_;
774  if (y_ >= 0 && y_ < grid_->gridheight_)
775  SetIterator();
776  }
777  CommonNext();
778  } while (unique_mode_ &&
779  !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_));
780  return previous_return_;
781 }
782 
783 // Start a vertical-looking search. Will search up or down
784 // for a box that horizontally overlaps the given line segment.
785 template<class BBC, class BBC_CLIST, class BBC_C_IT>
787  int xmax,
788  int y) {
789  // Right search records the xmin in x_origin_, the y in y_origin_
790  // and the size of the horizontal strip to search in radius_.
791  radius_ = (xmax - xmin + grid_->gridsize_ - 1) / grid_->gridsize_;
792  rad_index_ = 0;
793  CommonStart(xmin, y);
794 }
795 
796 // Return the next bbox in the vertical search or NULL if the
797 // edge has been reached. Searches top to bottom or bottom to top
798 // according to the flag.
799 template<class BBC, class BBC_CLIST, class BBC_C_IT>
801  bool top_to_bottom) {
802  do {
803  while (it_.cycled_list()) {
804  ++rad_index_;
805  if (rad_index_ > radius_) {
806  if (top_to_bottom)
807  --y_;
808  else
809  ++y_;
810  rad_index_ = 0;
811  if (y_ < 0 || y_ >= grid_->gridheight_)
812  return CommonEnd();
813  }
814  x_ = x_origin_ + rad_index_;
815  if (x_ >= 0 && x_ < grid_->gridwidth_)
816  SetIterator();
817  }
818  CommonNext();
819  } while (unique_mode_ &&
820  !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_));
821  return previous_return_;
822 }
823 
824 // Start a rectangular search. Will search for a box that overlaps the
825 // given rectangle.
826 template<class BBC, class BBC_CLIST, class BBC_C_IT>
828  // Rect search records the xmin in x_origin_, the ymin in y_origin_
829  // and the xmax in max_radius_.
830  // The search proceeds left to right, top to bottom.
831  rect_ = rect;
832  CommonStart(rect.left(), rect.top());
833  grid_->GridCoords(rect.right(), rect.bottom(), // - rect.height(),
834  &max_radius_, &y_origin_);
835 }
836 
837 // Return the next bbox in the rectangular search or NULL if complete.
838 template<class BBC, class BBC_CLIST, class BBC_C_IT>
840  do {
841  while (it_.cycled_list()) {
842  ++x_;
843  if (x_ > max_radius_) {
844  --y_;
845  x_ = x_origin_;
846  if (y_ < y_origin_)
847  return CommonEnd();
848  }
849  SetIterator();
850  }
851  CommonNext();
852  } while (!rect_.overlap(previous_return_->bounding_box()) ||
853  (unique_mode_ &&
854  !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_)));
855  return previous_return_;
856 }
857 
858 // Remove the last returned BBC. Will not invalidate this. May invalidate
859 // any other concurrent GridSearch on the same grid. If any others are
860 // in use, call RepositionIterator on those, to continue without harm.
861 template<class BBC, class BBC_CLIST, class BBC_C_IT>
863  if (previous_return_ != NULL) {
864  // Remove all instances of previous_return_ from the list, so the iterator
865  // remains valid after removal from the rest of the grid cells.
866  // if previous_return_ is not on the list, then it has been removed already.
867  BBC* prev_data = NULL;
868  BBC* new_previous_return = NULL;
869  it_.move_to_first();
870  for (it_.mark_cycle_pt(); !it_.cycled_list();) {
871  if (it_.data() == previous_return_) {
872  new_previous_return = prev_data;
873  it_.extract();
874  it_.forward();
875  next_return_ = it_.cycled_list() ? NULL : it_.data();
876  } else {
877  prev_data = it_.data();
878  it_.forward();
879  }
880  }
881  grid_->RemoveBBox(previous_return_);
882  previous_return_ = new_previous_return;
883  RepositionIterator();
884  }
885 }
886 
887 template<class BBC, class BBC_CLIST, class BBC_C_IT>
889  // Something was deleted, so we have little choice but to clear the
890  // returns list.
891  returns_.shallow_clear();
892  // Reset the iterator back to one past the previous return.
893  // If the previous_return_ is no longer in the list, then
894  // next_return_ serves as a backup.
895  it_.move_to_first();
896  // Special case, the first element was removed and reposition
897  // iterator was called. In this case, the data is fine, but the
898  // cycle point is not. Detect it and return.
899  if (!it_.empty() && it_.data() == next_return_) {
900  it_.mark_cycle_pt();
901  return;
902  }
903  for (it_.mark_cycle_pt(); !it_.cycled_list(); it_.forward()) {
904  if (it_.data() == previous_return_ ||
905  it_.data_relative(1) == next_return_) {
906  CommonNext();
907  return;
908  }
909  }
910  // We ran off the end of the list. Move to a new cell next time.
911  previous_return_ = NULL;
912  next_return_ = NULL;
913 }
914 
915 // Factored out helper to start a search.
916 template<class BBC, class BBC_CLIST, class BBC_C_IT>
918  grid_->GridCoords(x, y, &x_origin_, &y_origin_);
919  x_ = x_origin_;
920  y_ = y_origin_;
921  SetIterator();
922  previous_return_ = NULL;
923  next_return_ = it_.empty() ? NULL : it_.data();
924  returns_.shallow_clear();
925 }
926 
927 // Factored out helper to complete a next search.
928 template<class BBC, class BBC_CLIST, class BBC_C_IT>
929 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonNext() {
930  previous_return_ = it_.data();
931  it_.forward();
932  next_return_ = it_.cycled_list() ? NULL : it_.data();
933  return previous_return_;
934 }
935 
936 // Factored out final return when search is exhausted.
937 template<class BBC, class BBC_CLIST, class BBC_C_IT>
938 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonEnd() {
939  previous_return_ = NULL;
940  next_return_ = NULL;
941  return NULL;
942 }
943 
944 // Factored out function to set the iterator to the current x_, y_
945 // grid coords and mark the cycle pt.
946 template<class BBC, class BBC_CLIST, class BBC_C_IT>
947 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::SetIterator() {
948  it_= &(grid_->grid_[y_ * grid_->gridwidth_ + x_]);
949  it_.mark_cycle_pt();
950 }
951 
952 } // namespace tesseract.
953 
954 #endif // TESSERACT_TEXTORD_BBGRID_H__