| /* |
| * Copyright 2023 Google LLC |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "include/core/SkSpan.h" |
| #include "include/core/SkTypes.h" |
| #include "include/private/base/SkFloatingPoint.h" |
| #include "src/base/SkCubics.h" |
| #include "src/pathops/SkPathOpsCubic.h" |
| #include "tests/Test.h" |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <iterator> |
| #include <string> |
| |
| static void testCubicRootsReal(skiatest::Reporter* reporter, std::string name, |
| double A, double B, double C, double D, |
| SkSpan<const double> expectedRoots) { |
| skiatest::ReporterContext subtest(reporter, name); |
| // Validate test case |
| REPORTER_ASSERT(reporter, expectedRoots.size() <= 3, |
| "Invalid test case, up to 3 roots allowed"); |
| |
| for (size_t i = 0; i < expectedRoots.size(); i++) { |
| double x = expectedRoots[i]; |
| // A*x^3 + B*x^2 + C*x + D should equal 0 |
| double y = A * x * x * x + B * x * x + C * x + D; |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(y), |
| "Invalid test case root %zu. %.16f != 0", i, y); |
| |
| if (i > 0) { |
| REPORTER_ASSERT(reporter, expectedRoots[i-1] <= expectedRoots[i], |
| "Invalid test case root %zu. Roots should be sorted in ascending order", i); |
| } |
| } |
| |
| { |
| skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation"); |
| double roots[3] = {0, 0, 0}; |
| int rootCount = SkDCubic::RootsReal(A, B, C, D, roots); |
| REPORTER_ASSERT(reporter, expectedRoots.size() == size_t(rootCount), |
| "Wrong number of roots returned %zu != %d", expectedRoots.size(), |
| rootCount); |
| |
| // We don't care which order the roots are returned from the algorithm. |
| // For determinism, we will sort them (and ensure the provided solutions are also sorted). |
| std::sort(std::begin(roots), std::begin(roots) + rootCount); |
| for (int i = 0; i < rootCount; i++) { |
| if (sk_double_nearly_zero(expectedRoots[i])) { |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[i]), |
| "0 != %.16f at index %d", roots[i], i); |
| } else { |
| REPORTER_ASSERT(reporter, |
| sk_doubles_nearly_equal_ulps(expectedRoots[i], roots[i], 64), |
| "%.16f != %.16f at index %d", expectedRoots[i], roots[i], i); |
| } |
| } |
| } |
| { |
| skiatest::ReporterContext subsubtest(reporter, "SkCubics Implementation"); |
| double roots[3] = {0, 0, 0}; |
| int rootCount = SkCubics::RootsReal(A, B, C, D, roots); |
| REPORTER_ASSERT(reporter, expectedRoots.size() == size_t(rootCount), |
| "Wrong number of roots returned %zu != %d", expectedRoots.size(), |
| rootCount); |
| |
| // We don't care which order the roots are returned from the algorithm. |
| // For determinism, we will sort them (and ensure the provided solutions are also sorted). |
| std::sort(std::begin(roots), std::begin(roots) + rootCount); |
| for (int i = 0; i < rootCount; i++) { |
| if (sk_double_nearly_zero(expectedRoots[i])) { |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[i]), |
| "0 != %.16f at index %d", roots[i], i); |
| } else { |
| REPORTER_ASSERT(reporter, |
| sk_doubles_nearly_equal_ulps(expectedRoots[i], roots[i], 64), |
| "%.16f != %.16f at index %d", expectedRoots[i], roots[i], i); |
| } |
| } |
| } |
| } |
| |
| DEF_TEST(CubicRootsReal_ActualCubics, reporter) { |
| // All answers are given with 16 significant digits (max for a double) or as an integer |
| // when the answer is exact. |
| testCubicRootsReal(reporter, "one root 1x^3 + 2x^2 + 3x + 4", |
| 1, 2, 3, 4, |
| {-1.650629191439388}); |
| //-1.650629191439388218880801 from Wolfram Alpha |
| |
| // (3x-5)(6x-10)(x+4) = 18x^3 + 12x^2 - 190x + 200 |
| testCubicRootsReal(reporter, "touches y axis 18x^3 + 12x^2 - 190x + 200", |
| 18, 12, -190, 200, |
| {-4., |
| 1.666666666666667, // 5/3 |
| }); |
| |
| testCubicRootsReal(reporter, "three roots 10x^3 - 20x^2 - 30x + 40", |
| 10, -20, -30, 40, |
| {-1.561552812808830, |
| //-1.561552812808830274910705 from Wolfram Alpha |
| 1., |
| 2.561552812808830, |
| // 2.561552812808830274910705 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "three roots -10x^3 + 200x^2 + 300x - 400", |
| -10, 200, 300, -400, |
| {-2.179884793243323, |
| //-2.179884793243323422232630 from Wolfram Alpha |
| 0.8607083693981839, |
| // 0.8607083693981838897123320 from Wolfram Alpha |
| 21.31917642384514, |
| //21.31917642384513953252030 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "one root -x^3 + 0x^2 + 5x - 7", |
| -1, 0, 5, -7, |
| {-2.747346540307211, |
| //-2.747346540307210849971436 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "one root 2x^3 - 3x^2 + 0x + 3", |
| 2, -3, 0, 3, |
| {-0.806443932358772, |
| //-0.8064439323587723772036250 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "one root x^3 + 0x^2 + 0x - 9", |
| 1, 0, 0, -9, |
| {2.080083823051904, |
| //2.0800838230519041145300568 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "three roots 2x^3 - 3x^2 - 4x + 0", |
| 2, -3, -4, 0, |
| {-0.8507810593582122, |
| //-0.8507810593582121716220544 from Wolfram Alpha |
| 0., |
| 2.350781059358212 |
| //2.350781059358212171622054 from Wolfram Alpha |
| }); |
| } |
| |
| DEF_TEST(CubicRootsReal_Quadratics, reporter) { |
| testCubicRootsReal(reporter, "two roots -2x^2 + 3x + 4", |
| 0, -2, 3, 4, |
| {-0.8507810593582122, |
| //-0.8507810593582121716220544 from Wolfram Alpha |
| 2.350781059358212, |
| // 2.350781059358212171622054 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "touches y axis -x^2 + 3x + 4", |
| 0, -2, 3, 4, |
| {-0.8507810593582122, |
| //-0.8507810593582121716220544 from Wolfram Alpha |
| 2.350781059358212, |
| // 2.350781059358212171622054 from Wolfram Alpha |
| }); |
| |
| testCubicRootsReal(reporter, "no roots x^2 + 2x + 7", |
| 0, 1, 2, 7, |
| {}); |
| } |
| |
| DEF_TEST(CubicRootsReal_Linear, reporter) { |
| testCubicRootsReal(reporter, "positive slope 3x + 4", |
| 0, 0, 3, 4, |
| {-1.333333333333333}); |
| |
| testCubicRootsReal(reporter, "negative slope -2x - 8", |
| 0, 0, -2, -8, |
| {-4.}); |
| } |
| |
| DEF_TEST(CubicRootsReal_Constant, reporter) { |
| testCubicRootsReal(reporter, "No intersections y = 4", |
| 0, 0, 0, 4, |
| {}); |
| |
| testCubicRootsReal(reporter, "Infinite solutions y = 0", |
| 0, 0, 0, 0, |
| {0.}); |
| } |
| |
| static void testCubicValidT(skiatest::Reporter* reporter, std::string name, |
| double A, double B, double C, double D, |
| SkSpan<const double> expectedRoots) { |
| skiatest::ReporterContext subtest(reporter, name); |
| // Validate test case |
| REPORTER_ASSERT(reporter, expectedRoots.size() <= 3, |
| "Invalid test case, up to 3 roots allowed"); |
| |
| for (size_t i = 0; i < expectedRoots.size(); i++) { |
| double x = expectedRoots[i]; |
| REPORTER_ASSERT(reporter, x >= 0 && x <= 1, |
| "Invalid test case root %zu. Roots must be in [0, 1]", i); |
| |
| // A*x^3 + B*x^2 + C*x + D should equal 0 |
| double y = A * x * x * x + B * x * x + C * x + D; |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(y), |
| "Invalid test case root %zu. %.16f != 0", i, y); |
| |
| if (i > 0) { |
| REPORTER_ASSERT(reporter, expectedRoots[i-1] <= expectedRoots[i], |
| "Invalid test case root %zu. Roots should be sorted in ascending order", i); |
| } |
| } |
| |
| { |
| skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation"); |
| double roots[3] = {0, 0, 0}; |
| int rootCount = SkDCubic::RootsValidT(A, B, C, D, roots); |
| REPORTER_ASSERT(reporter, expectedRoots.size() == size_t(rootCount), |
| "Wrong number of roots returned %zu != %d", |
| expectedRoots.size(), rootCount); |
| |
| // We don't care which order the roots are returned from the algorithm. |
| // For determinism, we will sort them (and ensure the provided solutions are also sorted). |
| std::sort(std::begin(roots), std::begin(roots) + rootCount); |
| for (int i = 0; i < rootCount; i++) { |
| if (sk_double_nearly_zero(expectedRoots[i])) { |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[i]), |
| "0 != %.16f at index %d", roots[i], i); |
| } else { |
| REPORTER_ASSERT(reporter, |
| sk_doubles_nearly_equal_ulps(expectedRoots[i], roots[i], 64), |
| "%.16f != %.16f at index %d", expectedRoots[i], roots[i], i); |
| } |
| } |
| } |
| { |
| skiatest::ReporterContext subsubtest(reporter, "SkCubics Implementation"); |
| double roots[3] = {0, 0, 0}; |
| int rootCount = SkCubics::RootsValidT(A, B, C, D, roots); |
| REPORTER_ASSERT(reporter, expectedRoots.size() == size_t(rootCount), |
| "Wrong number of roots returned %zu != %d", |
| expectedRoots.size(), rootCount); |
| |
| // We don't care which order the roots are returned from the algorithm. |
| // For determinism, we will sort them (and ensure the provided solutions are also sorted). |
| std::sort(std::begin(roots), std::begin(roots) + rootCount); |
| for (int i = 0; i < rootCount; i++) { |
| if (sk_double_nearly_zero(expectedRoots[i])) { |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[i]), |
| "0 != %.16f at index %d", roots[i], i); |
| } else { |
| REPORTER_ASSERT(reporter, |
| sk_doubles_nearly_equal_ulps(expectedRoots[i], roots[i], 64), |
| "%.16f != %.16f at index %d", expectedRoots[i], roots[i], i); |
| } |
| } |
| } |
| } |
| |
| DEF_TEST(CubicRootsValidT, reporter) { |
| // All answers are given with 16 significant digits (max for a double) or as an integer |
| // when the answer is exact. |
| testCubicValidT(reporter, "three roots 24x^3 - 46x^2 + 29x - 6", |
| 24, -46, 29, -6, |
| {0.5, |
| 0.6666666666666667, |
| 0.75}); |
| |
| testCubicValidT(reporter, "one root = 1 10x^3 - 20x^2 - 30x + 40", |
| 10, -20, -30, 40, |
| {1.}); |
| |
| testCubicValidT(reporter, "one root = 0 2x^3 - 3x^2 - 4x + 0", |
| 2, -3, -4, 0, |
| {0.}); |
| |
| testCubicValidT(reporter, "two roots -2x^3 - 3x^2 + 4x + 0", |
| -2, -3, 4, 0, |
| { 0., |
| 0.8507810593582122, |
| // 0.8507810593582121716220544 from Wolfram Alpha |
| }); |
| } |
| |
| DEF_TEST(CubicRootsValidT_ClampToZeroAndOne, reporter) { |
| // (x + 0.00001)(x - 1.00005), but the answers will be 0 and 1 |
| double A = 0.; |
| double B = 1.; |
| double C = -1.00004; |
| double D = -0.0000100005; |
| double roots[3] = {0, 0, 0}; |
| int rootCount = SkDCubic::RootsValidT(A, B, C, D, roots); |
| |
| REPORTER_ASSERT(reporter, rootCount == 2); |
| std::sort(std::begin(roots), std::begin(roots) + rootCount); |
| REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[0]), "%.16f != 0", roots[0]); |
| REPORTER_ASSERT(reporter, sk_doubles_nearly_equal_ulps(roots[1], 1), "%.16f != 1", roots[1]); |
| } |
