Debian Codegraph @

test/unit/cpp/geometry/ConvexTriangulation.cpp

raw
1 // Copyright (C) 2017 Benjamin Kehlet
2 //
3 // This file is part of DOLFIN.
4 //
5 // DOLFIN is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU Lesser General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // DOLFIN is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
17 //
18 // Unit tests for convex triangulation
19
20 #include <dolfin/geometry/ConvexTriangulation.h>
21 #include <dolfin/geometry/CollisionPredicates.h>
22 #include <dolfin/geometry/predicates.h>
23 #include <catch.hpp>
24
25 using namespace dolfin;
26
27 namespace
28 {
29 bool pure_triangular(const std::vector<std::vector<Point>>& triangulation, std::size_t dim)
30 {
31 for (const std::vector<Point>& tri : triangulation)
32 {
33
34 if (tri.size() != dim+1)
35 return false;
36 }
37
38 return true;
39 }
40
41 bool has_degenerate(const std::vector<std::vector<Point>>& triangulation, std::size_t dim)
42 {
43 for (const std::vector<Point>& tri : triangulation)
44 {
45 if (orient3d(tri[0], tri[1], tri[2], tri[3]) == 0)
46 return true;
47 }
48 return false;
49 }
50
51 bool triangulation_selfintersects(const std::vector<std::vector<Point>>& triangulation,
52 std::size_t dim)
53 {
54 for (std::size_t i = 0; i < triangulation.size(); i++)
55 {
56 const auto& t1 = triangulation[i];
57 for (std::size_t j = i+1; j < triangulation.size(); j++)
58 {
59 const auto& t2 = triangulation[j];
60
61 // Count number of shared vertices
62 std::size_t shared_vertices = 0;
63 std::set<std::size_t> t1_shared;
64 std::set<std::size_t> t2_shared;
65 for (std::size_t v1 = 0; v1 < dim+1; v1++)
66 {
67 for (std::size_t v2 = 0; v2 < dim+1; v2++)
68 {
69 if (t1[v1] == t2[v2])
70 {
71 shared_vertices++;
72 t1_shared.insert(v1);
73 t2_shared.insert(v2);
74 }
75 }
76 }
77
78 if (dim == 3)
79 {
80 if (shared_vertices == 0 &&
81 CollisionPredicates::collides_tetrahedron_tetrahedron_3d(t1[0], t1[1], t1[2], t1[3],
82 t2[0], t2[1], t2[2], t2[3]))
83 {
84 return true;
85 }
86 else if (shared_vertices > 0)
87 {
88
89 for (std::size_t a = 0; a < dim+1; a++)
90 {
91 // None of the non-shared vertices should collide with the other tet
92 if (t1_shared.count(a) == 0 &&
93 CollisionPredicates::collides_tetrahedron_point_3d(t2[0], t2[1], t2[2], t2[3],
94 t1[a]))
95 {
96 return true;
97 }
98
99 if (t2_shared.count(a) == 0 &&
100 CollisionPredicates::collides_tetrahedron_point_3d(t1[0], t1[1], t1[2], t1[3],
101 t2[a]))
102 {
103 return true;
104 }
105 }
106 }
107 }
108 else if(dim == 2)
109 {
110 if (shared_vertices == 0 &&
111 CollisionPredicates::collides_triangle_triangle_2d(t1[0],
112 t1[1],
113 t1[2],
114 t2[0],
115 t2[1],
116 t2[2]))
117 {
118 return true;
119 }
120 }
121 }
122 }
123 return false;
124 }
125 //-----------------------------------------------------------------------------
126 double triangulation_volume(const std::vector<std::vector<dolfin::Point>>& triangulation)
127 {
128 double vol = 0;
129 for (const std::vector<dolfin::Point>& tri : triangulation)
130 {
131 const Point& x0 = tri[0];
132 const Point& x1 = tri[1];
133 const Point& x2 = tri[2];
134 const Point& x3 = tri[3];
135 // Formula for volume from http://mathworld.wolfram.com
136 const double v = (x0[0]*(x1[1]*x2[2] + x3[1]*x1[2] + x2[1]*x3[2]
137 - x2[1]*x1[2] - x1[1]*x3[2] - x3[1]*x2[2])
138 - x1[0]*(x0[1]*x2[2] + x3[1]*x0[2] + x2[1]*x3[2]
139 - x2[1]*x0[2] - x0[1]*x3[2] - x3[1]*x2[2])
140 + x2[0]*(x0[1]*x1[2] + x3[1]*x0[2] + x1[1]*x3[2]
141 - x1[1]*x0[2] - x0[1]*x3[2] - x3[1]*x1[2])
142 - x3[0]*(x0[1]*x1[2] + x1[1]*x2[2] + x2[1]*x0[2]
143 - x1[1]*x0[2] - x2[1]*x1[2] - x0[1]*x2[2]));
144 vol += std::abs(v);
145 }
146
147 return vol/6;
148 }
149 }
150
151 //-----------------------------------------------------------------------------
152 TEST_CASE("Convex triangulation test")
153 {
154 SECTION("test trivial case]")
155 {
156 std::vector<Point> input = {{Point(0,0,0),
157 Point(0,0,1),
158 Point(0,1,0),
159 Point(1,0,0)}};
160
161 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
162 std::size_t expected_size = 1;
163
164 CHECK(tri.size() == expected_size);
165 CHECK(triangulation_volume(tri) == Approx(1.0/6.0));
166 }
167
168 SECTION("test trivial case 2")
169 {
170 std::vector<Point> input = {{Point(0,0,0),
171 Point(0,0,1),
172 Point(0,1,0),
173 Point(0,1,1),
174 Point(1,0,0),
175 Point(1,0,1),
176 Point(1,1,0),
177 Point(1,1,1)}};
178
179 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
180
181 CHECK(pure_triangular(tri, 3));
182 CHECK_FALSE(has_degenerate(tri, 3));
183 CHECK_FALSE(triangulation_selfintersects(tri, 3));
184 CHECK(triangulation_volume(tri) == Approx(1.0));
185 }
186
187 SECTION("test coplanar points")
188 {
189 std::vector<Point> input {
190 Point(0, 0, 0),
191 Point(0, 0, 1),
192 Point(0, 1, 0),
193 Point(0, 1, 1),
194 Point(1, 0, 0),
195 Point(1, 0, 1),
196 Point(1, 1, 0),
197 Point(1, 1, 1),
198 Point(0.1, 0.1, 0)};
199
200 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
201
202 CHECK(pure_triangular(tri, 3));
203 CHECK_FALSE(has_degenerate(tri, 3));
204 CHECK_FALSE(triangulation_selfintersects(tri, 3));
205 CHECK(triangulation_volume(tri) == Approx(1.0));
206 }
207
208 SECTION("test coplanar colinear points]")
209 {
210 std::vector<Point> input {
211 Point(0, 0, 0),
212 Point(0, 0, 1),
213 Point(0, 1, 0),
214 Point(0, 1, 1),
215 Point(1, 0, 0),
216 Point(1, 0, 1),
217 Point(1, 1, 0),
218 Point(1, 1, 1),
219 Point(0, 0.1, 0)};
220
221 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
222
223 CHECK(pure_triangular(tri, 3));
224 CHECK_FALSE(has_degenerate(tri, 3));
225 CHECK_FALSE(triangulation_selfintersects(tri, 3));
226 CHECK(triangulation_volume(tri) == Approx(1.0));
227 }
228
229 SECTION("test failing case")
230 {
231 std::vector<Point> input {
232 Point(0.7, 0.6, 0.1),
233 Point(0.7, 0.6, 0.5),
234 Point(0.1, 0.1, 0.1),
235 Point(0.8333333333333333, 0.8333333333333333, 0),
236 Point(0.1, 0.15, 0.1),
237 Point(0.1, 0.45, 0.1),
238 Point(0.16, 0.15, 0.1),
239 Point(0.61, 0.525, 0.1),
240 Point(0.46, 0.6, 0.100000000000000006) };
241
242 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
243
244 CHECK(pure_triangular(tri, 3));
245 CHECK_FALSE(has_degenerate(tri, 3));
246 CHECK_FALSE(triangulation_selfintersects(tri, 3));
247 }
248
249 SECTION("test failing case 2")
250 {
251 std::vector<Point> input {
252 Point(0.7, 0.6, 0.5),
253 Point(0.7, 0.1, 0.1),
254 Point(0.8, 0, 0),
255 Point (0.1, 0.1, 0.1),
256 Point(0.16, 0.1, 0.1),
257 Point(0.592, 0.1, 0.1),
258 Point (0.16, 0.1, 0.14),
259 Point (0.52, 0.1, 0.38),
260 Point (0.7, 0.1, 0.38)};
261
262 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
263
264 CHECK(pure_triangular(tri, 3));
265 CHECK_FALSE(has_degenerate(tri, 3));
266 CHECK_FALSE(triangulation_selfintersects(tri, 3));
267 }
268
269 SECTION("test failing case 3")
270 {
271 std::vector<Point> input {
272 Point (0.495926, 0.512037, 0.144444),
273 Point (0.376482, 0.519121, 0.284321),
274 Point (0.386541, 0.599783, 0.0609262),
275 Point (0.388086, 0.60059, 0.0607155),
276 Point (0.7, 0.6, 0.5),
277 Point (0.504965, 0.504965, 0.0447775),
278 Point (0.833333, 0.833333, 0)};
279
280 std::vector<std::vector<Point>> tri = ConvexTriangulation::triangulate_graham_scan_3d(input);
281
282 CHECK(pure_triangular(tri, 3));
283 CHECK_FALSE(has_degenerate(tri, 3));
284 CHECK_FALSE(triangulation_selfintersects(tri, 3));
285 }
286 }
287 //-----------------------------------------------------------------------------