Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/affinecompose.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*!
28 * \file affinecompose.c
29 * <pre>
30 *
31 * Composable coordinate transforms
32 * l_float32 *createMatrix2dTranslate()
33 * l_float32 *createMatrix2dScale()
34 * l_float32 *createMatrix2dRotate()
35 *
36 * Special coordinate transforms on pta
37 * PTA *ptaTranslate()
38 * PTA *ptaScale()
39 * PTA *ptaRotate()
40 *
41 * Special coordinate transforms on boxa
42 * BOXA *boxaTranslate()
43 * BOXA *boxaScale()
44 * BOXA *boxaRotate()
45 *
46 * General coordinate transform on pta and boxa
47 * PTA *ptaAffineTransform()
48 * BOXA *boxaAffineTransform()
49 *
50 * Matrix operations
51 * l_int32 l_productMatVec()
52 * l_int32 l_productMat2()
53 * l_int32 l_productMat3()
54 * l_int32 l_productMat4()
55 * </pre>
56 */
57
58 #ifdef HAVE_CONFIG_H
59 #include <config_auto.h>
60 #endif /* HAVE_CONFIG_H */
61
62 #include <math.h>
63 #include "allheaders.h"
64
65 /*-------------------------------------------------------------*
66 * Composable coordinate transforms *
67 *-------------------------------------------------------------*/
68 /*!
69 * \brief createMatrix2dTranslate()
70 *
71 * \param[in] transx x component of translation wrt. the origin
72 * \param[in] transy y component of translation wrt. the origin
73 * \return 3x3 transform matrix, or NULL on error
74 *
75 * <pre>
76 * Notes:
77 * (1) The translation is equivalent to:
78 * v' = Av
79 * where v and v' are 1x3 column vectors in the form
80 * v = [x, y, 1]^ ^ denotes transpose
81 * and the affine translation matrix is
82 * A = [ 1 0 tx
83 * 0 1 ty
84 * 0 0 1 ]
85 *
86 * (2) We consider translation as with respect to a fixed origin.
87 * In a clipping operation, the origin moves and the points
88 * are fixed, and you use (-tx, -ty) where (tx, ty) is the
89 * translation vector of the origin.
90 * </pre>
91 */
92 l_float32 *
93 createMatrix2dTranslate(l_float32 transx,
94 l_float32 transy)
95 {
96 l_float32 *mat;
97
98 mat = (l_float32 *)LEPT_CALLOC(9, sizeof(l_float32));
99 mat[0] = mat[4] = mat[8] = 1;
100 mat[2] = transx;
101 mat[5] = transy;
102 return mat;
103 }
104
105
106 /*!
107 * \brief createMatrix2dScale()
108 *
109 * \param[in] scalex horizontal scale factor
110 * \param[in] scaley vertical scale factor
111 * \return 3x3 transform matrix, or NULL on error
112 *
113 * <pre>
114 * Notes:
115 * (1) The scaling is equivalent to:
116 * v' = Av
117 * where v and v' are 1x3 column vectors in the form
118 * v = [x, y, 1]^ ^ denotes transpose
119 * and the affine scaling matrix is
120 * A = [ sx 0 0
121 * 0 sy 0
122 * 0 0 1 ]
123 *
124 * (2) We consider scaling as with respect to a fixed origin.
125 * In other words, the origin is the only point that doesn't
126 * move in the scaling transform.
127 * </pre>
128 */
129 l_float32 *
130 createMatrix2dScale(l_float32 scalex,
131 l_float32 scaley)
132 {
133 l_float32 *mat;
134
135 mat = (l_float32 *)LEPT_CALLOC(9, sizeof(l_float32));
136 mat[0] = scalex;
137 mat[4] = scaley;
138 mat[8] = 1;
139 return mat;
140 }
141
142
143 /*!
144 * \brief createMatrix2dRotate()
145 *
146 * \param[in] xc, yc location of center of rotation
147 * \param[in] angle rotation in radians; clockwise is positive
148 * \return 3x3 transform matrix, or NULL on error
149 *
150 * <pre>
151 * Notes:
152 * (1) The rotation is equivalent to:
153 * v' = Av
154 * where v and v' are 1x3 column vectors in the form
155 * v = [x, y, 1]^ ^ denotes transpose
156 * and the affine rotation matrix is
157 * A = [ cosa -sina xc*1-cosa + yc*sina
158 * sina cosa yc*1-cosa - xc*sina
159 * 0 0 1 ]
160 *
161 * If the rotation is about the origin, xc, yc) = (0, 0 and
162 * this simplifies to
163 * A = [ cosa -sina 0
164 * sina cosa 0
165 * 0 0 1 ]
166 *
167 * These relations follow from the following equations, which
168 * you can convince yourself are correct as follows. Draw a
169 * circle centered on xc,yc) and passing through (x,y), with
170 * (x',y') on the arc at an angle 'a' clockwise from (x,y).
171 * [ Hint: cosa + b = cosa * cosb - sina * sinb
172 * sina + b = sina * cosb + cosa * sinb ]
173 *
174 * x' - xc = x - xc) * cosa - (y - yc * sina
175 * y' - yc = x - xc) * sina + (y - yc * cosa
176 * </pre>
177 */
178 l_float32 *
179 createMatrix2dRotate(l_float32 xc,
180 l_float32 yc,
181 l_float32 angle)
182 {
183 l_float32 sina, cosa;
184 l_float32 *mat;
185
186 mat = (l_float32 *)LEPT_CALLOC(9, sizeof(l_float32));
187 sina = sin(angle);
188 cosa = cos(angle);
189 mat[0] = mat[4] = cosa;
190 mat[1] = -sina;
191 mat[2] = xc * (1.0 - cosa) + yc * sina;
192 mat[3] = sina;
193 mat[5] = yc * (1.0 - cosa) - xc * sina;
194 mat[8] = 1;
195 return mat;
196 }
197
198
199
200 /*-------------------------------------------------------------*
201 * Special coordinate transforms on pta *
202 *-------------------------------------------------------------*/
203 /*!
204 * \brief ptaTranslate()
205 *
206 * \param[in] ptas for initial points
207 * \param[in] transx x component of translation wrt. the origin
208 * \param[in] transy y component of translation wrt. the origin
209 * \return ptad translated points, or NULL on error
210 *
211 * <pre>
212 * Notes:
213 * (1) See createMatrix2dTranslate() for details of transform.
214 * </pre>
215 */
216 PTA *
217 ptaTranslate(PTA *ptas,
218 l_float32 transx,
219 l_float32 transy)
220 {
221 l_int32 i, npts;
222 l_float32 x, y;
223 PTA *ptad;
224
225 if (!ptas)
226 return (PTA *)ERROR_PTR("ptas not defined", __func__, NULL);
227
228 npts = ptaGetCount(ptas);
229 if ((ptad = ptaCreate(npts)) == NULL)
230 return (PTA *)ERROR_PTR("ptad not made", __func__, NULL);
231 for (i = 0; i < npts; i++) {
232 ptaGetPt(ptas, i, &x, &y);
233 ptaAddPt(ptad, x + transx, y + transy);
234 }
235
236 return ptad;
237 }
238
239
240 /*!
241 * \brief ptaScale()
242 *
243 * \param[in] ptas for initial points
244 * \param[in] scalex horizontal scale factor
245 * \param[in] scaley vertical scale factor
246 * \return 0 if OK; 1 on error
247 *
248 * <pre>
249 * Notes:
250 * (1) See createMatrix2dScale() for details of transform.
251 * </pre>
252 */
253 PTA *
254 ptaScale(PTA *ptas,
255 l_float32 scalex,
256 l_float32 scaley)
257 {
258 l_int32 i, npts;
259 l_float32 x, y;
260 PTA *ptad;
261
262 if (!ptas)
263 return (PTA *)ERROR_PTR("ptas not defined", __func__, NULL);
264
265 npts = ptaGetCount(ptas);
266 if ((ptad = ptaCreate(npts)) == NULL)
267 return (PTA *)ERROR_PTR("ptad not made", __func__, NULL);
268 for (i = 0; i < npts; i++) {
269 ptaGetPt(ptas, i, &x, &y);
270 ptaAddPt(ptad, scalex * x, scaley * y);
271 }
272
273 return ptad;
274 }
275
276
277 /*!
278 * \brief ptaRotate()
279 *
280 * \param[in] ptas for initial points
281 * \param[in] xc, yc location of center of rotation
282 * \param[in] angle rotation in radians; clockwise is positive
283 * \return ptad rotated pta, or NULL on error
284 *
285 * <pre>
286 * Notes;
287 * (1) See createMatrix2dRotate() for details of transform.
288 * (2) This transform can be thought of as composed of the
289 * sum of two parts:
290 * a) an (x,y)-dependent rotation about the origin:
291 * xr = x * cosa - y * sina
292 * yr = x * sina + y * cosa
293 * b) an (x,y)-independent translation that depends on the
294 * rotation center and the angle:
295 * xt = xc - xc * cosa + yc * sina
296 * yt = yc - xc * sina - yc * cosa
297 * The translation part (xt,yt) is equal to the difference
298 * between the center (xc,yc) and the location of the
299 * center after it is rotated about the origin.
300 * </pre>
301 */
302 PTA *
303 ptaRotate(PTA *ptas,
304 l_float32 xc,
305 l_float32 yc,
306 l_float32 angle)
307 {
308 l_int32 i, npts;
309 l_float32 x, y, xp, yp, sina, cosa;
310 PTA *ptad;
311
312 if (!ptas)
313 return (PTA *)ERROR_PTR("ptas not defined", __func__, NULL);
314
315 npts = ptaGetCount(ptas);
316 if ((ptad = ptaCreate(npts)) == NULL)
317 return (PTA *)ERROR_PTR("ptad not made", __func__, NULL);
318 sina = sin(angle);
319 cosa = cos(angle);
320 for (i = 0; i < npts; i++) {
321 ptaGetPt(ptas, i, &x, &y);
322 xp = xc + (x - xc) * cosa - (y - yc) * sina;
323 yp = yc + (x - xc) * sina + (y - yc) * cosa;
324 ptaAddPt(ptad, xp, yp);
325 }
326
327 return ptad;
328 }
329
330
331 /*-------------------------------------------------------------*
332 * Special coordinate transforms on boxa *
333 *-------------------------------------------------------------*/
334 /*!
335 * \brief boxaTranslate()
336 *
337 * \param[in] boxas
338 * \param[in] transx x component of translation wrt. the origin
339 * \param[in] transy y component of translation wrt. the origin
340 * \return boxad translated boxas, or NULL on error
341 *
342 * Notes:
343 * (1) See createMatrix2dTranslate() for details of transform.
344 */
345 BOXA *
346 boxaTranslate(BOXA *boxas,
347 l_float32 transx,
348 l_float32 transy)
349 {
350 PTA *ptas, *ptad;
351 BOXA *boxad;
352
353 if (!boxas)
354 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
355
356 ptas = boxaConvertToPta(boxas, 4);
357 ptad = ptaTranslate(ptas, transx, transy);
358 boxad = ptaConvertToBoxa(ptad, 4);
359 ptaDestroy(&ptas);
360 ptaDestroy(&ptad);
361 return boxad;
362 }
363
364
365 /*!
366 * \brief boxaScale()
367 *
368 * \param[in] boxas
369 * \param[in] scalex horizontal scale factor
370 * \param[in] scaley vertical scale factor
371 * \return boxad scaled boxas, or NULL on error
372 *
373 * Notes:
374 * (1) See createMatrix2dScale() for details of transform.
375 */
376 BOXA *
377 boxaScale(BOXA *boxas,
378 l_float32 scalex,
379 l_float32 scaley)
380 {
381 PTA *ptas, *ptad;
382 BOXA *boxad;
383
384 if (!boxas)
385 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
386
387 ptas = boxaConvertToPta(boxas, 4);
388 ptad = ptaScale(ptas, scalex, scaley);
389 boxad = ptaConvertToBoxa(ptad, 4);
390 ptaDestroy(&ptas);
391 ptaDestroy(&ptad);
392 return boxad;
393 }
394
395
396 /*!
397 * \brief boxaRotate()
398 *
399 * \param[in] boxas
400 * \param[in] xc, yc location of center of rotation
401 * \param[in] angle rotation in radians; clockwise is positive
402 * \return boxad rotated boxas, or NULL on error
403 *
404 * Notes:
405 * (1) See createMatrix2dRotate() for details of transform.
406 */
407 BOXA *
408 boxaRotate(BOXA *boxas,
409 l_float32 xc,
410 l_float32 yc,
411 l_float32 angle)
412 {
413 PTA *ptas, *ptad;
414 BOXA *boxad;
415
416 if (!boxas)
417 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
418
419 ptas = boxaConvertToPta(boxas, 4);
420 ptad = ptaRotate(ptas, xc, yc, angle);
421 boxad = ptaConvertToBoxa(ptad, 4);
422 ptaDestroy(&ptas);
423 ptaDestroy(&ptad);
424 return boxad;
425 }
426
427
428 /*-------------------------------------------------------------*
429 * General affine coordinate transform *
430 *-------------------------------------------------------------*/
431 /*!
432 * \brief ptaAffineTransform()
433 *
434 * \param[in] ptas for initial points
435 * \param[in] mat 3x3 transform matrix; canonical form
436 * \return ptad transformed points, or NULL on error
437 */
438 PTA *
439 ptaAffineTransform(PTA *ptas,
440 l_float32 *mat)
441 {
442 l_int32 i, npts;
443 l_float32 vecs[3], vecd[3];
444 PTA *ptad;
445
446 if (!ptas)
447 return (PTA *)ERROR_PTR("ptas not defined", __func__, NULL);
448 if (!mat)
449 return (PTA *)ERROR_PTR("transform not defined", __func__, NULL);
450
451 vecs[2] = 1;
452 npts = ptaGetCount(ptas);
453 if ((ptad = ptaCreate(npts)) == NULL)
454 return (PTA *)ERROR_PTR("ptad not made", __func__, NULL);
455 for (i = 0; i < npts; i++) {
456 ptaGetPt(ptas, i, &vecs[0], &vecs[1]);
457 l_productMatVec(mat, vecs, vecd, 3);
458 ptaAddPt(ptad, vecd[0], vecd[1]);
459 }
460
461 return ptad;
462 }
463
464
465 /*!
466 * \brief boxaAffineTransform()
467 *
468 * \param[in] boxas
469 * \param[in] mat 3x3 transform matrix; canonical form
470 * \return boxad transformed boxas, or NULL on error
471 */
472 BOXA *
473 boxaAffineTransform(BOXA *boxas,
474 l_float32 *mat)
475 {
476 PTA *ptas, *ptad;
477 BOXA *boxad;
478
479 if (!boxas)
480 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
481 if (!mat)
482 return (BOXA *)ERROR_PTR("transform not defined", __func__, NULL);
483
484 ptas = boxaConvertToPta(boxas, 4);
485 ptad = ptaAffineTransform(ptas, mat);
486 boxad = ptaConvertToBoxa(ptad, 4);
487 ptaDestroy(&ptas);
488 ptaDestroy(&ptad);
489 return boxad;
490 }
491
492
493 /*-------------------------------------------------------------*
494 * Matrix operations *
495 *-------------------------------------------------------------*/
496 /*!
497 * \brief l_productMatVec()
498 *
499 * \param[in] mat square matrix, as a 1-dimensional %size^2 array
500 * \param[in] vecs input column vector of length %size
501 * \param[in] vecd result column vector
502 * \param[in] size matrix is %size x %size; vectors are length %size
503 * \return 0 if OK, 1 on error
504 */
505 l_ok
506 l_productMatVec(l_float32 *mat,
507 l_float32 *vecs,
508 l_float32 *vecd,
509 l_int32 size)
510 {
511 l_int32 i, j;
512
513 if (!mat)
514 return ERROR_INT("matrix not defined", __func__, 1);
515 if (!vecs)
516 return ERROR_INT("input vector not defined", __func__, 1);
517 if (!vecd)
518 return ERROR_INT("result vector not defined", __func__, 1);
519
520 for (i = 0; i < size; i++) {
521 vecd[i] = 0;
522 for (j = 0; j < size; j++) {
523 vecd[i] += mat[size * i + j] * vecs[j];
524 }
525 }
526 return 0;
527 }
528
529
530 /*!
531 * \brief l_productMat2()
532 *
533 * \param[in] mat1 square matrix, as a 1-dimensional size^2 array
534 * \param[in] mat2 square matrix, as a 1-dimensional size^2 array
535 * \param[in] matd square matrix; product stored here
536 * \param[in] size of matrices
537 * \return 0 if OK, 1 on error
538 */
539 l_ok
540 l_productMat2(l_float32 *mat1,
541 l_float32 *mat2,
542 l_float32 *matd,
543 l_int32 size)
544 {
545 l_int32 i, j, k, index;
546
547 if (!mat1)
548 return ERROR_INT("matrix 1 not defined", __func__, 1);
549 if (!mat2)
550 return ERROR_INT("matrix 2 not defined", __func__, 1);
551 if (!matd)
552 return ERROR_INT("result matrix not defined", __func__, 1);
553
554 for (i = 0; i < size; i++) {
555 for (j = 0; j < size; j++) {
556 index = size * i + j;
557 matd[index] = 0;
558 for (k = 0; k < size; k++)
559 matd[index] += mat1[size * i + k] * mat2[size * k + j];
560 }
561 }
562 return 0;
563 }
564
565
566 /*!
567 * \brief l_productMat3()
568 *
569 * \param[in] mat1 square matrix, as a 1-dimensional size^2 array
570 * \param[in] mat2 square matrix, as a 1-dimensional size^2 array
571 * \param[in] mat3 square matrix, as a 1-dimensional size^2 array
572 * \param[in] matd square matrix; product stored here
573 * \param[in] size of matrices
574 * \return 0 if OK, 1 on error
575 */
576 l_ok
577 l_productMat3(l_float32 *mat1,
578 l_float32 *mat2,
579 l_float32 *mat3,
580 l_float32 *matd,
581 l_int32 size)
582 {
583 l_float32 *matt;
584
585 if (!mat1)
586 return ERROR_INT("matrix 1 not defined", __func__, 1);
587 if (!mat2)
588 return ERROR_INT("matrix 2 not defined", __func__, 1);
589 if (!mat3)
590 return ERROR_INT("matrix 3 not defined", __func__, 1);
591 if (!matd)
592 return ERROR_INT("result matrix not defined", __func__, 1);
593
594 if ((matt = (l_float32 *)LEPT_CALLOC((size_t)size * size,
595 sizeof(l_float32))) == NULL)
596 return ERROR_INT("matt not made", __func__, 1);
597 l_productMat2(mat1, mat2, matt, size);
598 l_productMat2(matt, mat3, matd, size);
599 LEPT_FREE(matt);
600 return 0;
601 }
602
603
604 /*!
605 * \brief l_productMat4()
606 *
607 * \param[in] mat1 square matrix, as a 1-dimensional size^2 array
608 * \param[in] mat2 square matrix, as a 1-dimensional size^2 array
609 * \param[in] mat3 square matrix, as a 1-dimensional size^2 array
610 * \param[in] mat4 square matrix, as a 1-dimensional size^2 array
611 * \param[in] matd square matrix; product stored here
612 * \param[in] size of matrices
613 * \return 0 if OK, 1 on error
614 */
615 l_ok
616 l_productMat4(l_float32 *mat1,
617 l_float32 *mat2,
618 l_float32 *mat3,
619 l_float32 *mat4,
620 l_float32 *matd,
621 l_int32 size)
622 {
623 l_float32 *matt;
624
625 if (!mat1)
626 return ERROR_INT("matrix 1 not defined", __func__, 1);
627 if (!mat2)
628 return ERROR_INT("matrix 2 not defined", __func__, 1);
629 if (!mat3)
630 return ERROR_INT("matrix 3 not defined", __func__, 1);
631 if (!matd)
632 return ERROR_INT("result matrix not defined", __func__, 1);
633
634 if ((matt = (l_float32 *)LEPT_CALLOC((size_t)size * size,
635 sizeof(l_float32))) == NULL)
636 return ERROR_INT("matt not made", __func__, 1);
637 l_productMat3(mat1, mat2, mat3, matt, size);
638 l_productMat2(matt, mat4, matd, size);
639 LEPT_FREE(matt);
640 return 0;
641 }