123456789101112131415161718192021222324252627282930313233343536373839404142 |
- // Copyright (c) 2021 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "ui/gfx/geometry/triangle_f.h"
- #include "ui/gfx/geometry/vector2d_f.h"
- namespace gfx {
- bool PointIsInTriangle(const PointF& point,
- const PointF& r1,
- const PointF& r2,
- const PointF& r3) {
- // Compute the barycentric coordinates (u, v, w) of |point| relative to the
- // triangle (r1, r2, r3) by the solving the system of equations:
- // 1) point = u * r1 + v * r2 + w * r3
- // 2) u + v + w = 1
- // This algorithm comes from Christer Ericson's Real-Time Collision Detection.
- Vector2dF r31 = r1 - r3;
- Vector2dF r32 = r2 - r3;
- Vector2dF r3p = point - r3;
- // Promote to doubles so all the math below is done with doubles, because
- // otherwise it gets incorrect results on arm64.
- double r31x = r31.x();
- double r31y = r31.y();
- double r32x = r32.x();
- double r32y = r32.y();
- double denom = r32y * r31x - r32x * r31y;
- double u = (r32y * r3p.x() - r32x * r3p.y()) / denom;
- double v = (r31x * r3p.y() - r31y * r3p.x()) / denom;
- double w = 1.0 - u - v;
- // Use the barycentric coordinates to test if |point| is inside the
- // triangle (r1, r2, r2).
- return (u >= 0) && (v >= 0) && (w >= 0);
- }
- } // namespace gfx
|