diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
commit | cca66b9ec4e494c1d919bff0f71a820d8afab1fa (patch) | |
tree | 146f39ded1c938019e1ed42d30923c2ac9e86789 /src/3rdparty/2geom/tests/convex-hull-test.cpp | |
parent | Initial commit. (diff) | |
download | inkscape-cca66b9ec4e494c1d919bff0f71a820d8afab1fa.tar.xz inkscape-cca66b9ec4e494c1d919bff0f71a820d8afab1fa.zip |
Adding upstream version 1.2.2.upstream/1.2.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/3rdparty/2geom/tests/convex-hull-test.cpp | 335 |
1 files changed, 335 insertions, 0 deletions
diff --git a/src/3rdparty/2geom/tests/convex-hull-test.cpp b/src/3rdparty/2geom/tests/convex-hull-test.cpp new file mode 100644 index 0000000..2f20f43 --- /dev/null +++ b/src/3rdparty/2geom/tests/convex-hull-test.cpp @@ -0,0 +1,335 @@ +/** @file + * @brief Unit tests for ConvexHull and related functions. + * Uses the Google Testing Framework + *//* + * Authors: + * Nathan Hurst <njh@njhurst.com> + * Krzysztof KosiĆski <tweenk.pl@gmail.com> + * + * Copyright 2011-2015 Authors + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + */ + +#include "testing.h" +#include <iostream> + +#include <2geom/convex-hull.h> +#include <vector> +#include <iterator> + +#ifndef M_PI +# define M_PI 3.14159265358979323846 +#endif + +using namespace std; +using namespace Geom; + +void points_from_shape(std::vector<Point> &pts, std::string const &shape) { + pts.clear(); + int x = 0, y = 0; + for (char c : shape) { + if (c == '\n') { + x = 0; ++y; + continue; + } + if (c == ' ') { + ++x; + continue; + } + pts.emplace_back(x, y); + ++x; + } +} + +class ConvexHullTest : public ::testing::Test { +protected: + ConvexHullTest() + : null(hulls[0]) + , point(hulls[1]) + , line(hulls[2]) + , triangle(hulls[3]) + , square(hulls[4]) + , hexagon(hulls[5]) + , antihexagon(hulls[6]) + , gem(hulls[7]) + , diamond(hulls[8]) + { + null = ConvexHull(); + + std::vector<Point> pts; + + pts.emplace_back(0,0); + point = ConvexHull(pts); + pts.emplace_back(1,0); + line = ConvexHull(pts); + pts.emplace_back(0,1); + triangle = ConvexHull(pts); + pts.emplace_back(1,1); + square = ConvexHull(pts); + pts.clear(); + + for(int i = 0; i < 6; i++) { + pts.emplace_back(cos(i*M_PI*2/6), sin(i*M_PI*2/6)); + } + hexagon = ConvexHull(pts); + pts.clear(); + + for(int i = 0; i < 6; i++) { + pts.emplace_back(cos((1-i*2)*M_PI/6), sin((1-i*2)*M_PI/6)); + } + antihexagon = ConvexHull(pts); + pts.clear(); + + gem_shape = + " ++++ \n" + "++++++ \n" + "++++++ \n" + "++++++ \n" + " ++++ \n"; + points_from_shape(pts, gem_shape); + gem.swap(pts); + + diamond_shape = + " + \n" + " +++++ \n" + " +++++ \n" + "+++++++ \n" + " +++++ \n" + " +++++ \n" + " + \n"; + points_from_shape(pts, diamond_shape); + diamond.swap(pts); + } + + ConvexHull hulls[9]; + ConvexHull &null, &point, &line, &triangle, &square, &hexagon, &antihexagon, &gem, ⋄ + std::string gem_shape, diamond_shape; +}; + +void check_convex(ConvexHull &/*ch*/) { + // TODO +} + +TEST_F(ConvexHullTest, SizeAndDegeneracy) { + EXPECT_EQ(0u, null.size()); + EXPECT_TRUE(null.empty()); + EXPECT_TRUE(null.isDegenerate()); + EXPECT_FALSE(null.isSingular()); + EXPECT_FALSE(null.isLinear()); + + EXPECT_EQ(1u, point.size()); + EXPECT_FALSE(point.empty()); + EXPECT_TRUE(point.isDegenerate()); + EXPECT_TRUE(point.isSingular()); + EXPECT_FALSE(point.isLinear()); + + EXPECT_EQ(2u, line.size()); + EXPECT_FALSE(line.empty()); + EXPECT_TRUE(line.isDegenerate()); + EXPECT_FALSE(line.isSingular()); + EXPECT_TRUE(line.isLinear()); + + EXPECT_EQ(3u, triangle.size()); + EXPECT_FALSE(triangle.empty()); + EXPECT_FALSE(triangle.isDegenerate()); + EXPECT_FALSE(triangle.isSingular()); + EXPECT_FALSE(triangle.isLinear()); + + EXPECT_EQ(4u, square.size()); + EXPECT_FALSE(square.empty()); + EXPECT_FALSE(square.isDegenerate()); + EXPECT_FALSE(square.isSingular()); + EXPECT_FALSE(square.isLinear()); + + EXPECT_EQ(6u, hexagon.size()); + EXPECT_FALSE(hexagon.empty()); + EXPECT_FALSE(hexagon.isDegenerate()); + EXPECT_FALSE(hexagon.isSingular()); + EXPECT_FALSE(hexagon.isLinear()); + + EXPECT_EQ(6u, antihexagon.size()); + EXPECT_FALSE(antihexagon.empty()); + EXPECT_FALSE(antihexagon.isDegenerate()); + EXPECT_FALSE(antihexagon.isSingular()); + EXPECT_FALSE(antihexagon.isLinear()); + + EXPECT_EQ(8u, gem.size()); + EXPECT_FALSE(gem.empty()); + EXPECT_FALSE(gem.isDegenerate()); + EXPECT_FALSE(gem.isSingular()); + EXPECT_FALSE(gem.isLinear()); + + EXPECT_EQ(8u, diamond.size()); + EXPECT_FALSE(diamond.empty()); + EXPECT_FALSE(diamond.isDegenerate()); + EXPECT_FALSE(diamond.isSingular()); + EXPECT_FALSE(diamond.isLinear()); +} + + +TEST_F(ConvexHullTest, Area) { + EXPECT_EQ(0, null.area()); + EXPECT_EQ(0, point.area()); + EXPECT_EQ(0, line.area()); + EXPECT_EQ(0.5, triangle.area()); + EXPECT_EQ(1, square.area()); + EXPECT_EQ(18, gem.area()); + EXPECT_EQ(24, diamond.area()); + EXPECT_FLOAT_EQ(6*(0.5*1*sin(M_PI/3)), hexagon.area()); + EXPECT_FLOAT_EQ(6*(0.5*1*sin(M_PI/3)), antihexagon.area()); +} + +TEST_F(ConvexHullTest, Bounds) { + //Rect hexbounds(-1,sin(M_PI/3),1,-sin(M_PI/3)); + + EXPECT_EQ(OptRect(), null.bounds()); + EXPECT_EQ(OptRect(0,0,0,0), point.bounds()); + EXPECT_EQ(OptRect(0,0,1,0), line.bounds()); + EXPECT_EQ(OptRect(0,0,1,1), triangle.bounds()); + EXPECT_EQ(OptRect(0,0,1,1), square.bounds()); + EXPECT_EQ(OptRect(0,0,5,4), gem.bounds()); + EXPECT_EQ(OptRect(0,0,6,6), diamond.bounds()); + //EXPECT_TRUE(hexbounds == hexagon.bounds()); + //EXPECT_TRUE(hexbounds == antihexagon.bounds()); +} + +::testing::AssertionResult HullContainsPoint(ConvexHull const &h, Point const &p) { + if (h.contains(p)) { + return ::testing::AssertionSuccess(); + } else { + return ::testing::AssertionFailure() + << "Convex hull:\n" + << h << "\ndoes not contain " << p; + } +} + +TEST_F(ConvexHullTest, PointContainment) { + Point zero(0,0), half(0.5, 0.5), x(0.25, 0.25); + EXPECT_FALSE(HullContainsPoint(null, zero)); + EXPECT_TRUE(HullContainsPoint(point, zero)); + EXPECT_TRUE(HullContainsPoint(line, zero)); + EXPECT_TRUE(HullContainsPoint(triangle, zero)); + EXPECT_TRUE(HullContainsPoint(square, zero)); + EXPECT_FALSE(HullContainsPoint(line, half)); + EXPECT_TRUE(HullContainsPoint(triangle, x)); + EXPECT_TRUE(HullContainsPoint(triangle, half)); + EXPECT_TRUE(HullContainsPoint(square, half)); + EXPECT_TRUE(HullContainsPoint(hexagon, zero)); + EXPECT_TRUE(HullContainsPoint(antihexagon, zero)); + + std::vector<Point> pts; + + points_from_shape(pts, gem_shape); + for (auto & pt : pts) { + EXPECT_TRUE(HullContainsPoint(gem, pt)); + } + + points_from_shape(pts, diamond_shape); + for (auto & pt : pts) { + EXPECT_TRUE(HullContainsPoint(diamond, pt)); + } + + /*EXPECT_FALSE(null.interiorContains(zero)); + EXPECT_FALSE(point.interiorContains(zero)); + EXPECT_FALSE(line.interiorContains(zero)); + EXPECT_FALSE(triangle.interiorContains(zero)); + EXPECT_FALSE(square.interiorContains(zero)); + EXPECT_FALSE(line.interiorContains(half)); + EXPECT_FALSE(triangle.interiorContains(Point(0,0.5))); + EXPECT_FALSE(triangle.interiorContains(half)); + EXPECT_TRUE(square.interiorContains(half));*/ +} + +TEST_F(ConvexHullTest, ExtremePoints) { + Point zero(0,0); + EXPECT_EQ(0., point.top()); + EXPECT_EQ(0., point.right()); + EXPECT_EQ(0., point.bottom()); + EXPECT_EQ(0., point.left()); + EXPECT_EQ(zero, point.topPoint()); + EXPECT_EQ(zero, point.rightPoint()); + EXPECT_EQ(zero, point.bottomPoint()); + EXPECT_EQ(zero, point.leftPoint()); + + // line from 0,0 to 1,0 + EXPECT_EQ(0., line.top()); + EXPECT_EQ(1., line.right()); + EXPECT_EQ(0., line.bottom()); + EXPECT_EQ(0., line.left()); + EXPECT_EQ(Point(1,0), line.topPoint()); + EXPECT_EQ(Point(1,0), line.rightPoint()); + EXPECT_EQ(Point(0,0), line.bottomPoint()); + EXPECT_EQ(Point(0,0), line.leftPoint()); + + // triangle 0,0 1,0 0,1 + EXPECT_EQ(0., triangle.top()); + EXPECT_EQ(1., triangle.right()); + EXPECT_EQ(1., triangle.bottom()); + EXPECT_EQ(0., triangle.left()); + EXPECT_EQ(Point(1,0), triangle.topPoint()); + EXPECT_EQ(Point(1,0), triangle.rightPoint()); + EXPECT_EQ(Point(0,1), triangle.bottomPoint()); + EXPECT_EQ(Point(0,0), triangle.leftPoint()); + + // square 0,0 to 1,1 + EXPECT_EQ(0., square.top()); + EXPECT_EQ(1., square.right()); + EXPECT_EQ(1., square.bottom()); + EXPECT_EQ(0., square.left()); + EXPECT_EQ(Point(1,0), square.topPoint()); + EXPECT_EQ(Point(1,1), square.rightPoint()); + EXPECT_EQ(Point(0,1), square.bottomPoint()); + EXPECT_EQ(Point(0,0), square.leftPoint()); + + EXPECT_EQ(0., gem.top()); + EXPECT_EQ(5., gem.right()); + EXPECT_EQ(4., gem.bottom()); + EXPECT_EQ(0., gem.left()); + EXPECT_EQ(Point(4,0), gem.topPoint()); + EXPECT_EQ(Point(5,3), gem.rightPoint()); + EXPECT_EQ(Point(1,4), gem.bottomPoint()); + EXPECT_EQ(Point(0,1), gem.leftPoint()); + + EXPECT_EQ(0., diamond.top()); + EXPECT_EQ(6., diamond.right()); + EXPECT_EQ(6., diamond.bottom()); + EXPECT_EQ(0., diamond.left()); + EXPECT_EQ(Point(3,0), diamond.topPoint()); + EXPECT_EQ(Point(6,3), diamond.rightPoint()); + EXPECT_EQ(Point(3,6), diamond.bottomPoint()); + EXPECT_EQ(Point(0,3), diamond.leftPoint()); +} + + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : |