21 #ifndef TESSERACT_TEXTORD_BBGRID_H__
22 #define TESSERACT_TEXTORD_BBGRID_H__
32 #include "config_auto.h"
35 #include "allheaders.h"
48 ICOORD bleft,
int* left,
int* bottom);
51 ICOORD bleft,
int* left,
int* bottom);
53 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
class GridSearch;
84 void GridCoords(
int x,
int y,
int* grid_x,
int* grid_y)
const;
163 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
class BBGrid
186 void InsertBBox(
bool h_spread,
bool v_spread, BBC* bbox);
232 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
class GridSearch {
235 : grid_(grid), unique_mode_(false),
236 previous_return_(
NULL), next_return_(
NULL) {
263 TBOX box = previous_return_->bounding_box();
264 int x_center = (box.
left()+box.
right())/2;
265 int y_center = (box.
top()+box.
bottom())/2;
267 grid_->GridCoords(x_center, y_center, &grid_x, &grid_y);
268 return (x_ == grid_x) && (y_ == grid_y);
335 void CommonStart(
int x,
int y);
359 BBC* previous_return_;
371 const BBC* p1 = *
reinterpret_cast<const BBC*
const *
>(void1);
372 const BBC* p2 = *
reinterpret_cast<const BBC*
const *
>(void2);
373 int result = p1->bounding_box().left() - p2->bounding_box().left();
376 result = p1->bounding_box().right() - p2->bounding_box().right();
379 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
382 return p1->bounding_box().top() - p2->bounding_box().top();
389 const BBC* p1 = *
reinterpret_cast<const BBC*
const *
>(void1);
390 const BBC* p2 = *
reinterpret_cast<const BBC*
const *
>(void2);
391 int result = p2->bounding_box().right() - p1->bounding_box().right();
394 result = p2->bounding_box().left() - p1->bounding_box().left();
397 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
400 return p1->bounding_box().top() - p2->bounding_box().top();
407 const BBC* p1 = *
reinterpret_cast<const BBC*
const *
>(void1);
408 const BBC* p2 = *
reinterpret_cast<const BBC*
const *
>(void2);
409 int result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
412 result = p1->bounding_box().top() - p2->bounding_box().top();
415 result = p1->bounding_box().left() - p2->bounding_box().left();
418 return p1->bounding_box().right() - p2->bounding_box().right();
424 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
428 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
430 int gridsize,
const ICOORD& bleft,
const ICOORD& tright)
432 Init(gridsize, bleft, tright);
435 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
443 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
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_ ==
NULL)
return;
471 BBC_C_IT it(&bb_list);
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>
560 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
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();
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
623 TBOX box = bbox->bounding_box();
624 int left_x = box.
left();
625 int right_x = box.
right();
626 int top_y = box.
top();
627 int bottom_y = box.
bottom();
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_ &&
738 !returns_.add_sorted(SortByBoxLeft<BBC>,
true, previous_return_));
739 return previous_return_;
744 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
746 int ymin,
int ymax) {
751 radius_ = ((ymax - ymin) * 2 + grid_->gridsize_ - 1) / grid_->gridsize_;
753 CommonStart(x, ymax);
759 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
762 while (it_.cycled_list()) {
764 if (rad_index_ > radius_) {
770 if (x_ < 0 || x_ >= grid_->gridwidth_)
773 y_ = y_origin_ - rad_index_;
774 if (y_ >= 0 && y_ < grid_->gridheight_)
778 }
while (unique_mode_ &&
779 !returns_.add_sorted(SortByBoxLeft<BBC>,
true, previous_return_));
780 return previous_return_;
785 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
791 radius_ = (xmax - xmin + grid_->gridsize_ - 1) / grid_->gridsize_;
793 CommonStart(xmin, y);
799 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
801 bool top_to_bottom) {
803 while (it_.cycled_list()) {
805 if (rad_index_ > radius_) {
811 if (y_ < 0 || y_ >= grid_->gridheight_)
814 x_ = x_origin_ + rad_index_;
815 if (x_ >= 0 && x_ < grid_->gridwidth_)
819 }
while (unique_mode_ &&
820 !returns_.add_sorted(SortByBoxLeft<BBC>,
true, previous_return_));
821 return previous_return_;
826 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
832 CommonStart(rect.
left(), rect.
top());
834 &max_radius_, &y_origin_);
838 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
841 while (it_.cycled_list()) {
843 if (x_ > max_radius_) {
852 }
while (!rect_.overlap(previous_return_->bounding_box()) ||
854 !returns_.add_sorted(SortByBoxLeft<BBC>,
true, previous_return_)));
855 return previous_return_;
861 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
863 if (previous_return_ !=
NULL) {
867 BBC* prev_data =
NULL;
868 BBC* new_previous_return =
NULL;
870 for (it_.mark_cycle_pt(); !it_.cycled_list();) {
871 if (it_.data() == previous_return_) {
872 new_previous_return = prev_data;
875 next_return_ = it_.cycled_list() ?
NULL : it_.data();
877 prev_data = it_.data();
881 grid_->RemoveBBox(previous_return_);
882 previous_return_ = new_previous_return;
883 RepositionIterator();
887 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
891 returns_.shallow_clear();
899 if (!it_.empty() && it_.data() == next_return_) {
903 for (it_.mark_cycle_pt(); !it_.cycled_list(); it_.forward()) {
904 if (it_.data() == previous_return_ ||
905 it_.data_relative(1) == next_return_) {
911 previous_return_ =
NULL;
916 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
918 grid_->GridCoords(x, y, &x_origin_, &y_origin_);
922 previous_return_ =
NULL;
923 next_return_ = it_.empty() ?
NULL : it_.data();
924 returns_.shallow_clear();
928 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
929 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonNext() {
930 previous_return_ = it_.data();
932 next_return_ = it_.cycled_list() ?
NULL : it_.data();
933 return previous_return_;
937 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
938 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonEnd() {
939 previous_return_ =
NULL;
946 template<
class BBC,
class BBC_CLIST,
class BBC_C_IT>
947 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::SetIterator() {
948 it_= &(grid_->grid_[y_ * grid_->gridwidth_ + x_]);
954 #endif // TESSERACT_TEXTORD_BBGRID_H__