1 //C- -*- C++ -*-
2 //C- -------------------------------------------------------------------
3 //C- DjVuLibre-3.5
4 //C- Copyright (c) 2002 Leon Bottou and Yann Le Cun.
5 //C- Copyright (c) 2001 AT&T
6 //C-
7 //C- This software is subject to, and may be distributed under, the
8 //C- GNU General Public License, either Version 2 of the license,
9 //C- or (at your option) any later version. The license should have
10 //C- accompanied the software or you may obtain a copy of the license
11 //C- from the Free Software Foundation at http://www.fsf.org .
12 //C-
13 //C- This program is distributed in the hope that it will be useful,
14 //C- but WITHOUT ANY WARRANTY; without even the implied warranty of
15 //C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 //C- GNU General Public License for more details.
17 //C-
18 //C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
19 //C- Lizardtech Software. Lizardtech Software has authorized us to
20 //C- replace the original DjVu(r) Reference Library notice by the following
21 //C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
22 //C-
23 //C- ------------------------------------------------------------------
24 //C- | DjVu (r) Reference Library (v. 3.5)
25 //C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
26 //C- | The DjVu Reference Library is protected by U.S. Pat. No.
27 //C- | 6,058,214 and patents pending.
28 //C- |
29 //C- | This software is subject to, and may be distributed under, the
30 //C- | GNU General Public License, either Version 2 of the license,
31 //C- | or (at your option) any later version. The license should have
32 //C- | accompanied the software or you may obtain a copy of the license
33 //C- | from the Free Software Foundation at http://www.fsf.org .
34 //C- |
35 //C- | The computer code originally released by LizardTech under this
36 //C- | license and unmodified by other parties is deemed "the LIZARDTECH
37 //C- | ORIGINAL CODE." Subject to any third party intellectual property
38 //C- | claims, LizardTech grants recipient a worldwide, royalty-free,
39 //C- | non-exclusive license to make, use, sell, or otherwise dispose of
40 //C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
41 //C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
42 //C- | General Public License. This grant only confers the right to
43 //C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
44 //C- | the extent such infringement is reasonably necessary to enable
45 //C- | recipient to make, have made, practice, sell, or otherwise dispose
46 //C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
47 //C- | any greater extent that may be necessary to utilize further
48 //C- | modifications or combinations.
49 //C- |
50 //C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
51 //C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
52 //C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
53 //C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
54 //C- +------------------------------------------------------------------
55
56 #ifndef _GRECT_H_
57 #define _GRECT_H_
58 #ifdef HAVE_CONFIG_H
59 #include "config.h"
60 #endif
61 #if NEED_GNUG_PRAGMAS
62 # pragma interface
63 #endif
64
65
66 /** @name GRect.h
67 Files #"GRect.h"# and #"GRect.cpp"# implement basic operations on
68 rectangles. Class \Ref{GRect} is used to represent rectangles. Class
69 \Ref{GRectMapper} represent the correspondence between points relative to
70 given rectangles. Class \Ref{GRatio} is used to represent scaling factors
71 as rational numbers.
72 @memo
73 Rectangle manipulation class.
74 @author
75 L\'eon Bottou <leonb@research.att.com> -- initial implementation.
76 */
77 //@{
78
79 #include "DjVuGlobal.h"
80
81 #ifdef HAVE_NAMESPACES
82 namespace DJVU {
83 # ifdef NOT_DEFINED // Just to fool emacs c++ mode
84 }
85 #endif
86 #endif
87
88
89 /* Flag to indicate that this djvulibre version
90 gets rid of all the crap about orientation bits.
91 All rotation code has been fixed and consistently
92 implements counter-clockwise rotations. */
93
94 #define GRECT_WITHOUT_ORIENTATION_BITS 1
95
96
97 /** @name Point Coordinates vs. Pixel Coordinates
98
99 The DjVu technology relies on the accurate superposition of images at
100 different resolutions. Such an accuracy cannot be reached with the usual
101 assumption that pixels are small enough to be considered infinitesimally
102 small. We must distinguish very precisely ``points'' and ``pixels''.
103 This distinction is essential for performing scaling operations.
104
105 The pixels of an image are identified by ``pixel coordinates''. The
106 bottom-left corner pixel has coordinates #(0,0)# and the top-right corner
107 pixel has coordinates #(w-1,h-1)# where #w# and #h# are the image size.
108 Pixel coordinates are necessarily integers since pixels never overlap.
109
110 An infinitesimally small point is identified by its ``point coordinates''.
111 There may be fractional point coordinates, although this library does not
112 make use of them. Points with integer coordinates are located {\em on the
113 corners of each pixel}. They are not located on the pixel centers. The
114 center of the pixel with pixel coordinates #(i,j)# is located at point
115 coordinates #(i+1/2,j+1/2)#. In other words, the pixel #(i,j)# extends
116 from point #(i,j)# to point #(i+1,j+1)#.
117
118 Therefore, the point located on the bottom left corner of an image has
119 coordinates #(0,0)#. This point is in fact the bottom left corner of the
120 bottom left pixel of the image. The point located on the top right corner
121 of an image has coordinates #(w,h)# where #w# and #h# are the image size.
122 This is in fact the top right corner of pixel #(w-1,h-1)# which is the
123 image pixel with the highest coordinates.
124 */
125 //@{
126 //@}
127
128
129
130 /** Rectangle class. Each instance of this class represents a rectangle whose
131 sides are parallel to the axis. Such a rectangle represents all the points
132 whose coordinates lies between well defined minimal and maximal values.
133 Member functions can combine several rectangles by computing the
134 intersection of rectangles (\Ref{intersect}) or the smallest rectangle
135 enclosing two rectangles (\Ref{recthull}). */
136
137 class DJVUAPI GRect
138 {
139 public:
140 /** Constructs an empty rectangle */
141 GRect();
142 /** Constructs a rectangle given its minimal coordinates #xmin# and #ymin#,
143 and its measurements #width# and #height#. Setting #width# or #height# to zero
144 produces an empty rectangle. */
145 GRect(int xmin, int ymin, unsigned int width=0, unsigned int height=0);
146 /** Returns the rectangle width. */
147 int width() const;
148 /** Returns the rectangle height. */
149 int height() const;
150 /** Returns the area of the rectangle. */
151 int area() const;
152 /** Returns true if the rectangle is empty. */
153 bool isempty() const;
154 /** Returns true if the rectangle contains pixel (#x#,#y#). A rectangle
155 contains all pixels with horizontal pixel coordinates in range #xmin#
156 (inclusive) to #xmax# (exclusive) and vertical coordinates #ymin#
157 (inclusive) to #ymax# (exclusive). */
158 int contains(int x, int y) const;
159 /** Returns true if this rectangle contains the passed rectangle #rect#.
160 The function basically checks, that the intersection of this rectangle
161 with #rect# is #rect#. */
162 int contains(const GRect & rect) const;
163 /** Returns true if rectangles #r1# and #r2# are equal. */
164 friend int operator==(const GRect & r1, const GRect & r2);
165 /** Returns true if rectangles #r1# and #r2# are not equal. */
166 friend int operator!=(const GRect & r1, const GRect & r2);
167 /** Resets the rectangle to the empty rectangle */
168 void clear();
169 /** Fatten the rectangle. Both vertical sides of the rectangle are pushed
170 apart by #dx# units. Both horizontal sides of the rectangle are pushed
171 apart by #dy# units. Setting arguments #dx# (resp. #dy#) to a negative
172 value reduces the rectangle horizontal (resp. vertical) size. */
173 int inflate(int dx, int dy);
174 /** Translate the rectangle. The new rectangle is composed of all the points
175 of the old rectangle translated by #dx# units horizontally and #dy#
176 units vertically. */
177 int translate(int dx, int dy);
178 /** Sets the rectangle to the intersection of rectangles #rect1# and #rect2#.
179 This function returns true if the intersection rectangle is not empty. */
180 int intersect(const GRect &rect1, const GRect &rect2);
181 /** Sets the rectangle to the smallest rectangle containing the points of
182 both rectangles #rect1# and #rect2#. This function returns true if the
183 created rectangle is not empty. */
184 int recthull(const GRect &rect1, const GRect &rect2);
185 /** Multiplies xmin, ymin, xmax, ymax by factor and scales the rectangle*/
186 void scale(float factor);
187 /** Multiplies xmin, xmax by xfactor and ymin, ymax by yfactor and scales the rectangle*/
188 void scale(float xfactor, float yfactor);
189 /** Minimal horizontal point coordinate of the rectangle. */
190 int xmin;
191 /** Minimal vertical point coordinate of the rectangle. */
192 int ymin;
193 /** Maximal horizontal point coordinate of the rectangle. */
194 int xmax;
195 /** Maximal vertical point coordinate of the rectangle. */
196 int ymax;
197 };
198
199
200 /** Maps points from one rectangle to another rectangle. This class
201 represents a relation between the points of two rectangles. Given the
202 coordinates of a point in the first rectangle (input rectangle), function
203 \Ref{map} computes the coordinates of the corresponding point in the
204 second rectangle (the output rectangle). This function actually implements
205 an affine transform which maps the corners of the first rectangle onto the
206 matching corners of the second rectangle. The scaling operation is
207 performed using integer fraction arithmetic in order to maximize
208 accuracy. */
209 class DJVUAPI GRectMapper
210 {
211 public:
212 /** Constructs a rectangle mapper. */
213 GRectMapper();
214 /** Resets the rectangle mapper state. Both the input rectangle
215 and the output rectangle are marked as undefined. */
216 void clear();
217 /** Sets the input rectangle. */
218 void set_input(const GRect &rect);
219 /** Returns the input rectangle. */
220 GRect get_input();
221 /** Sets the output rectangle. */
222 void set_output(const GRect &rect);
223 /** Returns the output rectangle. */
224 GRect get_output();
225 /** Composes the affine transform with a rotation of #count# quarter turns
226 counter-clockwise. This operation essentially is a modification of the
227 match between the corners of the input rectangle and the corners of the
228 output rectangle. */
229 void rotate(int count=1);
230 /** Composes the affine transform with a symmetry with respect to the
231 vertical line crossing the center of the output rectangle. This
232 operation essentially is a modification of the match between the corners
233 of the input rectangle and the corners of the output rectangle. */
234 void mirrorx();
235 /** Composes the affine transform with a symmetry with respect to the
236 horizontal line crossing the center of the output rectangle. This
237 operation essentially is a modification of the match between the corners
238 of the input rectangle and the corners of the output rectangle. */
239 void mirrory();
240 /** Maps a point according to the affine transform. Variables #x# and #y#
241 initially contain the coordinates of a point. This operation overwrites
242 these variables with the coordinates of a second point located in the
243 same position relative to the corners of the output rectangle as the
244 first point relative to the matching corners of the input rectangle.
245 Coordinates are rounded to the nearest integer. */
246 void map(int &x, int &y);
247 /** Maps a rectangle according to the affine transform. This operation
248 consists in mapping the rectangle corners and reordering the corners in
249 the canonical rectangle representation. Variable #rect# is overwritten
250 with the new rectangle coordinates. */
251 void map(GRect &rect);
252 /** Maps a point according to the inverse of the affine transform.
253 Variables #x# and #y# initially contain the coordinates of a point. This
254 operation overwrites these variables with the coordinates of a second
255 point located in the same position relative to the corners of input
256 rectangle as the first point relative to the matching corners of the
257 input rectangle. Coordinates are rounded to the nearest integer. */
258 void unmap(int &x, int &y);
259 /** Maps a rectangle according to the inverse of the affine transform. This
260 operation consists in mapping the rectangle corners and reordering the
261 corners in the canonical rectangle representation. Variable #rect# is
262 overwritten with the new rectangle coordinates. */
263 void unmap(GRect &rect);
264 public:
265 // GRatio
266 struct GRatio {
267 GRatio ();
268 GRatio (int p, int q);
269 int p;
270 int q;
271 };
272 private:
273 // Data
274 GRect rectFrom;
275 GRect rectTo;
276 int code;
277 // Helper
278 void precalc();
279 friend int operator*(int n, GRatio r );
280 friend int operator/(int n, GRatio r );
281 GRatio rw;
282 GRatio rh;
283 };
284
285
286 //@}
287
288
289
290 // ---- INLINES
291
292 inline
GRect()293 GRect::GRect()
294 : xmin(0), ymin(0), xmax(0), ymax(0)
295 {
296 }
297
298 inline
GRect(int xmin,int ymin,unsigned int width,unsigned int height)299 GRect::GRect(int xmin, int ymin, unsigned int width, unsigned int height)
300 : xmin(xmin), ymin(ymin), xmax(xmin+width), ymax(ymin+height)
301 {
302 }
303
304 inline int
width()305 GRect::width() const
306 {
307 return xmax - xmin;
308 }
309
310 inline int
height()311 GRect::height() const
312 {
313 return ymax - ymin;
314 }
315
316 inline bool
isempty()317 GRect::isempty() const
318 {
319 return (xmin>=xmax || ymin>=ymax);
320 }
321
322 inline int
area()323 GRect::area() const
324 {
325 return isempty() ? 0 : (xmax-xmin)*(ymax-ymin);
326 }
327
328 inline int
contains(int x,int y)329 GRect::contains(int x, int y) const
330 {
331 return (x>=xmin && x<xmax && y>=ymin && y<ymax);
332 }
333
334 inline void
clear()335 GRect::clear()
336 {
337 xmin = xmax = ymin = ymax = 0;
338 }
339
340 inline int
341 operator!=(const GRect & r1, const GRect & r2)
342 {
343 return !(r1==r2);
344 }
345
346 // ---- THE END
347
348 #ifdef HAVE_NAMESPACES
349 }
350 # ifndef NOT_USING_DJVU_NAMESPACE
351 using namespace DJVU;
352 # endif
353 #endif
354 #endif
355