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 : * Permission is hereby granted, free of charge, to any person obtaining a
12 : * copy of this software and associated documentation files (the "Software"),
13 : * to deal in the Software without restriction, including without limitation
14 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15 : * and/or sell copies of the Software, and to permit persons to whom the
16 : * Software is furnished to do so, subject to the following conditions:
17 : *
18 : * The above copyright notice and this permission notice shall be included
19 : * in all copies or substantial portions of the Software.
20 : *
21 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 : * DEALINGS IN THE SOFTWARE.
28 : ****************************************************************************/
29 :
30 : #include "cpl_conv.h"
31 : #include "gdal_alg.h"
32 :
33 : #include "gtest_include.h"
34 :
35 : namespace
36 : {
37 :
38 : // Common fixture with test data
39 : struct test_triangulation : public ::testing::Test
40 : {
41 : GDALTriangulation *psDT = nullptr;
42 :
43 3 : void SetUp() override
44 : {
45 3 : if (!GDALHasTriangulation())
46 : {
47 0 : GTEST_SKIP() << "qhull support missing";
48 : }
49 : }
50 :
51 3 : void TearDown() override
52 : {
53 3 : GDALTriangulationFree(psDT);
54 3 : psDT = nullptr;
55 3 : }
56 : };
57 :
58 4 : TEST_F(test_triangulation, error_case_1)
59 : {
60 :
61 1 : double adfX[] = {0, -5, -5, 5, 5};
62 1 : double adfY[] = {0, -5, 5, -5, 5};
63 1 : CPLPushErrorHandler(CPLQuietErrorHandler);
64 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", "YES");
65 1 : psDT = GDALTriangulationCreateDelaunay(2, adfX, adfY);
66 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", nullptr);
67 1 : CPLPopErrorHandler();
68 1 : ASSERT_TRUE(psDT == nullptr);
69 : }
70 :
71 4 : TEST_F(test_triangulation, error_case_2)
72 : {
73 1 : double adfX[] = {0, 1, 2, 3};
74 1 : double adfY[] = {0, 1, 2, 3};
75 1 : CPLPushErrorHandler(CPLQuietErrorHandler);
76 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", "YES");
77 1 : psDT = GDALTriangulationCreateDelaunay(4, adfX, adfY);
78 1 : CPLSetConfigOption("QHULL_LOG_TO_TEMP_FILE", nullptr);
79 1 : CPLPopErrorHandler();
80 1 : ASSERT_TRUE(psDT == nullptr);
81 : }
82 :
83 4 : TEST_F(test_triangulation, nominal)
84 : {
85 : {
86 1 : double adfX[] = {0, -5, -5, 5, 5};
87 1 : double adfY[] = {0, -5, 5, -5, 5};
88 : int i, j;
89 1 : psDT = GDALTriangulationCreateDelaunay(5, adfX, adfY);
90 1 : ASSERT_TRUE(psDT != nullptr);
91 1 : ASSERT_EQ(psDT->nFacets, 4);
92 5 : for (i = 0; i < psDT->nFacets; i++)
93 : {
94 16 : for (j = 0; j < 3; j++)
95 : {
96 12 : ASSERT_TRUE(psDT->pasFacets[i].anVertexIdx[j] >= 0);
97 12 : ASSERT_TRUE(psDT->pasFacets[i].anVertexIdx[j] <= 4);
98 12 : ASSERT_TRUE(psDT->pasFacets[i].anNeighborIdx[j] >= -1);
99 12 : ASSERT_TRUE(psDT->pasFacets[i].anNeighborIdx[j] <= 4);
100 : }
101 : }
102 : int face;
103 1 : CPLPushErrorHandler(CPLQuietErrorHandler);
104 1 : ASSERT_EQ(GDALTriangulationFindFacetDirected(psDT, 0, 0, 0, &face),
105 : FALSE);
106 1 : ASSERT_EQ(GDALTriangulationFindFacetBruteForce(psDT, 0, 0, &face),
107 : FALSE);
108 : double l1, l2, l3;
109 1 : ASSERT_EQ(GDALTriangulationComputeBarycentricCoordinates(psDT, 0, 0, 0,
110 : &l1, &l2, &l3),
111 : FALSE);
112 1 : CPLPopErrorHandler();
113 1 : ASSERT_EQ(
114 : GDALTriangulationComputeBarycentricCoefficients(psDT, adfX, adfY),
115 : TRUE);
116 1 : ASSERT_EQ(
117 : GDALTriangulationComputeBarycentricCoefficients(psDT, adfX, adfY),
118 : TRUE);
119 : }
120 :
121 : // Points inside
122 : {
123 1 : double adfX[] = {0.1, 0.9, 0.499, -0.9};
124 1 : double adfY[] = {0.9, 0.1, -0.5, 0.1};
125 5 : for (int i = 0; i < 4; i++)
126 : {
127 4 : double x = adfX[i];
128 4 : double y = adfY[i];
129 : int new_face;
130 : int face;
131 4 : ASSERT_EQ(GDALTriangulationFindFacetDirected(psDT, 0, x, y, &face),
132 : TRUE);
133 4 : ASSERT_TRUE(face >= 0 && face < 4);
134 4 : ASSERT_EQ(
135 : GDALTriangulationFindFacetDirected(psDT, 1, x, y, &new_face),
136 : TRUE);
137 4 : ASSERT_EQ(face, new_face);
138 4 : ASSERT_EQ(
139 : GDALTriangulationFindFacetDirected(psDT, 2, x, y, &new_face),
140 : TRUE);
141 4 : ASSERT_EQ(face, new_face);
142 4 : ASSERT_EQ(
143 : GDALTriangulationFindFacetDirected(psDT, 3, x, y, &new_face),
144 : TRUE);
145 4 : ASSERT_EQ(face, new_face);
146 4 : ASSERT_EQ(
147 : GDALTriangulationFindFacetBruteForce(psDT, x, y, &new_face),
148 : TRUE);
149 4 : ASSERT_EQ(face, new_face);
150 :
151 : double l1, l2, l3;
152 4 : GDALTriangulationComputeBarycentricCoordinates(psDT, face, x, y,
153 : &l1, &l2, &l3);
154 4 : ASSERT_TRUE(l1 >= 0 && l1 <= 1);
155 4 : ASSERT_TRUE(l2 >= 0 && l2 <= 1);
156 4 : ASSERT_TRUE(l3 >= 0 && l3 <= 1);
157 4 : ASSERT_NEAR(l3, 1.0 - l1 - l2, 1e-10);
158 : }
159 : }
160 :
161 : // Points outside
162 : {
163 1 : double adfX[] = {0, 10, 0, -10};
164 1 : double adfY[] = {10, 0, -10, 0};
165 5 : for (int i = 0; i < 4; i++)
166 : {
167 4 : double x = adfX[i];
168 4 : double y = adfY[i];
169 : int new_face;
170 : int face;
171 4 : ASSERT_EQ(GDALTriangulationFindFacetDirected(psDT, 0, x, y, &face),
172 : FALSE);
173 4 : ASSERT_TRUE(face < 0 || (face >= 0 && face < 4));
174 4 : ASSERT_EQ(
175 : GDALTriangulationFindFacetDirected(psDT, 1, x, y, &new_face),
176 : FALSE);
177 4 : ASSERT_EQ(face, new_face);
178 4 : ASSERT_EQ(
179 : GDALTriangulationFindFacetDirected(psDT, 2, x, y, &new_face),
180 : FALSE);
181 4 : ASSERT_EQ(face, new_face);
182 4 : ASSERT_EQ(
183 : GDALTriangulationFindFacetDirected(psDT, 3, x, y, &new_face),
184 : FALSE);
185 4 : ASSERT_EQ(face, new_face);
186 4 : ASSERT_EQ(
187 : GDALTriangulationFindFacetBruteForce(psDT, x, y, &new_face),
188 : FALSE);
189 4 : ASSERT_EQ(face, new_face);
190 :
191 : double l1, l2, l3;
192 4 : if (face < 0)
193 0 : face = 0;
194 4 : GDALTriangulationComputeBarycentricCoordinates(psDT, face, x, y,
195 : &l1, &l2, &l3);
196 4 : ASSERT_TRUE(!((l1 >= 0 && l1 <= 1) && (l2 >= 0 && l2 <= 1) &&
197 : (l3 >= 0 && l3 <= 1)))
198 0 : << "outside";
199 4 : ASSERT_NEAR(l3, 1.0 - l1 - l2, 1e-10);
200 : }
201 : }
202 : }
203 : } // namespace
|
