20 #ifndef TESSERACT_TEXTORD_BBGRID_H_
21 #define TESSERACT_TEXTORD_BBGRID_H_
23 #include <unordered_set>
30 #include "allheaders.h"
43 ICOORD bleft,
int* left,
int* bottom);
46 ICOORD bleft,
int* left,
int* bottom);
48 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
class GridSearch;
79 void GridCoords(
int x,
int y,
int* grid_x,
int* grid_y)
const;
158 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
class BBGrid
181 void InsertBBox(
bool h_spread,
bool v_spread, BBC* bbox);
229 return reinterpret_cast<uintptr_t>(ptr) /
sizeof(T);
235 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
class GridSearch {
265 TBOX box = previous_return_->bounding_box();
266 int x_center = (box.
left()+box.
right())/2;
267 int y_center = (box.
top()+box.
bottom())/2;
269 grid_->GridCoords(x_center, y_center, &grid_x, &grid_y);
270 return (x_ == grid_x) && (y_ == grid_y);
337 void CommonStart(
int x,
int y);
360 bool unique_mode_ =
false;
361 BBC* previous_return_ =
nullptr;
362 BBC* next_return_ =
nullptr;
366 std::unordered_set<BBC*, PtrHash<BBC> > returns_;
373 const BBC* p1 = *static_cast<const BBC* const*>(void1);
374 const BBC* p2 = *static_cast<const BBC* const*>(void2);
375 int result = p1->bounding_box().left() - p2->bounding_box().left();
378 result = p1->bounding_box().right() - p2->bounding_box().right();
381 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
384 return p1->bounding_box().top() - p2->bounding_box().top();
391 const BBC* p1 = *static_cast<const BBC* const*>(void1);
392 const BBC* p2 = *static_cast<const BBC* const*>(void2);
393 int result = p2->bounding_box().right() - p1->bounding_box().right();
396 result = p2->bounding_box().left() - p1->bounding_box().left();
399 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
402 return p1->bounding_box().top() - p2->bounding_box().top();
409 const BBC* p1 = *static_cast<const BBC* const*>(void1);
410 const BBC* p2 = *static_cast<const BBC* const*>(void2);
411 int result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
414 result = p1->bounding_box().top() - p2->bounding_box().top();
417 result = p1->bounding_box().left() - p2->bounding_box().left();
420 return p1->bounding_box().right() - p2->bounding_box().right();
426 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
430 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
432 int gridsize,
const ICOORD& bleft,
const ICOORD& tright)
434 Init(gridsize, bleft, tright);
437 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
444 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
448 GridBase::Init(gridsize, bleft, tright);
450 grid_ =
new BBC_CLIST[gridbuckets_];
454 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
456 for (
int i = 0; i < gridbuckets_; ++i) {
457 grid_[i].shallow_clear();
463 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
465 void (*free_method)(BBC*)) {
466 if (grid_ ==
nullptr)
return;
471 BBC_C_IT it(&bb_list);
472 while ((bb =
search.NextFullSearch()) !=
nullptr) {
473 it.add_after_then_move(bb);
475 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
476 free_method(it.data());
485 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
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);
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);
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);
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)
551 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
554 rsearch.StartRectSearch(rect);
555 return rsearch.NextRectSearch() ==
nullptr;
560 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
562 auto* 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);
579 grid_->HandleClick(sv_event->
x, sv_event->
y);
588 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
590 int x,
int y,
const char* window_name) {
592 #ifndef GRAPHICS_DISABLED
594 tright_.x() - bleft_.x(),
595 tright_.y() - bleft_.y(),
596 tright_.x() - bleft_.x(),
597 tright_.y() - bleft_.y(),
603 tab_win->
Rectangle(0, 0, tright_.x() - bleft_.x(), tright_.y() - bleft_.y());
612 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
614 #ifndef GRAPHICS_DISABLED
620 gsearch.StartFullSearch();
622 while ((bbox = gsearch.NextFullSearch()) !=
nullptr) {
623 const 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();
629 tab_win->
Pen(box_color);
630 tab_win->
Rectangle(left_x, bottom_y, right_x, top_y);
637 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
640 for (
int i = gridwidth_ * gridheight_ - 1; i >= 0; --i) {
642 for (BBC_C_IT it(&grid_[i]); !it.at_last(); it.forward()) {
643 BBC* ptr = it.data();
646 for (it2.forward(); !it2.at_first(); it2.forward()) {
654 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
656 tprintf(
"Click at (%d, %d)\n", x, y);
664 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
668 CommonStart(grid_->bleft_.x(), grid_->tright_.y());
674 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
679 while (it_.cycled_list()) {
681 if (x_ >= grid_->gridwidth_) {
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_;
697 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
703 max_radius_ = max_radius;
712 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
715 while (it_.cycled_list()) {
717 if (rad_index_ >= radius_) {
722 if (radius_ > max_radius_)
728 offset *= radius_ - 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_)
737 }
while (unique_mode_ && returns_.find(previous_return_) != returns_.end());
739 returns_.insert(previous_return_);
740 return previous_return_;
745 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
747 int ymin,
int ymax) {
752 radius_ = ((ymax - ymin) * 2 + grid_->gridsize_ - 1) / grid_->gridsize_;
754 CommonStart(x, ymax);
760 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
763 while (it_.cycled_list()) {
765 if (rad_index_ > radius_) {
771 if (x_ < 0 || x_ >= grid_->gridwidth_)
774 y_ = y_origin_ - rad_index_;
775 if (y_ >= 0 && y_ < grid_->gridheight_)
779 }
while (unique_mode_ && returns_.find(previous_return_) != returns_.end());
781 returns_.insert(previous_return_);
782 return previous_return_;
787 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
793 radius_ = (xmax - xmin + grid_->gridsize_ - 1) / grid_->gridsize_;
795 CommonStart(xmin, y);
801 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
803 bool top_to_bottom) {
805 while (it_.cycled_list()) {
807 if (rad_index_ > radius_) {
813 if (y_ < 0 || y_ >= grid_->gridheight_)
816 x_ = x_origin_ + rad_index_;
817 if (x_ >= 0 && x_ < grid_->gridwidth_)
821 }
while (unique_mode_ && returns_.find(previous_return_) != returns_.end());
823 returns_.insert(previous_return_);
824 return previous_return_;
829 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
835 CommonStart(rect.
left(), rect.
top());
837 &max_radius_, &y_origin_);
841 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
844 while (it_.cycled_list()) {
846 if (x_ > max_radius_) {
855 }
while (!rect_.overlap(previous_return_->bounding_box()) ||
856 (unique_mode_ && returns_.find(previous_return_) != returns_.end()));
858 returns_.insert(previous_return_);
859 return previous_return_;
865 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
867 if (previous_return_ !=
nullptr) {
871 BBC* prev_data =
nullptr;
872 BBC* new_previous_return =
nullptr;
874 for (it_.mark_cycle_pt(); !it_.cycled_list();) {
875 if (it_.data() == previous_return_) {
876 new_previous_return = prev_data;
879 next_return_ = it_.cycled_list() ? nullptr : it_.data();
881 prev_data = it_.data();
886 previous_return_ = new_previous_return;
887 RepositionIterator();
891 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
903 if (!it_.empty() && it_.data() == next_return_) {
907 for (it_.mark_cycle_pt(); !it_.cycled_list(); it_.forward()) {
908 if (it_.data() == previous_return_ ||
909 it_.data_relative(1) == next_return_) {
915 previous_return_ =
nullptr;
916 next_return_ =
nullptr;
920 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
922 grid_->GridCoords(x, y, &x_origin_, &y_origin_);
926 previous_return_ =
nullptr;
927 next_return_ = it_.empty() ? nullptr : it_.data();
932 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
933 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonNext() {
934 previous_return_ = it_.data();
936 next_return_ = it_.cycled_list() ? nullptr : it_.data();
937 return previous_return_;
941 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
942 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonEnd() {
943 previous_return_ =
nullptr;
944 next_return_ =
nullptr;
950 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
951 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::SetIterator() {
952 it_= &(grid_->grid_[y_ * grid_->gridwidth_ + x_]);
958 #endif // TESSERACT_TEXTORD_BBGRID_H_