triangle_f.cc 1.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142
  1. // Copyright (c) 2021 The Chromium 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. #include "ui/gfx/geometry/triangle_f.h"
  5. #include "ui/gfx/geometry/vector2d_f.h"
  6. namespace gfx {
  7. bool PointIsInTriangle(const PointF& point,
  8. const PointF& r1,
  9. const PointF& r2,
  10. const PointF& r3) {
  11. // Compute the barycentric coordinates (u, v, w) of |point| relative to the
  12. // triangle (r1, r2, r3) by the solving the system of equations:
  13. // 1) point = u * r1 + v * r2 + w * r3
  14. // 2) u + v + w = 1
  15. // This algorithm comes from Christer Ericson's Real-Time Collision Detection.
  16. Vector2dF r31 = r1 - r3;
  17. Vector2dF r32 = r2 - r3;
  18. Vector2dF r3p = point - r3;
  19. // Promote to doubles so all the math below is done with doubles, because
  20. // otherwise it gets incorrect results on arm64.
  21. double r31x = r31.x();
  22. double r31y = r31.y();
  23. double r32x = r32.x();
  24. double r32y = r32.y();
  25. double denom = r32y * r31x - r32x * r31y;
  26. double u = (r32y * r3p.x() - r32x * r3p.y()) / denom;
  27. double v = (r31x * r3p.y() - r31y * r3p.x()) / denom;
  28. double w = 1.0 - u - v;
  29. // Use the barycentric coordinates to test if |point| is inside the
  30. // triangle (r1, r2, r2).
  31. return (u >= 0) && (v >= 0) && (w >= 0);
  32. }
  33. } // namespace gfx