Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
rect.h
Go to the documentation of this file.
1 /**********************************************************************
2  * File: rect.h (Formerly box.h)
3  * Description: Bounding box class definition.
4  * Author: Phil Cheatle
5  * Created: Wed Oct 16 15:18:45 BST 1991
6  *
7  * (C) Copyright 1991, Hewlett-Packard Ltd.
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 RECT_H
21 #define RECT_H
22 
23 #include <math.h>
24 #include "points.h"
25 #include "ndminx.h"
26 #include "scrollview.h"
27 #include "tprintf.h"
28 
29 class DLLSYM TBOX { // bounding box
30  public:
31  TBOX (): // empty constructor making a null box
32  bot_left (MAX_INT16, MAX_INT16), top_right (-MAX_INT16, -MAX_INT16) {
33  }
34 
35  TBOX( // constructor
36  const ICOORD pt1, // one corner
37  const ICOORD pt2); // the other corner
38 
39  TBOX( // constructor
40  inT16 left, inT16 bottom, inT16 right, inT16 top);
41 
42  TBOX( // box around FCOORD
43  const FCOORD pt);
44 
45  bool null_box() const { // Is box null
46  return ((left () >= right ()) || (top () <= bottom ()));
47  }
48 
49  bool operator==(const TBOX& other) const {
50  return bot_left == other.bot_left && top_right == other.top_right;
51  }
52 
53  inT16 top() const { // coord of top
54  return top_right.y ();
55  }
56  void set_top(int y) {
57  top_right.set_y(y);
58  }
59 
60  inT16 bottom() const { // coord of bottom
61  return bot_left.y ();
62  }
63  void set_bottom(int y) {
64  bot_left.set_y(y);
65  }
66 
67  inT16 left() const { // coord of left
68  return bot_left.x ();
69  }
70  void set_left(int x) {
71  bot_left.set_x(x);
72  }
73 
74  inT16 right() const { // coord of right
75  return top_right.x ();
76  }
77  void set_right(int x) {
78  top_right.set_x(x);
79  }
80 
81  const ICOORD &botleft() const { // access function
82  return bot_left;
83  }
84 
85  ICOORD botright() const { // ~ access function
86  return ICOORD (top_right.x (), bot_left.y ());
87  }
88 
89  ICOORD topleft() const { // ~ access function
90  return ICOORD (bot_left.x (), top_right.y ());
91  }
92 
93  const ICOORD &topright() const { // access function
94  return top_right;
95  }
96 
97  inT16 height() const { // how high is it?
98  if (!null_box ())
99  return top_right.y () - bot_left.y ();
100  else
101  return 0;
102  }
103 
104  inT16 width() const { // how high is it?
105  if (!null_box ())
106  return top_right.x () - bot_left.x ();
107  else
108  return 0;
109  }
110 
111  inT32 area() const { // what is the area?
112  if (!null_box ())
113  return width () * height ();
114  else
115  return 0;
116  }
117 
118  // Pads the box on either side by the supplied x,y pad amounts.
119  // NO checks for exceeding any bounds like 0 or an image size.
120  void pad(int xpad, int ypad) {
121  ICOORD pad(xpad, ypad);
122  bot_left -= pad;
123  top_right += pad;
124  }
125 
126  void move_bottom_edge( // move one edge
127  const inT16 y) { // by +/- y
128  bot_left += ICOORD (0, y);
129  }
130 
131  void move_left_edge( // move one edge
132  const inT16 x) { // by +/- x
133  bot_left += ICOORD (x, 0);
134  }
135 
136  void move_right_edge( // move one edge
137  const inT16 x) { // by +/- x
138  top_right += ICOORD (x, 0);
139  }
140 
141  void move_top_edge( // move one edge
142  const inT16 y) { // by +/- y
143  top_right += ICOORD (0, y);
144  }
145 
146  void move( // move box
147  const ICOORD vec) { // by vector
148  bot_left += vec;
149  top_right += vec;
150  }
151 
152  void move( // move box
153  const FCOORD vec) { // by float vector
154  bot_left.set_x ((inT16) floor (bot_left.x () + vec.x ()));
155  // round left
156  bot_left.set_y ((inT16) floor (bot_left.y () + vec.y ()));
157  // round down
158  top_right.set_x ((inT16) ceil (top_right.x () + vec.x ()));
159  // round right
160  top_right.set_y ((inT16) ceil (top_right.y () + vec.y ()));
161  // round up
162  }
163 
164  void scale( // scale box
165  const float f) { // by multiplier
166  bot_left.set_x ((inT16) floor (bot_left.x () * f)); // round left
167  bot_left.set_y ((inT16) floor (bot_left.y () * f)); // round down
168  top_right.set_x ((inT16) ceil (top_right.x () * f)); // round right
169  top_right.set_y ((inT16) ceil (top_right.y () * f)); // round up
170  }
171  void scale( // scale box
172  const FCOORD vec) { // by float vector
173  bot_left.set_x ((inT16) floor (bot_left.x () * vec.x ()));
174  bot_left.set_y ((inT16) floor (bot_left.y () * vec.y ()));
175  top_right.set_x ((inT16) ceil (top_right.x () * vec.x ()));
176  top_right.set_y ((inT16) ceil (top_right.y () * vec.y ()));
177  }
178 
179  // rotate doesn't enlarge the box - it just rotates the bottom-left
180  // and top-right corners. Use rotate_large if you want to guarantee
181  // that all content is contained within the rotated box.
182  void rotate(const FCOORD& vec) { // by vector
183  bot_left.rotate (vec);
184  top_right.rotate (vec);
185  *this = TBOX (bot_left, top_right);
186  }
187  // rotate_large constructs the containing bounding box of all 4
188  // corners after rotating them. It therefore guarantees that all
189  // original content is contained within, but also slightly enlarges the box.
190  void rotate_large(const FCOORD& vec);
191 
192  bool contains( // is pt inside box
193  const FCOORD pt) const;
194 
195  bool contains( // is box inside box
196  const TBOX &box) const;
197 
198  bool overlap( // do boxes overlap
199  const TBOX &box) const;
200 
201  bool major_overlap( // do boxes overlap more than half
202  const TBOX &box) const;
203 
204  // Do boxes overlap on x axis.
205  bool x_overlap(const TBOX &box) const;
206 
207  // Return the horizontal gap between the boxes. If the boxes
208  // overlap horizontally then the return value is negative, indicating
209  // the amount of the overlap.
210  int x_gap(const TBOX& box) const {
211  return MAX(bot_left.x(), box.bot_left.x()) -
212  MIN(top_right.x(), box.top_right.x());
213  }
214 
215  // Return the vertical gap between the boxes. If the boxes
216  // overlap vertically then the return value is negative, indicating
217  // the amount of the overlap.
218  int y_gap(const TBOX& box) const {
219  return MAX(bot_left.y(), box.bot_left.y()) -
220  MIN(top_right.y(), box.top_right.y());
221  }
222 
223  // Do boxes overlap on x axis by more than
224  // half of the width of the narrower box.
225  bool major_x_overlap(const TBOX &box) const;
226 
227  // Do boxes overlap on y axis.
228  bool y_overlap(const TBOX &box) const;
229 
230  // Do boxes overlap on y axis by more than
231  // half of the height of the shorter box.
232  bool major_y_overlap(const TBOX &box) const;
233 
234  // fraction of current box's area covered by other
235  double overlap_fraction(const TBOX &box) const;
236 
237  // fraction of the current box's projected area covered by the other's
238  double x_overlap_fraction(const TBOX& box) const;
239 
240  // fraction of the current box's projected area covered by the other's
241  double y_overlap_fraction(const TBOX& box) const;
242 
243  // Returns true if the boxes are almost equal on x axis.
244  bool x_almost_equal(const TBOX &box, int tolerance) const;
245 
246  // Returns true if the boxes are almost equal
247  bool almost_equal(const TBOX &box, int tolerance) const;
248 
249  TBOX intersection( // shared area box
250  const TBOX &box) const;
251 
252  TBOX bounding_union( // box enclosing both
253  const TBOX &box) const;
254 
255  // Sets the box boundaries to the given coordinates.
256  void set_to_given_coords(int x_min, int y_min, int x_max, int y_max) {
257  bot_left.set_x(x_min);
258  bot_left.set_y(y_min);
259  top_right.set_x(x_max);
260  top_right.set_y(y_max);
261  }
262 
263  void print() const { // print
264  tprintf("Bounding box=(%d,%d)->(%d,%d)\n",
265  left(), bottom(), right(), top());
266  }
267 
268  // Same as print(), but appends debug information to the given string
269  // instead of printing it to stdout.
270  void append_debug(STRING *str) const {
271  char buffer[256];
272  sprintf(buffer, "Bounding box=(%d,%d)->(%d,%d)\n",
273  left(), bottom(), right(), top());
274  *str += buffer;
275  }
276 
277 #ifndef GRAPHICS_DISABLED
278  void plot( // use current settings
279  ScrollView* fd) const { // where to paint
280  fd->Rectangle(bot_left.x (), bot_left.y (), top_right.x (),
281  top_right.y ());
282  }
283 
284  void plot( // paint box
285  ScrollView* fd, // where to paint
286  ScrollView::Color fill_colour, // colour for inside
287  ScrollView::Color border_colour) const; // colour for border
288 #endif
289  // Writes to the given file. Returns false in case of error.
290  bool Serialize(FILE* fp) const;
291  // Reads from the given file. Returns false in case of error.
292  // If swap is true, assumes a big/little-endian swap is needed.
293  bool DeSerialize(bool swap, FILE* fp);
294 
295  friend TBOX& operator+=(TBOX&, const TBOX&);
296  // in place union
297  friend TBOX& operator&=(TBOX&, const TBOX&);
298  // in place intersection
299 
300  private:
301  ICOORD bot_left; // bottom left corner
302  ICOORD top_right; // top right corner
303 };
304 
305 /**********************************************************************
306  * TBOX::TBOX() Constructor from 1 FCOORD
307  *
308  **********************************************************************/
309 
310 inline TBOX::TBOX( // construtor
311  const FCOORD pt // floating centre
312  ) {
313  bot_left = ICOORD ((inT16) floor (pt.x ()), (inT16) floor (pt.y ()));
314  top_right = ICOORD ((inT16) ceil (pt.x ()), (inT16) ceil (pt.y ()));
315 }
316 
317 
318 /**********************************************************************
319  * TBOX::contains() Is point within box
320  *
321  **********************************************************************/
322 
323 inline bool TBOX::contains(const FCOORD pt) const {
324  return ((pt.x () >= bot_left.x ()) &&
325  (pt.x () <= top_right.x ()) &&
326  (pt.y () >= bot_left.y ()) && (pt.y () <= top_right.y ()));
327 }
328 
329 
330 /**********************************************************************
331  * TBOX::contains() Is box within box
332  *
333  **********************************************************************/
334 
335 inline bool TBOX::contains(const TBOX &box) const {
336  return (contains (box.bot_left) && contains (box.top_right));
337 }
338 
339 
340 /**********************************************************************
341  * TBOX::overlap() Do two boxes overlap?
342  *
343  **********************************************************************/
344 
345 inline bool TBOX::overlap( // do boxes overlap
346  const TBOX &box) const {
347  return ((box.bot_left.x () <= top_right.x ()) &&
348  (box.top_right.x () >= bot_left.x ()) &&
349  (box.bot_left.y () <= top_right.y ()) &&
350  (box.top_right.y () >= bot_left.y ()));
351 }
352 
353 /**********************************************************************
354  * TBOX::major_overlap() Do two boxes overlap by at least half of the smallest?
355  *
356  **********************************************************************/
357 
358 inline bool TBOX::major_overlap( // Do boxes overlap more that half.
359  const TBOX &box) const {
360  int overlap = MIN(box.top_right.x(), top_right.x());
361  overlap -= MAX(box.bot_left.x(), bot_left.x());
362  overlap += overlap;
363  if (overlap < MIN(box.width(), width()))
364  return false;
365  overlap = MIN(box.top_right.y(), top_right.y());
366  overlap -= MAX(box.bot_left.y(), bot_left.y());
367  overlap += overlap;
368  if (overlap < MIN(box.height(), height()))
369  return false;
370  return true;
371 }
372 
373 /**********************************************************************
374  * TBOX::overlap_fraction() Fraction of area covered by the other box
375  *
376  **********************************************************************/
377 
378 inline double TBOX::overlap_fraction(const TBOX &box) const {
379  double fraction = 0.0;
380  if (this->area()) {
381  fraction = this->intersection(box).area() * 1.0 / this->area();
382  }
383  return fraction;
384 }
385 
386 /**********************************************************************
387  * TBOX::x_overlap() Do two boxes overlap on x-axis
388  *
389  **********************************************************************/
390 
391 inline bool TBOX::x_overlap(const TBOX &box) const {
392  return ((box.bot_left.x() <= top_right.x()) &&
393  (box.top_right.x() >= bot_left.x()));
394 }
395 
396 /**********************************************************************
397  * TBOX::major_x_overlap() Do two boxes overlap by more than half the
398  * width of the narrower box on the x-axis
399  *
400  **********************************************************************/
401 
402 inline bool TBOX::major_x_overlap(const TBOX &box) const {
403  inT16 overlap = box.width();
404  if (this->left() > box.left()) {
405  overlap -= this->left() - box.left();
406  }
407  if (this->right() < box.right()) {
408  overlap -= box.right() - this->right();
409  }
410  return (overlap >= box.width() / 2 || overlap >= this->width() / 2);
411 }
412 
413 /**********************************************************************
414  * TBOX::y_overlap() Do two boxes overlap on y-axis
415  *
416  **********************************************************************/
417 
418 inline bool TBOX::y_overlap(const TBOX &box) const {
419  return ((box.bot_left.y() <= top_right.y()) &&
420  (box.top_right.y() >= bot_left.y()));
421 }
422 
423 /**********************************************************************
424  * TBOX::major_y_overlap() Do two boxes overlap by more than half the
425  * height of the shorter box on the y-axis
426  *
427  **********************************************************************/
428 
429 inline bool TBOX::major_y_overlap(const TBOX &box) const {
430  inT16 overlap = box.height();
431  if (this->bottom() > box.bottom()) {
432  overlap -= this->bottom() - box.bottom();
433  }
434  if (this->top() < box.top()) {
435  overlap -= box.top() - this->top();
436  }
437  return (overlap >= box.height() / 2 || overlap >= this->height() / 2);
438 }
439 
440 /**********************************************************************
441  * TBOX::x_overlap_fraction() Calculates the horizontal overlap of the
442  * given boxes as a fraction of this boxes
443  * width.
444  *
445  **********************************************************************/
446 
447 inline double TBOX::x_overlap_fraction(const TBOX& other) const {
448  int low = MAX(left(), other.left());
449  int high = MIN(right(), other.right());
450  int width = right() - left();
451  if (width == 0) {
452  int x = left();
453  if (other.left() <= x && x <= other.right())
454  return 1.0;
455  else
456  return 0.0;
457  } else {
458  return MAX(0, static_cast<double>(high - low) / width);
459  }
460 }
461 
462 /**********************************************************************
463  * TBOX::y_overlap_fraction() Calculates the vertical overlap of the
464  * given boxes as a fraction of this boxes
465  * height.
466  *
467  **********************************************************************/
468 
469 inline double TBOX::y_overlap_fraction(const TBOX& other) const {
470  int low = MAX(bottom(), other.bottom());
471  int high = MIN(top(), other.top());
472  int height = top() - bottom();
473  if (height == 0) {
474  int y = bottom();
475  if (other.bottom() <= y && y <= other.top())
476  return 1.0;
477  else
478  return 0.0;
479  } else {
480  return MAX(0, static_cast<double>(high - low) / height);
481  }
482 }
483 
484 #endif