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