Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/textord/bbgrid.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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.
63 int gridsize() const {
64 return gridsize_;
65 }
66 int gridwidth() const {
67 return gridwidth_;
68 }
69 int gridheight() const {
70 return gridheight_;
71 }
72 const ICOORD &bleft() const {
73 return bleft_;
74 }
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
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 }
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:
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.
238 int GridX() const {
239 return x_;
240 }
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.
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
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>
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>
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>
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>
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>
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>
472 BBGrid<BBC, BBC_CLIST, BBC_C_IT>::BBGrid() : grid_(nullptr) {}
473
474 template <class BBC, class BBC_CLIST, class BBC_C_IT>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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:
619 explicit TabEventHandler(G *grid) : grid_(grid) {}
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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_