1 // Copyright 2014 PDFium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6 7 #include <limits.h> 8 9 #include "core/include/fxcrt/fx_coordinates.h" 10 #include "core/include/fxcrt/fx_ext.h" 11 12 void FX_RECT::Normalize() { 13 if (left > right) { 14 int temp = left; 15 left = right; 16 right = temp; 17 } 18 if (top > bottom) { 19 int temp = top; 20 top = bottom; 21 bottom = temp; 22 } 23 } 24 void FX_RECT::Intersect(const FX_RECT& src) { 25 FX_RECT src_n = src; 26 src_n.Normalize(); 27 Normalize(); 28 left = left > src_n.left ? left : src_n.left; 29 top = top > src_n.top ? top : src_n.top; 30 right = right < src_n.right ? right : src_n.right; 31 bottom = bottom < src_n.bottom ? bottom : src_n.bottom; 32 if (left > right || top > bottom) { 33 left = top = right = bottom = 0; 34 } 35 } 36 void FX_RECT::Union(const FX_RECT& other_rect) { 37 Normalize(); 38 FX_RECT other = other_rect; 39 other.Normalize(); 40 left = left < other.left ? left : other.left; 41 right = right > other.right ? right : other.right; 42 bottom = bottom > other.bottom ? bottom : other.bottom; 43 top = top < other.top ? top : other.top; 44 } 45 FX_BOOL GetIntersection(FX_FLOAT low1, 46 FX_FLOAT high1, 47 FX_FLOAT low2, 48 FX_FLOAT high2, 49 FX_FLOAT& interlow, 50 FX_FLOAT& interhigh) { 51 if (low1 >= high2 || low2 >= high1) { 52 return FALSE; 53 } 54 interlow = low1 > low2 ? low1 : low2; 55 interhigh = high1 > high2 ? high2 : high1; 56 return TRUE; 57 } 58 extern "C" int FXSYS_round(FX_FLOAT d) { 59 if (d < (FX_FLOAT)INT_MIN) { 60 return INT_MIN; 61 } 62 if (d > (FX_FLOAT)INT_MAX) { 63 return INT_MAX; 64 } 65 66 return (int)round(d); 67 } 68 CFX_FloatRect::CFX_FloatRect(const FX_RECT& rect) { 69 left = (FX_FLOAT)(rect.left); 70 right = (FX_FLOAT)(rect.right); 71 bottom = (FX_FLOAT)(rect.top); 72 top = (FX_FLOAT)(rect.bottom); 73 } 74 void CFX_FloatRect::Normalize() { 75 FX_FLOAT temp; 76 if (left > right) { 77 temp = left; 78 left = right; 79 right = temp; 80 } 81 if (bottom > top) { 82 temp = top; 83 top = bottom; 84 bottom = temp; 85 } 86 } 87 void CFX_FloatRect::Intersect(const CFX_FloatRect& other_rect) { 88 Normalize(); 89 CFX_FloatRect other = other_rect; 90 other.Normalize(); 91 left = left > other.left ? left : other.left; 92 right = right < other.right ? right : other.right; 93 bottom = bottom > other.bottom ? bottom : other.bottom; 94 top = top < other.top ? top : other.top; 95 if (left > right || bottom > top) { 96 left = right = bottom = top = 0; 97 } 98 } 99 void CFX_FloatRect::Union(const CFX_FloatRect& other_rect) { 100 Normalize(); 101 CFX_FloatRect other = other_rect; 102 other.Normalize(); 103 left = left < other.left ? left : other.left; 104 right = right > other.right ? right : other.right; 105 bottom = bottom < other.bottom ? bottom : other.bottom; 106 top = top > other.top ? top : other.top; 107 } 108 void CFX_FloatRect::Transform(const CFX_Matrix* pMatrix) { 109 pMatrix->TransformRect(left, right, top, bottom); 110 } 111 int CFX_FloatRect::Substract4(CFX_FloatRect& s, CFX_FloatRect* pRects) { 112 Normalize(); 113 s.Normalize(); 114 int nRects = 0; 115 CFX_FloatRect rects[4]; 116 if (left < s.left) { 117 rects[nRects].left = left; 118 rects[nRects].right = s.left; 119 rects[nRects].bottom = bottom; 120 rects[nRects].top = top; 121 nRects++; 122 } 123 if (s.left < right && s.top < top) { 124 rects[nRects].left = s.left; 125 rects[nRects].right = right; 126 rects[nRects].bottom = s.top; 127 rects[nRects].top = top; 128 nRects++; 129 } 130 if (s.top > bottom && s.right < right) { 131 rects[nRects].left = s.right; 132 rects[nRects].right = right; 133 rects[nRects].bottom = bottom; 134 rects[nRects].top = s.top; 135 nRects++; 136 } 137 if (s.bottom > bottom) { 138 rects[nRects].left = s.left; 139 rects[nRects].right = s.right; 140 rects[nRects].bottom = bottom; 141 rects[nRects].top = s.bottom; 142 nRects++; 143 } 144 if (nRects == 0) { 145 return 0; 146 } 147 for (int i = 0; i < nRects; i++) { 148 pRects[i] = rects[i]; 149 pRects[i].Intersect(*this); 150 } 151 return nRects; 152 } 153 FX_RECT CFX_FloatRect::GetOutterRect() const { 154 CFX_FloatRect rect1 = *this; 155 FX_RECT rect; 156 rect.left = (int)FXSYS_floor(rect1.left); 157 rect.right = (int)FXSYS_ceil(rect1.right); 158 rect.top = (int)FXSYS_floor(rect1.bottom); 159 rect.bottom = (int)FXSYS_ceil(rect1.top); 160 rect.Normalize(); 161 return rect; 162 } 163 FX_RECT CFX_FloatRect::GetInnerRect() const { 164 CFX_FloatRect rect1 = *this; 165 FX_RECT rect; 166 rect.left = (int)FXSYS_ceil(rect1.left); 167 rect.right = (int)FXSYS_floor(rect1.right); 168 rect.top = (int)FXSYS_ceil(rect1.bottom); 169 rect.bottom = (int)FXSYS_floor(rect1.top); 170 rect.Normalize(); 171 return rect; 172 } 173 static void _MatchFloatRange(FX_FLOAT f1, FX_FLOAT f2, int& i1, int& i2) { 174 int length = (int)FXSYS_ceil(f2 - f1); 175 int i1_1 = (int)FXSYS_floor(f1); 176 int i1_2 = (int)FXSYS_ceil(f1); 177 FX_FLOAT error1 = f1 - i1_1 + (FX_FLOAT)FXSYS_fabs(f2 - i1_1 - length); 178 FX_FLOAT error2 = i1_2 - f1 + (FX_FLOAT)FXSYS_fabs(f2 - i1_2 - length); 179 i1 = (error1 > error2) ? i1_2 : i1_1; 180 i2 = i1 + length; 181 } 182 FX_RECT CFX_FloatRect::GetClosestRect() const { 183 CFX_FloatRect rect1 = *this; 184 FX_RECT rect; 185 _MatchFloatRange(rect1.left, rect1.right, rect.left, rect.right); 186 _MatchFloatRange(rect1.bottom, rect1.top, rect.top, rect.bottom); 187 rect.Normalize(); 188 return rect; 189 } 190 FX_BOOL CFX_FloatRect::Contains(const CFX_FloatRect& other_rect) const { 191 CFX_FloatRect n1 = *this; 192 n1.Normalize(); 193 CFX_FloatRect n2 = other_rect; 194 n2.Normalize(); 195 if (n2.left >= n1.left && n2.right <= n1.right && n2.bottom >= n1.bottom && 196 n2.top <= n1.top) { 197 return TRUE; 198 } 199 return FALSE; 200 } 201 FX_BOOL CFX_FloatRect::Contains(FX_FLOAT x, FX_FLOAT y) const { 202 CFX_FloatRect n1 = *this; 203 n1.Normalize(); 204 return x <= n1.right && x >= n1.left && y <= n1.top && y >= n1.bottom; 205 } 206 void CFX_FloatRect::UpdateRect(FX_FLOAT x, FX_FLOAT y) { 207 if (left > x) { 208 left = x; 209 } 210 if (right < x) { 211 right = x; 212 } 213 if (bottom > y) { 214 bottom = y; 215 } 216 if (top < y) { 217 top = y; 218 } 219 } 220 CFX_FloatRect CFX_FloatRect::GetBBox(const CFX_FloatPoint* pPoints, 221 int nPoints) { 222 if (nPoints == 0) { 223 return CFX_FloatRect(); 224 } 225 FX_FLOAT min_x = pPoints->x, max_x = pPoints->x, min_y = pPoints->y, 226 max_y = pPoints->y; 227 for (int i = 1; i < nPoints; i++) { 228 if (min_x > pPoints[i].x) { 229 min_x = pPoints[i].x; 230 } 231 if (max_x < pPoints[i].x) { 232 max_x = pPoints[i].x; 233 } 234 if (min_y > pPoints[i].y) { 235 min_y = pPoints[i].y; 236 } 237 if (max_y < pPoints[i].y) { 238 max_y = pPoints[i].y; 239 } 240 } 241 return CFX_FloatRect(min_x, min_y, max_x, max_y); 242 } 243 void CFX_Matrix::Set(FX_FLOAT other_a, 244 FX_FLOAT other_b, 245 FX_FLOAT other_c, 246 FX_FLOAT other_d, 247 FX_FLOAT other_e, 248 FX_FLOAT other_f) { 249 a = other_a; 250 b = other_b; 251 c = other_c; 252 d = other_d; 253 e = other_e; 254 f = other_f; 255 } 256 void CFX_Matrix::Set(const FX_FLOAT n[6]) { 257 a = n[0]; 258 b = n[1]; 259 c = n[2]; 260 d = n[3]; 261 e = n[4]; 262 f = n[5]; 263 } 264 void CFX_Matrix::SetReverse(const CFX_Matrix& m) { 265 FX_FLOAT i = m.a * m.d - m.b * m.c; 266 if (FXSYS_fabs(i) == 0) { 267 return; 268 } 269 FX_FLOAT j = -i; 270 a = m.d / i; 271 b = m.b / j; 272 c = m.c / j; 273 d = m.a / i; 274 e = (m.c * m.f - m.d * m.e) / i; 275 f = (m.a * m.f - m.b * m.e) / j; 276 } 277 static void FXCRT_Matrix_Concat(CFX_Matrix& m, 278 const CFX_Matrix& m1, 279 const CFX_Matrix& m2) { 280 FX_FLOAT aa = m1.a * m2.a + m1.b * m2.c; 281 FX_FLOAT bb = m1.a * m2.b + m1.b * m2.d; 282 FX_FLOAT cc = m1.c * m2.a + m1.d * m2.c; 283 FX_FLOAT dd = m1.c * m2.b + m1.d * m2.d; 284 FX_FLOAT ee = m1.e * m2.a + m1.f * m2.c + m2.e; 285 FX_FLOAT ff = m1.e * m2.b + m1.f * m2.d + m2.f; 286 m.a = aa, m.b = bb, m.c = cc, m.d = dd, m.e = ee, m.f = ff; 287 } 288 void CFX_Matrix::Concat(FX_FLOAT a, 289 FX_FLOAT b, 290 FX_FLOAT c, 291 FX_FLOAT d, 292 FX_FLOAT e, 293 FX_FLOAT f, 294 FX_BOOL bPrepended) { 295 CFX_Matrix m; 296 m.Set(a, b, c, d, e, f); 297 Concat(m, bPrepended); 298 } 299 void CFX_Matrix::Concat(const CFX_Matrix& m, FX_BOOL bPrepended) { 300 if (bPrepended) { 301 FXCRT_Matrix_Concat(*this, m, *this); 302 } else { 303 FXCRT_Matrix_Concat(*this, *this, m); 304 } 305 } 306 void CFX_Matrix::ConcatInverse(const CFX_Matrix& src, FX_BOOL bPrepended) { 307 CFX_Matrix m; 308 m.SetReverse(src); 309 Concat(m, bPrepended); 310 } 311 FX_BOOL CFX_Matrix::IsInvertible() const { 312 return FXSYS_fabs(a * d - b * c) >= 0.0001f; 313 } 314 FX_BOOL CFX_Matrix::Is90Rotated() const { 315 return FXSYS_fabs(a * 1000) < FXSYS_fabs(b) && 316 FXSYS_fabs(d * 1000) < FXSYS_fabs(c); 317 } 318 FX_BOOL CFX_Matrix::IsScaled() const { 319 return FXSYS_fabs(b * 1000) < FXSYS_fabs(a) && 320 FXSYS_fabs(c * 1000) < FXSYS_fabs(d); 321 } 322 void CFX_Matrix::Translate(FX_FLOAT x, FX_FLOAT y, FX_BOOL bPrepended) { 323 if (bPrepended) { 324 e += x * a + y * c; 325 f += y * d + x * b; 326 } else { 327 e += x, f += y; 328 } 329 } 330 void CFX_Matrix::Scale(FX_FLOAT sx, FX_FLOAT sy, FX_BOOL bPrepended) { 331 a *= sx, d *= sy; 332 if (bPrepended) { 333 b *= sx; 334 c *= sy; 335 } else { 336 b *= sy; 337 c *= sx; 338 e *= sx; 339 f *= sy; 340 } 341 } 342 void CFX_Matrix::Rotate(FX_FLOAT fRadian, FX_BOOL bPrepended) { 343 FX_FLOAT cosValue = FXSYS_cos(fRadian); 344 FX_FLOAT sinValue = FXSYS_sin(fRadian); 345 CFX_Matrix m; 346 m.Set(cosValue, sinValue, -sinValue, cosValue, 0, 0); 347 if (bPrepended) { 348 FXCRT_Matrix_Concat(*this, m, *this); 349 } else { 350 FXCRT_Matrix_Concat(*this, *this, m); 351 } 352 } 353 void CFX_Matrix::RotateAt(FX_FLOAT fRadian, 354 FX_FLOAT dx, 355 FX_FLOAT dy, 356 FX_BOOL bPrepended) { 357 Translate(dx, dy, bPrepended); 358 Rotate(fRadian, bPrepended); 359 Translate(-dx, -dy, bPrepended); 360 } 361 void CFX_Matrix::Shear(FX_FLOAT fAlphaRadian, 362 FX_FLOAT fBetaRadian, 363 FX_BOOL bPrepended) { 364 CFX_Matrix m; 365 m.Set(1, FXSYS_tan(fAlphaRadian), FXSYS_tan(fBetaRadian), 1, 0, 0); 366 if (bPrepended) { 367 FXCRT_Matrix_Concat(*this, m, *this); 368 } else { 369 FXCRT_Matrix_Concat(*this, *this, m); 370 } 371 } 372 void CFX_Matrix::MatchRect(const CFX_FloatRect& dest, 373 const CFX_FloatRect& src) { 374 FX_FLOAT fDiff = src.left - src.right; 375 a = FXSYS_fabs(fDiff) < 0.001f ? 1 : (dest.left - dest.right) / fDiff; 376 fDiff = src.bottom - src.top; 377 d = FXSYS_fabs(fDiff) < 0.001f ? 1 : (dest.bottom - dest.top) / fDiff; 378 e = dest.left - src.left * a; 379 f = dest.bottom - src.bottom * d; 380 b = 0; 381 c = 0; 382 } 383 FX_FLOAT CFX_Matrix::GetXUnit() const { 384 if (b == 0) { 385 return (a > 0 ? a : -a); 386 } 387 if (a == 0) { 388 return (b > 0 ? b : -b); 389 } 390 return FXSYS_sqrt(a * a + b * b); 391 } 392 FX_FLOAT CFX_Matrix::GetYUnit() const { 393 if (c == 0) { 394 return (d > 0 ? d : -d); 395 } 396 if (d == 0) { 397 return (c > 0 ? c : -c); 398 } 399 return FXSYS_sqrt(c * c + d * d); 400 } 401 void CFX_Matrix::GetUnitRect(CFX_RectF& rect) const { 402 rect.left = rect.top = 0; 403 rect.width = rect.height = 1; 404 TransformRect(rect); 405 } 406 CFX_FloatRect CFX_Matrix::GetUnitRect() const { 407 CFX_FloatRect rect(0, 0, 1, 1); 408 rect.Transform((const CFX_Matrix*)this); 409 return rect; 410 } 411 FX_FLOAT CFX_Matrix::GetUnitArea() const { 412 FX_FLOAT A = FXSYS_sqrt(a * a + b * b); 413 FX_FLOAT B = FXSYS_sqrt(c * c + d * d); 414 FX_FLOAT ac = a + c, bd = b + d; 415 FX_FLOAT C = FXSYS_sqrt(ac * ac + bd * bd); 416 FX_FLOAT P = (A + B + C) / 2; 417 return FXSYS_sqrt(P * (P - A) * (P - B) * (P - C)) * 2; 418 } 419 FX_FLOAT CFX_Matrix::TransformXDistance(FX_FLOAT dx) const { 420 FX_FLOAT fx = a * dx, fy = b * dx; 421 return FXSYS_sqrt(fx * fx + fy * fy); 422 } 423 int32_t CFX_Matrix::TransformXDistance(int32_t dx) const { 424 FX_FLOAT fx = a * dx, fy = b * dx; 425 return FXSYS_round(FXSYS_sqrt(fx * fx + fy * fy)); 426 } 427 FX_FLOAT CFX_Matrix::TransformYDistance(FX_FLOAT dy) const { 428 FX_FLOAT fx = c * dy, fy = d * dy; 429 return FXSYS_sqrt(fx * fx + fy * fy); 430 } 431 int32_t CFX_Matrix::TransformYDistance(int32_t dy) const { 432 FX_FLOAT fx = c * dy, fy = d * dy; 433 return FXSYS_round(FXSYS_sqrt(fx * fx + fy * fy)); 434 } 435 FX_FLOAT CFX_Matrix::TransformDistance(FX_FLOAT dx, FX_FLOAT dy) const { 436 FX_FLOAT fx = a * dx + c * dy, fy = b * dx + d * dy; 437 return FXSYS_sqrt(fx * fx + fy * fy); 438 } 439 int32_t CFX_Matrix::TransformDistance(int32_t dx, int32_t dy) const { 440 FX_FLOAT fx = a * dx + c * dy, fy = b * dx + d * dy; 441 return FXSYS_round(FXSYS_sqrt(fx * fx + fy * fy)); 442 } 443 FX_FLOAT CFX_Matrix::TransformDistance(FX_FLOAT distance) const { 444 return distance * (GetXUnit() + GetYUnit()) / 2; 445 } 446 void CFX_Matrix::TransformVector(CFX_VectorF& v) const { 447 FX_FLOAT fx = a * v.x + c * v.y; 448 FX_FLOAT fy = b * v.x + d * v.y; 449 v.x = fx, v.y = fy; 450 } 451 void CFX_Matrix::TransformVector(CFX_Vector& v) const { 452 FX_FLOAT fx = a * v.x + c * v.y; 453 FX_FLOAT fy = b * v.x + d * v.y; 454 v.x = FXSYS_round(fx); 455 v.y = FXSYS_round(fy); 456 } 457 void CFX_Matrix::TransformPoints(CFX_Point* points, int32_t iCount) const { 458 FXSYS_assert(iCount > 0); 459 FX_FLOAT fx, fy; 460 for (int32_t i = 0; i < iCount; i++) { 461 fx = a * points->x + c * points->y + e; 462 fy = b * points->x + d * points->y + f; 463 points->x = FXSYS_round(fx); 464 points->y = FXSYS_round(fy); 465 points++; 466 } 467 } 468 void CFX_Matrix::TransformPoints(CFX_PointF* points, int32_t iCount) const { 469 FXSYS_assert(iCount > 0); 470 FX_FLOAT fx, fy; 471 for (int32_t i = 0; i < iCount; i++) { 472 fx = a * points->x + c * points->y + e; 473 fy = b * points->x + d * points->y + f; 474 points->x = fx, points->y = fy; 475 points++; 476 } 477 } 478 void CFX_Matrix::TransformPoint(FX_FLOAT& x, FX_FLOAT& y) const { 479 FX_FLOAT fx = a * x + c * y + e; 480 FX_FLOAT fy = b * x + d * y + f; 481 x = fx, y = fy; 482 } 483 void CFX_Matrix::TransformPoint(int32_t& x, int32_t& y) const { 484 FX_FLOAT fx = a * x + c * y + e; 485 FX_FLOAT fy = b * x + d * y + f; 486 x = FXSYS_round(fx); 487 y = FXSYS_round(fy); 488 } 489 void CFX_Matrix::TransformRect(CFX_RectF& rect) const { 490 FX_FLOAT right = rect.right(), bottom = rect.bottom(); 491 TransformRect(rect.left, right, bottom, rect.top); 492 rect.width = right - rect.left; 493 rect.height = bottom - rect.top; 494 } 495 void CFX_Matrix::TransformRect(CFX_Rect& rect) const { 496 FX_FLOAT left = (FX_FLOAT)rect.left; 497 FX_FLOAT top = (FX_FLOAT)rect.bottom(); 498 FX_FLOAT right = (FX_FLOAT)rect.right(); 499 FX_FLOAT bottom = (FX_FLOAT)rect.top; 500 TransformRect(left, right, top, bottom); 501 rect.left = FXSYS_round(left); 502 rect.top = FXSYS_round(bottom); 503 rect.width = FXSYS_round(right - left); 504 rect.height = FXSYS_round(top - bottom); 505 } 506 void CFX_Matrix::TransformRect(FX_FLOAT& left, 507 FX_FLOAT& right, 508 FX_FLOAT& top, 509 FX_FLOAT& bottom) const { 510 FX_FLOAT x[4], y[4]; 511 x[0] = left; 512 y[0] = top; 513 x[1] = left; 514 y[1] = bottom; 515 x[2] = right; 516 y[2] = top; 517 x[3] = right; 518 y[3] = bottom; 519 int i; 520 for (i = 0; i < 4; i++) { 521 Transform(x[i], y[i], x[i], y[i]); 522 } 523 right = left = x[0]; 524 top = bottom = y[0]; 525 for (i = 1; i < 4; i++) { 526 if (right < x[i]) { 527 right = x[i]; 528 } 529 if (left > x[i]) { 530 left = x[i]; 531 } 532 if (top < y[i]) { 533 top = y[i]; 534 } 535 if (bottom > y[i]) { 536 bottom = y[i]; 537 } 538 } 539 } 540