Tesseract  3.02
tesseract-ocr/ccstruct/rect.h
Go to the documentation of this file.
00001 /**********************************************************************
00002  * File:        rect.h  (Formerly box.h)
00003  * Description: Bounding box class definition.
00004  * Author:                                      Phil Cheatle
00005  * Created:                                     Wed Oct 16 15:18:45 BST 1991
00006  *
00007  * (C) Copyright 1991, Hewlett-Packard Ltd.
00008  ** Licensed under the Apache License, Version 2.0 (the "License");
00009  ** you may not use this file except in compliance with the License.
00010  ** You may obtain a copy of the License at
00011  ** http://www.apache.org/licenses/LICENSE-2.0
00012  ** Unless required by applicable law or agreed to in writing, software
00013  ** distributed under the License is distributed on an "AS IS" BASIS,
00014  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00015  ** See the License for the specific language governing permissions and
00016  ** limitations under the License.
00017  *
00018  **********************************************************************/
00019 
00020 #ifndef           RECT_H
00021 #define           RECT_H
00022 
00023 #include <math.h>
00024 #include "points.h"
00025 #include "ndminx.h"
00026 #include "scrollview.h"
00027 #include "tprintf.h"
00028 
00029 class DLLSYM TBOX  {  // bounding box
00030   public:
00031     TBOX ():       // empty constructor making a null box
00032     bot_left (MAX_INT16, MAX_INT16), top_right (-MAX_INT16, -MAX_INT16) {
00033     }
00034 
00035     TBOX(          // constructor
00036         const ICOORD pt1,   // one corner
00037         const ICOORD pt2);  // the other corner
00038 
00039     TBOX(                    // constructor
00040         inT16 left, inT16 bottom, inT16 right, inT16 top);
00041 
00042     TBOX(  // box around FCOORD
00043         const FCOORD pt);
00044 
00045     bool null_box() const {  // Is box null
00046       return ((left () >= right ()) || (top () <= bottom ()));
00047     }
00048 
00049     bool operator==(const TBOX& other) const {
00050       return bot_left == other.bot_left && top_right == other.top_right;
00051     }
00052 
00053     inT16 top() const {  // coord of top
00054       return top_right.y ();
00055     }
00056     void set_top(int y) {
00057       top_right.set_y(y);
00058     }
00059 
00060     inT16 bottom() const {  // coord of bottom
00061       return bot_left.y ();
00062     }
00063     void set_bottom(int y) {
00064       bot_left.set_y(y);
00065     }
00066 
00067     inT16 left() const {  // coord of left
00068       return bot_left.x ();
00069     }
00070     void set_left(int x) {
00071       bot_left.set_x(x);
00072     }
00073 
00074     inT16 right() const {  // coord of right
00075       return top_right.x ();
00076     }
00077     void set_right(int x) {
00078       top_right.set_x(x);
00079     }
00080 
00081     const ICOORD &botleft() const {  // access function
00082       return bot_left;
00083     }
00084 
00085     ICOORD botright() const {  // ~ access function
00086       return ICOORD (top_right.x (), bot_left.y ());
00087     }
00088 
00089     ICOORD topleft() const {  // ~ access function
00090       return ICOORD (bot_left.x (), top_right.y ());
00091     }
00092 
00093     const ICOORD &topright() const {  // access function
00094       return top_right;
00095     }
00096 
00097     inT16 height() const {  // how high is it?
00098       if (!null_box ())
00099         return top_right.y () - bot_left.y ();
00100       else
00101         return 0;
00102     }
00103 
00104     inT16 width() const {  // how high is it?
00105       if (!null_box ())
00106         return top_right.x () - bot_left.x ();
00107       else
00108         return 0;
00109     }
00110 
00111     inT32 area() const {  // what is the area?
00112       if (!null_box ())
00113         return width () * height ();
00114       else
00115         return 0;
00116     }
00117 
00118     // Pads the box on either side by the supplied x,y pad amounts.
00119     // NO checks for exceeding any bounds like 0 or an image size.
00120     void pad(int xpad, int ypad) {
00121       ICOORD pad(xpad, ypad);
00122       bot_left -= pad;
00123       top_right += pad;
00124     }
00125 
00126     void move_bottom_edge(                  // move one edge
00127                           const inT16 y) {  // by +/- y
00128       bot_left += ICOORD (0, y);
00129     }
00130 
00131     void move_left_edge(                  // move one edge
00132                         const inT16 x) {  // by +/- x
00133       bot_left += ICOORD (x, 0);
00134     }
00135 
00136     void move_right_edge(                  // move one edge
00137                          const inT16 x) {  // by +/- x
00138       top_right += ICOORD (x, 0);
00139     }
00140 
00141     void move_top_edge(                  // move one edge
00142                        const inT16 y) {  // by +/- y
00143       top_right += ICOORD (0, y);
00144     }
00145 
00146     void move(                     // move box
00147               const ICOORD vec) {  // by vector
00148       bot_left += vec;
00149       top_right += vec;
00150     }
00151 
00152     void move(                     // move box
00153               const FCOORD vec) {  // by float vector
00154       bot_left.set_x ((inT16) floor (bot_left.x () + vec.x ()));
00155       // round left
00156       bot_left.set_y ((inT16) floor (bot_left.y () + vec.y ()));
00157       // round down
00158       top_right.set_x ((inT16) ceil (top_right.x () + vec.x ()));
00159       // round right
00160       top_right.set_y ((inT16) ceil (top_right.y () + vec.y ()));
00161       // round up
00162     }
00163 
00164     void scale(                  // scale box
00165                const float f) {  // by multiplier
00166       bot_left.set_x ((inT16) floor (bot_left.x () * f));  // round left
00167       bot_left.set_y ((inT16) floor (bot_left.y () * f));  // round down
00168       top_right.set_x ((inT16) ceil (top_right.x () * f));  // round right
00169       top_right.set_y ((inT16) ceil (top_right.y () * f));  // round up
00170     }
00171     void scale(                     // scale box
00172                const FCOORD vec) {  // by float vector
00173       bot_left.set_x ((inT16) floor (bot_left.x () * vec.x ()));
00174       bot_left.set_y ((inT16) floor (bot_left.y () * vec.y ()));
00175       top_right.set_x ((inT16) ceil (top_right.x () * vec.x ()));
00176       top_right.set_y ((inT16) ceil (top_right.y () * vec.y ()));
00177     }
00178 
00179     // rotate doesn't enlarge the box - it just rotates the bottom-left
00180     // and top-right corners. Use rotate_large if you want to guarantee
00181     // that all content is contained within the rotated box.
00182     void rotate(const FCOORD& vec) {  // by vector
00183       bot_left.rotate (vec);
00184       top_right.rotate (vec);
00185       *this = TBOX (bot_left, top_right);
00186     }
00187     // rotate_large constructs the containing bounding box of all 4
00188     // corners after rotating them. It therefore guarantees that all
00189     // original content is contained within, but also slightly enlarges the box.
00190     void rotate_large(const FCOORD& vec);
00191 
00192     bool contains(  // is pt inside box
00193                    const FCOORD pt) const;
00194 
00195     bool contains(  // is box inside box
00196                    const TBOX &box) const;
00197 
00198     bool overlap(  // do boxes overlap
00199                   const TBOX &box) const;
00200 
00201     bool major_overlap(  // do boxes overlap more than half
00202                         const TBOX &box) const;
00203 
00204     // Do boxes overlap on x axis.
00205     bool x_overlap(const TBOX &box) const;
00206 
00207     // Return the horizontal gap between the boxes. If the boxes
00208     // overlap horizontally then the return value is negative, indicating
00209     // the amount of the overlap.
00210     int x_gap(const TBOX& box) const {
00211       return MAX(bot_left.x(), box.bot_left.x()) -
00212              MIN(top_right.x(), box.top_right.x());
00213     }
00214 
00215     // Return the vertical gap between the boxes. If the boxes
00216     // overlap vertically then the return value is negative, indicating
00217     // the amount of the overlap.
00218     int y_gap(const TBOX& box) const {
00219       return MAX(bot_left.y(), box.bot_left.y()) -
00220              MIN(top_right.y(), box.top_right.y());
00221     }
00222 
00223     // Do boxes overlap on x axis by more than
00224     // half of the width of the narrower box.
00225     bool major_x_overlap(const TBOX &box) const;
00226 
00227     // Do boxes overlap on y axis.
00228     bool y_overlap(const TBOX &box) const;
00229 
00230     // Do boxes overlap on y axis by more than
00231     // half of the height of the shorter box.
00232     bool major_y_overlap(const TBOX &box) const;
00233 
00234     // fraction of current box's area covered by other
00235     double overlap_fraction(const TBOX &box) const;
00236 
00237     // fraction of the current box's projected area covered by the other's
00238     double x_overlap_fraction(const TBOX& box) const;
00239 
00240     // fraction of the current box's projected area covered by the other's
00241     double y_overlap_fraction(const TBOX& box) const;
00242 
00243     // Returns true if the boxes are almost equal on x axis.
00244     bool x_almost_equal(const TBOX &box, int tolerance) const;
00245 
00246     // Returns true if the boxes are almost equal
00247     bool almost_equal(const TBOX &box, int tolerance) const;
00248 
00249     TBOX intersection(  // shared area box
00250                      const TBOX &box) const;
00251 
00252     TBOX bounding_union(  // box enclosing both
00253                        const TBOX &box) const;
00254 
00255     // Sets the box boundaries to the given coordinates.
00256     void set_to_given_coords(int x_min, int y_min, int x_max, int y_max) {
00257       bot_left.set_x(x_min);
00258       bot_left.set_y(y_min);
00259       top_right.set_x(x_max);
00260       top_right.set_y(y_max);
00261     }
00262 
00263     void print() const {  // print
00264       tprintf("Bounding box=(%d,%d)->(%d,%d)\n",
00265               left(), bottom(), right(), top());
00266     }
00267 
00268     // Same as print(), but appends debug information to the given string
00269     // instead of printing it to stdout.
00270     void append_debug(STRING *str) const {
00271       char buffer[256];
00272       sprintf(buffer, "Bounding box=(%d,%d)->(%d,%d)\n",
00273               left(), bottom(), right(), top());
00274       *str += buffer;
00275     }
00276 
00277 #ifndef GRAPHICS_DISABLED
00278     void plot(                    // use current settings
00279               ScrollView* fd) const {  // where to paint
00280       fd->Rectangle(bot_left.x (), bot_left.y (), top_right.x (),
00281         top_right.y ());
00282     }
00283 
00284     void plot(                              // paint box
00285               ScrollView* fd,                    // where to paint
00286               ScrollView::Color fill_colour,           // colour for inside
00287               ScrollView::Color border_colour) const;  // colour for border
00288 #endif
00289     // Writes to the given file. Returns false in case of error.
00290     bool Serialize(FILE* fp) const;
00291     // Reads from the given file. Returns false in case of error.
00292     // If swap is true, assumes a big/little-endian swap is needed.
00293     bool DeSerialize(bool swap, FILE* fp);
00294 
00295     friend TBOX& operator+=(TBOX&, const TBOX&);
00296     // in place union
00297     friend TBOX& operator&=(TBOX&, const TBOX&);
00298     // in place intersection
00299 
00300   private:
00301     ICOORD bot_left;             // bottom left corner
00302     ICOORD top_right;            // top right corner
00303 };
00304 
00305 /**********************************************************************
00306  * TBOX::TBOX()  Constructor from 1 FCOORD
00307  *
00308  **********************************************************************/
00309 
00310 inline TBOX::TBOX(               // construtor
00311                 const FCOORD pt  // floating centre
00312                ) {
00313   bot_left = ICOORD ((inT16) floor (pt.x ()), (inT16) floor (pt.y ()));
00314   top_right = ICOORD ((inT16) ceil (pt.x ()), (inT16) ceil (pt.y ()));
00315 }
00316 
00317 
00318 /**********************************************************************
00319  * TBOX::contains()  Is point within box
00320  *
00321  **********************************************************************/
00322 
00323 inline bool TBOX::contains(const FCOORD pt) const {
00324   return ((pt.x () >= bot_left.x ()) &&
00325     (pt.x () <= top_right.x ()) &&
00326     (pt.y () >= bot_left.y ()) && (pt.y () <= top_right.y ()));
00327 }
00328 
00329 
00330 /**********************************************************************
00331  * TBOX::contains()  Is box within box
00332  *
00333  **********************************************************************/
00334 
00335 inline bool TBOX::contains(const TBOX &box) const {
00336   return (contains (box.bot_left) && contains (box.top_right));
00337 }
00338 
00339 
00340 /**********************************************************************
00341  * TBOX::overlap()  Do two boxes overlap?
00342  *
00343  **********************************************************************/
00344 
00345 inline bool TBOX::overlap(  // do boxes overlap
00346                           const TBOX &box) const {
00347   return ((box.bot_left.x () <= top_right.x ()) &&
00348     (box.top_right.x () >= bot_left.x ()) &&
00349     (box.bot_left.y () <= top_right.y ()) &&
00350     (box.top_right.y () >= bot_left.y ()));
00351 }
00352 
00353 /**********************************************************************
00354  * TBOX::major_overlap()  Do two boxes overlap by at least half of the smallest?
00355  *
00356  **********************************************************************/
00357 
00358 inline bool TBOX::major_overlap(  // Do boxes overlap more that half.
00359                                 const TBOX &box) const {
00360   int overlap = MIN(box.top_right.x(), top_right.x());
00361   overlap -= MAX(box.bot_left.x(), bot_left.x());
00362   overlap += overlap;
00363   if (overlap < MIN(box.width(), width()))
00364     return false;
00365   overlap = MIN(box.top_right.y(), top_right.y());
00366   overlap -= MAX(box.bot_left.y(), bot_left.y());
00367   overlap += overlap;
00368   if (overlap < MIN(box.height(), height()))
00369     return false;
00370   return true;
00371 }
00372 
00373 /**********************************************************************
00374  * TBOX::overlap_fraction()  Fraction of area covered by the other box
00375  *
00376  **********************************************************************/
00377 
00378 inline double TBOX::overlap_fraction(const TBOX &box) const {
00379   double fraction = 0.0;
00380   if (this->area()) {
00381     fraction = this->intersection(box).area() * 1.0 / this->area();
00382   }
00383   return fraction;
00384 }
00385 
00386 /**********************************************************************
00387  * TBOX::x_overlap()  Do two boxes overlap on x-axis
00388  *
00389  **********************************************************************/
00390 
00391 inline bool TBOX::x_overlap(const TBOX &box) const {
00392   return ((box.bot_left.x() <= top_right.x()) &&
00393     (box.top_right.x() >= bot_left.x()));
00394 }
00395 
00396 /**********************************************************************
00397  * TBOX::major_x_overlap()  Do two boxes overlap by more than half the
00398  *                          width of the narrower box on the x-axis
00399  *
00400  **********************************************************************/
00401 
00402 inline bool TBOX::major_x_overlap(const TBOX &box) const {
00403   inT16 overlap = box.width();
00404   if (this->left() > box.left()) {
00405     overlap -= this->left() - box.left();
00406   }
00407   if (this->right() < box.right()) {
00408     overlap -= box.right() - this->right();
00409   }
00410   return (overlap >= box.width() / 2 || overlap >= this->width() / 2);
00411 }
00412 
00413 /**********************************************************************
00414  * TBOX::y_overlap()  Do two boxes overlap on y-axis
00415  *
00416  **********************************************************************/
00417 
00418 inline bool TBOX::y_overlap(const TBOX &box) const {
00419   return ((box.bot_left.y() <= top_right.y()) &&
00420     (box.top_right.y() >= bot_left.y()));
00421 }
00422 
00423 /**********************************************************************
00424  * TBOX::major_y_overlap()  Do two boxes overlap by more than half the
00425  *                          height of the shorter box on the y-axis
00426  *
00427  **********************************************************************/
00428 
00429 inline bool TBOX::major_y_overlap(const TBOX &box) const {
00430   inT16 overlap = box.height();
00431   if (this->bottom() > box.bottom()) {
00432     overlap -= this->bottom() - box.bottom();
00433   }
00434   if (this->top() < box.top()) {
00435     overlap -= box.top() - this->top();
00436   }
00437   return (overlap >= box.height() / 2 || overlap >= this->height() / 2);
00438 }
00439 
00440 /**********************************************************************
00441  * TBOX::x_overlap_fraction() Calculates the horizontal overlap of the
00442  *                            given boxes as a fraction of this boxes
00443  *                            width.
00444  *
00445  **********************************************************************/
00446 
00447 inline double TBOX::x_overlap_fraction(const TBOX& other) const {
00448   int low = MAX(left(), other.left());
00449   int high = MIN(right(), other.right());
00450   int width = right() - left();
00451   if (width == 0) {
00452     int x = left();
00453     if (other.left() <= x && x <= other.right())
00454       return 1.0;
00455     else
00456       return 0.0;
00457   } else {
00458     return MAX(0, static_cast<double>(high - low) / width);
00459   }
00460 }
00461 
00462 /**********************************************************************
00463  * TBOX::y_overlap_fraction() Calculates the vertical overlap of the
00464  *                            given boxes as a fraction of this boxes
00465  *                            height.
00466  *
00467  **********************************************************************/
00468 
00469 inline double TBOX::y_overlap_fraction(const TBOX& other) const {
00470   int low = MAX(bottom(), other.bottom());
00471   int high = MIN(top(), other.top());
00472   int height = top() - bottom();
00473   if (height == 0) {
00474     int y = bottom();
00475     if (other.bottom() <= y && y <= other.top())
00476       return 1.0;
00477     else
00478       return 0.0;
00479   } else {
00480     return MAX(0, static_cast<double>(high - low) / height);
00481   }
00482 }
00483 
00484 #endif