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