Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: GDAL algorithms
4 : * Purpose: Test Delaunay triangulation
5 : * Author: Even Rouault, even.rouault at spatialys.com
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2015, Even Rouault <even.rouault at spatialys.com>
9 : *
10 : * SPDX-License-Identifier: MIT
11 : ****************************************************************************/
12 :
13 : #include "cpl_conv.h"
14 : #include "gdal_alg.h"
15 :
16 : #include "gtest_include.h"
17 :
18 : namespace
19 : {
20 :
21 : // Common fixture with test data
22 : struct test_triangulation : public ::testing::Test
23 : {
24 : GDALTriangulation *psDT = nullptr;
25 :
26 3 : void SetUp() override
27 : {
28 3 : if (!GDALHasTriangulation())
29 : {
30 0 : GTEST_SKIP() << "qhull support missing";
31 : }
32 : }
33 :
34 3 : void TearDown() override
35 : {
36 3 : GDALTriangulationFree(psDT);
37 3 : psDT = nullptr;
38 3 : }
39 : };
40 :
41 4 : TEST_F(test_triangulation, error_case_1)
42 : {
43 :
44 1 : double adfX[] = {0, -5, -5, 5, 5};
45 1 : double adfY[] = {0, -5, 5, -5, 5};
46 1 : CPLPushErrorHandler(CPLQuietErrorHandler);
47 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", "YES");
48 1 : psDT = GDALTriangulationCreateDelaunay(2, adfX, adfY);
49 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", nullptr);
50 1 : CPLPopErrorHandler();
51 1 : ASSERT_TRUE(psDT == nullptr);
52 : }
53 :
54 4 : TEST_F(test_triangulation, error_case_2)
55 : {
56 1 : double adfX[] = {0, 1, 2, 3};
57 1 : double adfY[] = {0, 1, 2, 3};
58 1 : CPLPushErrorHandler(CPLQuietErrorHandler);
59 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", "YES");
60 1 : psDT = GDALTriangulationCreateDelaunay(4, adfX, adfY);
61 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", nullptr);
62 1 : CPLPopErrorHandler();
63 1 : ASSERT_TRUE(psDT == nullptr);
64 : }
65 :
66 4 : TEST_F(test_triangulation, nominal)
67 : {
68 : {
69 1 : double adfX[] = {0, -5, -5, 5, 5};
70 1 : double adfY[] = {0, -5, 5, -5, 5};
71 : int i, j;
72 1 : psDT = GDALTriangulationCreateDelaunay(5, adfX, adfY);
73 1 : ASSERT_TRUE(psDT != nullptr);
74 1 : ASSERT_EQ(psDT->nFacets, 4);
75 5 : for (i = 0; i < psDT->nFacets; i++)
76 : {
77 16 : for (j = 0; j < 3; j++)
78 : {
79 12 : ASSERT_TRUE(psDT->pasFacets[i].anVertexIdx[j] >= 0);
80 12 : ASSERT_TRUE(psDT->pasFacets[i].anVertexIdx[j] <= 4);
81 12 : ASSERT_TRUE(psDT->pasFacets[i].anNeighborIdx[j] >= -1);
82 12 : ASSERT_TRUE(psDT->pasFacets[i].anNeighborIdx[j] <= 4);
83 : }
84 : }
85 : int face;
86 1 : CPLPushErrorHandler(CPLQuietErrorHandler);
87 1 : ASSERT_EQ(GDALTriangulationFindFacetDirected(psDT, 0, 0, 0, &face),
88 : FALSE);
89 1 : ASSERT_EQ(GDALTriangulationFindFacetBruteForce(psDT, 0, 0, &face),
90 : FALSE);
91 : double l1, l2, l3;
92 1 : ASSERT_EQ(GDALTriangulationComputeBarycentricCoordinates(psDT, 0, 0, 0,
93 : &l1, &l2, &l3),
94 : FALSE);
95 1 : CPLPopErrorHandler();
96 1 : ASSERT_EQ(
97 : GDALTriangulationComputeBarycentricCoefficients(psDT, adfX, adfY),
98 : TRUE);
99 1 : ASSERT_EQ(
100 : GDALTriangulationComputeBarycentricCoefficients(psDT, adfX, adfY),
101 : TRUE);
102 : }
103 :
104 : // Points inside
105 : {
106 1 : double adfX[] = {0.1, 0.9, 0.499, -0.9};
107 1 : double adfY[] = {0.9, 0.1, -0.5, 0.1};
108 5 : for (int i = 0; i < 4; i++)
109 : {
110 4 : double x = adfX[i];
111 4 : double y = adfY[i];
112 : int new_face;
113 : int face;
114 4 : ASSERT_EQ(GDALTriangulationFindFacetDirected(psDT, 0, x, y, &face),
115 : TRUE);
116 4 : ASSERT_TRUE(face >= 0 && face < 4);
117 4 : ASSERT_EQ(
118 : GDALTriangulationFindFacetDirected(psDT, 1, x, y, &new_face),
119 : TRUE);
120 4 : ASSERT_EQ(face, new_face);
121 4 : ASSERT_EQ(
122 : GDALTriangulationFindFacetDirected(psDT, 2, x, y, &new_face),
123 : TRUE);
124 4 : ASSERT_EQ(face, new_face);
125 4 : ASSERT_EQ(
126 : GDALTriangulationFindFacetDirected(psDT, 3, x, y, &new_face),
127 : TRUE);
128 4 : ASSERT_EQ(face, new_face);
129 4 : ASSERT_EQ(
130 : GDALTriangulationFindFacetBruteForce(psDT, x, y, &new_face),
131 : TRUE);
132 4 : ASSERT_EQ(face, new_face);
133 :
134 : double l1, l2, l3;
135 4 : GDALTriangulationComputeBarycentricCoordinates(psDT, face, x, y,
136 : &l1, &l2, &l3);
137 4 : ASSERT_TRUE(l1 >= 0 && l1 <= 1);
138 4 : ASSERT_TRUE(l2 >= 0 && l2 <= 1);
139 4 : ASSERT_TRUE(l3 >= 0 && l3 <= 1);
140 4 : ASSERT_NEAR(l3, 1.0 - l1 - l2, 1e-10);
141 : }
142 : }
143 :
144 : // Points outside
145 : {
146 1 : double adfX[] = {0, 10, 0, -10};
147 1 : double adfY[] = {10, 0, -10, 0};
148 5 : for (int i = 0; i < 4; i++)
149 : {
150 4 : double x = adfX[i];
151 4 : double y = adfY[i];
152 : int new_face;
153 : int face;
154 4 : ASSERT_EQ(GDALTriangulationFindFacetDirected(psDT, 0, x, y, &face),
155 : FALSE);
156 4 : ASSERT_TRUE(face < 0 || (face >= 0 && face < 4));
157 4 : ASSERT_EQ(
158 : GDALTriangulationFindFacetDirected(psDT, 1, x, y, &new_face),
159 : FALSE);
160 4 : ASSERT_EQ(face, new_face);
161 4 : ASSERT_EQ(
162 : GDALTriangulationFindFacetDirected(psDT, 2, x, y, &new_face),
163 : FALSE);
164 4 : ASSERT_EQ(face, new_face);
165 4 : ASSERT_EQ(
166 : GDALTriangulationFindFacetDirected(psDT, 3, x, y, &new_face),
167 : FALSE);
168 4 : ASSERT_EQ(face, new_face);
169 4 : ASSERT_EQ(
170 : GDALTriangulationFindFacetBruteForce(psDT, x, y, &new_face),
171 : FALSE);
172 4 : ASSERT_EQ(face, new_face);
173 :
174 : double l1, l2, l3;
175 4 : if (face < 0)
176 0 : face = 0;
177 4 : GDALTriangulationComputeBarycentricCoordinates(psDT, face, x, y,
178 : &l1, &l2, &l3);
179 4 : ASSERT_TRUE(!((l1 >= 0 && l1 <= 1) && (l2 >= 0 && l2 <= 1) &&
180 : (l3 >= 0 && l3 <= 1)))
181 0 : << "outside";
182 4 : ASSERT_NEAR(l3, 1.0 - l1 - l2, 1e-10);
183 : }
184 : }
185 : }
186 : } // namespace
|
