1#[cfg(test)]
6mod tests {
7 use crate::computational_geometry::HalfEdgeMesh;
8 use crate::computational_geometry::Line2D;
9 use crate::computational_geometry::LineArrangement;
10 use crate::computational_geometry::Obstacle2D;
11 use crate::computational_geometry::Point2;
12 use crate::computational_geometry::Segment2D;
13 use crate::computational_geometry::SlabPointLocator;
14 use crate::computational_geometry::VisibilityGraph;
15 use crate::computational_geometry::*;
16 use std::ops::{Add, Sub};
17 #[test]
18 fn test_point2_add_sub() {
19 let a = Point2::new(1.0, 2.0);
20 let b = Point2::new(3.0, 4.0);
21 let s = a.add(b);
22 assert!((s.x - 4.0).abs() < 1e-12);
23 assert!((s.y - 6.0).abs() < 1e-12);
24 let d = b.sub(a);
25 assert!((d.x - 2.0).abs() < 1e-12);
26 }
27 #[test]
28 fn test_point2_cross() {
29 let a = Point2::new(1.0, 0.0);
30 let b = Point2::new(0.0, 1.0);
31 assert!((a.cross(b) - 1.0).abs() < 1e-12);
32 assert!((b.cross(a) + 1.0).abs() < 1e-12);
33 }
34 #[test]
35 fn test_point2_dist() {
36 let a = Point2::new(0.0, 0.0);
37 let b = Point2::new(3.0, 4.0);
38 assert!((a.dist(b) - 5.0).abs() < 1e-10);
39 }
40 #[test]
41 fn test_cross2_ccw() {
42 let a = Point2::new(0.0, 0.0);
43 let b = Point2::new(1.0, 0.0);
44 let c = Point2::new(0.5, 1.0);
45 assert!(Point2::cross2(a, b, c) > 0.0);
46 }
47 #[test]
48 fn test_cross3_orthogonal() {
49 let x: Point3 = [1.0, 0.0, 0.0];
50 let y: Point3 = [0.0, 1.0, 0.0];
51 let z = cross3(x, y);
52 assert!((z[0]).abs() < 1e-12);
53 assert!((z[1]).abs() < 1e-12);
54 assert!((z[2] - 1.0).abs() < 1e-12);
55 }
56 #[test]
57 fn test_normalize3() {
58 let v: Point3 = [3.0, 4.0, 0.0];
59 let n = normalize3(v);
60 assert!((mag3(n) - 1.0).abs() < 1e-12);
61 }
62 #[test]
63 fn test_dot3() {
64 let a: Point3 = [1.0, 0.0, 0.0];
65 let b: Point3 = [0.0, 1.0, 0.0];
66 assert!((dot3(a, b)).abs() < 1e-12);
67 let c: Point3 = [2.0, 3.0, 4.0];
68 assert!((dot3(c, c) - 29.0).abs() < 1e-12);
69 }
70 #[test]
71 fn test_halfedge_add_triangle() {
72 let mut mesh = HalfEdgeMesh::new();
73 let v0 = mesh.add_vertex([0.0, 0.0, 0.0]);
74 let v1 = mesh.add_vertex([1.0, 0.0, 0.0]);
75 let v2 = mesh.add_vertex([0.0, 1.0, 0.0]);
76 let fid = mesh.add_triangle(v0, v1, v2);
77 assert_eq!(mesh.num_faces(), 1);
78 let verts = mesh.face_vertices(fid);
79 assert_eq!(verts.len(), 3);
80 }
81 #[test]
82 fn test_halfedge_face_normal_up() {
83 let mut mesh = HalfEdgeMesh::new();
84 let v0 = mesh.add_vertex([0.0, 0.0, 0.0]);
85 let v1 = mesh.add_vertex([1.0, 0.0, 0.0]);
86 let v2 = mesh.add_vertex([0.0, 1.0, 0.0]);
87 let fid = mesh.add_triangle(v0, v1, v2);
88 let n = mesh.face_normal(fid);
89 assert!(n[2] > 0.9);
90 }
91 #[test]
92 fn test_halfedge_face_centroid() {
93 let mut mesh = HalfEdgeMesh::new();
94 let v0 = mesh.add_vertex([0.0, 0.0, 0.0]);
95 let v1 = mesh.add_vertex([3.0, 0.0, 0.0]);
96 let v2 = mesh.add_vertex([0.0, 3.0, 0.0]);
97 let fid = mesh.add_triangle(v0, v1, v2);
98 let c = mesh.face_centroid(fid);
99 assert!((c[0] - 1.0).abs() < 1e-10);
100 assert!((c[1] - 1.0).abs() < 1e-10);
101 }
102 #[test]
103 fn test_halfedge_twin_links() {
104 let mut mesh = HalfEdgeMesh::new();
105 let v0 = mesh.add_vertex([0.0, 0.0, 0.0]);
106 let v1 = mesh.add_vertex([1.0, 0.0, 0.0]);
107 let v2 = mesh.add_vertex([0.0, 1.0, 0.0]);
108 let v3 = mesh.add_vertex([1.0, 1.0, 0.0]);
109 mesh.add_triangle(v0, v1, v2);
110 mesh.add_triangle(v1, v3, v2);
111 mesh.build_twin_links();
112 let has_twin = mesh.half_edges.iter().any(|he| he.twin != usize::MAX);
113 assert!(has_twin);
114 }
115 #[test]
116 fn test_convex_hull_3d_tetrahedron() {
117 let pts: Vec<Point3> = vec![
118 [0.0, 0.0, 0.0],
119 [1.0, 0.0, 0.0],
120 [0.0, 1.0, 0.0],
121 [0.0, 0.0, 1.0],
122 ];
123 let hull = convex_hull_3d(&pts).expect("Hull should succeed");
124 assert_eq!(hull.faces.len(), 4);
125 }
126 #[test]
127 fn test_convex_hull_3d_cube_faces() {
128 let pts: Vec<Point3> = vec![
129 [0.0, 0.0, 0.0],
130 [1.0, 0.0, 0.0],
131 [0.0, 1.0, 0.0],
132 [1.0, 1.0, 0.0],
133 [0.0, 0.0, 1.0],
134 [1.0, 0.0, 1.0],
135 [0.0, 1.0, 1.0],
136 [1.0, 1.0, 1.0],
137 ];
138 let hull = convex_hull_3d(&pts).expect("Cube hull should succeed");
139 assert!(hull.faces.len() >= 12);
140 }
141 #[test]
142 fn test_convex_hull_3d_volume_tetrahedron() {
143 let pts: Vec<Point3> = vec![
144 [0.0, 0.0, 0.0],
145 [6.0, 0.0, 0.0],
146 [0.0, 6.0, 0.0],
147 [0.0, 0.0, 6.0],
148 ];
149 let hull = convex_hull_3d(&pts).expect("Hull should succeed");
150 let vol = hull.volume();
151 assert!((vol - 36.0).abs() < 1.0, "Volume was {vol}");
152 }
153 #[test]
154 fn test_convex_hull_3d_surface_area_tetrahedron() {
155 let pts: Vec<Point3> = vec![
156 [0.0, 0.0, 0.0],
157 [1.0, 0.0, 0.0],
158 [0.0, 1.0, 0.0],
159 [0.0, 0.0, 1.0],
160 ];
161 let hull = convex_hull_3d(&pts).expect("Hull should succeed");
162 let sa = hull.surface_area();
163 assert!(sa > 2.0 && sa < 3.0, "Surface area was {sa}");
164 }
165 #[test]
166 fn test_sutherland_hodgman_unit_squares_overlap() {
167 let sq: Vec<Point2> = vec![
168 Point2::new(0.0, 0.0),
169 Point2::new(1.0, 0.0),
170 Point2::new(1.0, 1.0),
171 Point2::new(0.0, 1.0),
172 ];
173 let result = sutherland_hodgman(&sq, &sq);
174 assert!(result.len() >= 4);
175 let area = polygon_area(&result).abs();
176 assert!((area - 1.0).abs() < 1e-9);
177 }
178 #[test]
179 fn test_sutherland_hodgman_half_overlap() {
180 let subject = vec![
181 Point2::new(0.0, 0.0),
182 Point2::new(2.0, 0.0),
183 Point2::new(2.0, 1.0),
184 Point2::new(0.0, 1.0),
185 ];
186 let clip = vec![
187 Point2::new(0.0, 0.0),
188 Point2::new(1.0, 0.0),
189 Point2::new(1.0, 1.0),
190 Point2::new(0.0, 1.0),
191 ];
192 let result = sutherland_hodgman(&subject, &clip);
193 let area = polygon_area(&result).abs();
194 assert!((area - 1.0).abs() < 1e-9);
195 }
196 #[test]
197 fn test_sutherland_hodgman_no_overlap() {
198 let sq1 = vec![
199 Point2::new(0.0, 0.0),
200 Point2::new(1.0, 0.0),
201 Point2::new(1.0, 1.0),
202 Point2::new(0.0, 1.0),
203 ];
204 let sq2 = vec![
205 Point2::new(2.0, 0.0),
206 Point2::new(3.0, 0.0),
207 Point2::new(3.0, 1.0),
208 Point2::new(2.0, 1.0),
209 ];
210 let result = sutherland_hodgman(&sq1, &sq2);
211 assert!(result.is_empty());
212 }
213 #[test]
214 fn test_polygon_area_square() {
215 let sq = vec![
216 Point2::new(0.0, 0.0),
217 Point2::new(2.0, 0.0),
218 Point2::new(2.0, 2.0),
219 Point2::new(0.0, 2.0),
220 ];
221 assert!((polygon_area(&sq) - 4.0).abs() < 1e-10);
222 }
223 #[test]
224 fn test_minkowski_sum_two_unit_squares() {
225 let sq = vec![
226 Point2::new(0.0, 0.0),
227 Point2::new(1.0, 0.0),
228 Point2::new(1.0, 1.0),
229 Point2::new(0.0, 1.0),
230 ];
231 let result = minkowski_sum(&sq, &sq);
232 assert!(result.len() >= 4);
233 let area = polygon_area(&result).abs();
234 assert!(area > 3.5 && area < 4.5, "Area was {area}");
235 }
236 #[test]
237 fn test_minkowski_sum_nonempty() {
238 let tri = vec![
239 Point2::new(0.0, 0.0),
240 Point2::new(1.0, 0.0),
241 Point2::new(0.0, 1.0),
242 ];
243 let sq = vec![
244 Point2::new(0.0, 0.0),
245 Point2::new(1.0, 0.0),
246 Point2::new(1.0, 1.0),
247 Point2::new(0.0, 1.0),
248 ];
249 let result = minkowski_sum(&tri, &sq);
250 assert!(!result.is_empty());
251 }
252 #[test]
253 fn test_line_arrangement_three_lines() {
254 let lines = vec![
255 Line2D::through(Point2::new(0.0, 0.0), Point2::new(1.0, 0.0)),
256 Line2D::through(Point2::new(0.0, 1.0), Point2::new(1.0, 2.0)),
257 Line2D::through(Point2::new(0.0, 3.0), Point2::new(3.0, 0.0)),
258 ];
259 let arr = LineArrangement::build(&lines);
260 assert_eq!(arr.num_vertices(), 3);
261 }
262 #[test]
263 fn test_line_arrangement_two_lines_one_vertex() {
264 let lines = vec![
265 Line2D::through(Point2::new(0.0, 0.0), Point2::new(1.0, 0.0)),
266 Line2D::through(Point2::new(0.5, -1.0), Point2::new(0.5, 1.0)),
267 ];
268 let arr = LineArrangement::build(&lines);
269 assert_eq!(arr.num_vertices(), 1);
270 let v = &arr.vertices[0];
271 assert!((v.point.x - 0.5).abs() < 1e-9);
272 assert!((v.point.y).abs() < 1e-9);
273 }
274 #[test]
275 fn test_line_intersect_2d_basic() {
276 let l1 = Line2D {
277 a: 1.0,
278 b: 0.0,
279 c: 2.0,
280 };
281 let l2 = Line2D {
282 a: 0.0,
283 b: 1.0,
284 c: 3.0,
285 };
286 let pt = line_intersect_2d(&l1, &l2).expect("Should intersect");
287 assert!((pt.x - 2.0).abs() < 1e-10);
288 assert!((pt.y - 3.0).abs() < 1e-10);
289 }
290 #[test]
291 fn test_line_intersect_parallel() {
292 let l1 = Line2D {
293 a: 1.0,
294 b: 0.0,
295 c: 1.0,
296 };
297 let l2 = Line2D {
298 a: 1.0,
299 b: 0.0,
300 c: 2.0,
301 };
302 assert!(line_intersect_2d(&l1, &l2).is_none());
303 }
304 #[test]
305 fn test_slab_locator_build() {
306 let segs = vec![
307 Segment2D::new(Point2::new(0.0, 1.0), Point2::new(4.0, 1.0)),
308 Segment2D::new(Point2::new(0.0, 2.0), Point2::new(4.0, 2.0)),
309 ];
310 let locator = SlabPointLocator::build(&segs, &[None, None]);
311 assert!(!locator.slab_xs.is_empty());
312 }
313 #[test]
314 fn test_slab_locator_query_above_first() {
315 let segs = vec![Segment2D::new(Point2::new(0.0, 1.0), Point2::new(4.0, 1.0))];
316 let locator = SlabPointLocator::build(&segs, &[None]);
317 let result = locator.locate(Point2::new(2.0, 0.5));
318 assert_eq!(result, Some(0));
319 }
320 #[test]
321 fn test_slab_locator_query_above_all() {
322 let segs = vec![Segment2D::new(Point2::new(0.0, 1.0), Point2::new(4.0, 1.0))];
323 let locator = SlabPointLocator::build(&segs, &[None]);
324 let result = locator.locate(Point2::new(2.0, 5.0));
325 assert!(result.is_none());
326 }
327 #[test]
328 fn test_visibility_graph_no_obstacles() {
329 let vg = VisibilityGraph::build(&[]);
330 assert_eq!(vg.num_nodes(), 0);
331 }
332 #[test]
333 fn test_visibility_graph_square_obstacle() {
334 let obs = Obstacle2D::new(vec![
335 Point2::new(0.0, 0.0),
336 Point2::new(1.0, 0.0),
337 Point2::new(1.0, 1.0),
338 Point2::new(0.0, 1.0),
339 ]);
340 let vg = VisibilityGraph::build(&[obs]);
341 assert_eq!(vg.num_nodes(), 4);
342 }
343 #[test]
344 fn test_visibility_graph_adjacent_vertices_visible() {
345 let obs = Obstacle2D::new(vec![
346 Point2::new(0.0, 0.0),
347 Point2::new(1.0, 0.0),
348 Point2::new(1.0, 1.0),
349 Point2::new(0.0, 1.0),
350 ]);
351 let vg = VisibilityGraph::build(&[obs]);
352 let v0_sees_v1 = vg.edges[0].contains(&1);
353 assert!(v0_sees_v1);
354 }
355 #[test]
356 fn test_art_gallery_triangle() {
357 let tri = vec![
358 Point2::new(0.0, 0.0),
359 Point2::new(4.0, 0.0),
360 Point2::new(2.0, 4.0),
361 ];
362 let result = art_gallery_greedy(&tri, 3);
363 assert!(!result.guards.is_empty());
364 assert!(result.covered.iter().all(|&c| c));
365 }
366 #[test]
367 fn test_art_gallery_square_one_guard() {
368 let sq = vec![
369 Point2::new(0.0, 0.0),
370 Point2::new(4.0, 0.0),
371 Point2::new(4.0, 4.0),
372 Point2::new(0.0, 4.0),
373 ];
374 let result = art_gallery_greedy(&sq, 4);
375 assert!(result.covered.iter().all(|&c| c));
376 }
377 #[test]
378 fn test_check_full_coverage_with_guard() {
379 let tri = vec![
380 Point2::new(0.0, 0.0),
381 Point2::new(1.0, 0.0),
382 Point2::new(0.0, 1.0),
383 ];
384 assert!(check_full_coverage(&tri, &[0]));
385 }
386 #[test]
387 fn test_delaunay_four_points() {
388 let pts = vec![
389 Point2::new(0.0, 0.0),
390 Point2::new(1.0, 0.0),
391 Point2::new(1.0, 1.0),
392 Point2::new(0.0, 1.0),
393 ];
394 let tris = delaunay_2d(&pts);
395 assert_eq!(tris.len(), 2);
396 }
397 #[test]
398 fn test_delaunay_triangle_count() {
399 let pts: Vec<Point2> = (0..6)
400 .map(|i| {
401 let angle = i as f64 * std::f64::consts::TAU / 6.0;
402 Point2::new(angle.cos(), angle.sin())
403 })
404 .collect();
405 let tris = delaunay_2d(&pts);
406 assert!(!tris.is_empty());
407 }
408 #[test]
409 fn test_circumcircle_2d_basic() {
410 let a = Point2::new(0.0, 0.0);
411 let b = Point2::new(1.0, 0.0);
412 let c = Point2::new(0.5, 1.0);
413 let result = circumcircle_2d(a, b, c);
414 assert!(result.is_some());
415 let (center, r2) = result.unwrap();
416 let r2a = center.dist_sq(a);
417 let r2b = center.dist_sq(b);
418 assert!((r2a - r2b).abs() < 1e-9);
419 assert!((r2a - r2).abs() < 1e-9);
420 }
421 #[test]
422 fn test_in_circumcircle_2d() {
423 let a = Point2::new(0.0, 0.0);
424 let b = Point2::new(2.0, 0.0);
425 let c = Point2::new(1.0, 2.0);
426 let inside = Point2::new(1.0, 0.5);
427 let outside = Point2::new(5.0, 5.0);
428 assert!(in_circumcircle_2d(a, b, c, inside));
429 assert!(!in_circumcircle_2d(a, b, c, outside));
430 }
431 #[test]
432 fn test_voronoi_from_delaunay_four_points() {
433 let pts = vec![
434 Point2::new(0.0, 0.0),
435 Point2::new(2.0, 0.0),
436 Point2::new(2.0, 2.0),
437 Point2::new(0.0, 2.0),
438 ];
439 let tris = delaunay_2d(&pts);
440 let cells = voronoi_from_delaunay(&pts, &tris);
441 assert_eq!(cells.len(), 4);
442 for cell in &cells {
443 assert!(!cell.circumcenters.is_empty());
444 }
445 }
446 #[test]
447 fn test_ccw_positive() {
448 let a = Point2::new(0.0, 0.0);
449 let b = Point2::new(1.0, 0.0);
450 let c = Point2::new(0.5, 1.0);
451 assert!(ccw(a, b, c));
452 assert!(!ccw(a, c, b));
453 }
454 #[test]
455 fn test_collinear() {
456 let a = Point2::new(0.0, 0.0);
457 let b = Point2::new(1.0, 1.0);
458 let c = Point2::new(2.0, 2.0);
459 assert!(collinear(a, b, c));
460 let d = Point2::new(1.0, 1.5);
461 assert!(!collinear(a, b, d));
462 }
463 #[test]
464 fn test_point_in_triangle() {
465 let a = Point2::new(0.0, 0.0);
466 let b = Point2::new(3.0, 0.0);
467 let c = Point2::new(0.0, 3.0);
468 assert!(point_in_triangle(Point2::new(0.5, 0.5), a, b, c));
469 assert!(!point_in_triangle(Point2::new(3.0, 3.0), a, b, c));
470 }
471 #[test]
472 fn test_point_in_convex_polygon() {
473 let sq = vec![
474 Point2::new(0.0, 0.0),
475 Point2::new(4.0, 0.0),
476 Point2::new(4.0, 4.0),
477 Point2::new(0.0, 4.0),
478 ];
479 assert!(point_in_convex_polygon(Point2::new(2.0, 2.0), &sq));
480 assert!(!point_in_convex_polygon(Point2::new(5.0, 2.0), &sq));
481 }
482 #[test]
483 fn test_convex_hull_2d_square() {
484 let pts = vec![
485 Point2::new(0.0, 0.0),
486 Point2::new(1.0, 0.0),
487 Point2::new(1.0, 1.0),
488 Point2::new(0.0, 1.0),
489 Point2::new(0.5, 0.5),
490 ];
491 let hull = convex_hull_2d(&pts);
492 assert_eq!(hull.len(), 4);
493 }
494 #[test]
495 fn test_convex_hull_2d_triangle() {
496 let pts = vec![
497 Point2::new(0.0, 0.0),
498 Point2::new(2.0, 0.0),
499 Point2::new(1.0, 2.0),
500 Point2::new(1.0, 0.5),
501 ];
502 let hull = convex_hull_2d(&pts);
503 assert_eq!(hull.len(), 3);
504 }
505 #[test]
506 fn test_segments_properly_intersect_yes() {
507 let p = Point2::new(0.0, 0.0);
508 let q = Point2::new(2.0, 2.0);
509 let a = Point2::new(0.0, 2.0);
510 let b = Point2::new(2.0, 0.0);
511 assert!(segments_properly_intersect(p, q, a, b));
512 }
513 #[test]
514 fn test_segments_properly_intersect_no() {
515 let p = Point2::new(0.0, 0.0);
516 let q = Point2::new(1.0, 0.0);
517 let a = Point2::new(2.0, 0.0);
518 let b = Point2::new(3.0, 0.0);
519 assert!(!segments_properly_intersect(p, q, a, b));
520 }
521 #[test]
522 fn test_segment2d_y_at() {
523 let s = Segment2D::new(Point2::new(0.0, 0.0), Point2::new(4.0, 4.0));
524 assert!((s.y_at(2.0).unwrap() - 2.0).abs() < 1e-10);
525 assert!(s.y_at(5.0).is_none());
526 }
527 #[test]
528 fn test_line2d_through_signed_dist() {
529 let l = Line2D::through(Point2::new(0.0, 2.0), Point2::new(1.0, 2.0));
530 let above = Point2::new(0.5, 5.0);
531 let below = Point2::new(0.5, 0.0);
532 assert!(l.signed_dist(above) * l.signed_dist(below) < 0.0);
533 }
534 #[test]
535 fn test_convex_hull_3d_insufficient_points() {
536 let pts: Vec<Point3> = vec![[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
537 assert!(convex_hull_3d(&pts).is_none());
538 }
539 #[test]
540 fn test_obstacle_edges_count() {
541 let obs = Obstacle2D::new(vec![
542 Point2::new(0.0, 0.0),
543 Point2::new(1.0, 0.0),
544 Point2::new(1.0, 1.0),
545 Point2::new(0.0, 1.0),
546 ]);
547 assert_eq!(obs.edges().len(), 4);
548 }
549 #[test]
550 fn test_euler_face_count() {
551 let lines = vec![
552 Line2D::through(Point2::new(0.0, 0.0), Point2::new(1.0, 0.5)),
553 Line2D::through(Point2::new(0.0, 1.0), Point2::new(1.0, 0.0)),
554 Line2D::through(Point2::new(0.0, 0.5), Point2::new(1.0, 1.0)),
555 ];
556 let arr = LineArrangement::build(&lines);
557 assert_eq!(arr.euler_face_count(), 7);
558 }
559 #[test]
560 fn test_halfedge_vertex_faces() {
561 let mut mesh = HalfEdgeMesh::new();
562 let v0 = mesh.add_vertex([0.0, 0.0, 0.0]);
563 let v1 = mesh.add_vertex([1.0, 0.0, 0.0]);
564 let v2 = mesh.add_vertex([0.0, 1.0, 0.0]);
565 mesh.add_triangle(v0, v1, v2);
566 mesh.build_twin_links();
567 let faces = mesh.vertex_faces(v0);
568 assert!(!faces.is_empty());
569 }
570 #[test]
571 fn test_convex_hull_2d_circle_approx() {
572 let n = 8usize;
573 let pts: Vec<Point2> = (0..n)
574 .map(|i| {
575 let t = i as f64 * std::f64::consts::TAU / n as f64;
576 Point2::new(t.cos(), t.sin())
577 })
578 .collect();
579 let hull = convex_hull_2d(&pts);
580 assert_eq!(hull.len(), n);
581 }
582 #[test]
583 fn test_sutherland_hodgman_triangle_clip() {
584 let subject = vec![
585 Point2::new(-1.0, -1.0),
586 Point2::new(3.0, -1.0),
587 Point2::new(1.0, 3.0),
588 ];
589 let clip = vec![
590 Point2::new(0.0, 0.0),
591 Point2::new(1.0, 0.0),
592 Point2::new(1.0, 1.0),
593 Point2::new(0.0, 1.0),
594 ];
595 let result = sutherland_hodgman(&subject, &clip);
596 assert!(!result.is_empty());
597 let area = polygon_area(&result).abs();
598 assert!(area > 0.9 && area <= 1.0 + 1e-9, "area={area}");
599 }
600 #[test]
601 fn test_voronoi_circumcenters_equidistant() {
602 let pts = vec![
603 Point2::new(0.0, 0.0),
604 Point2::new(2.0, 0.0),
605 Point2::new(1.0, 2.0),
606 ];
607 let tris = delaunay_2d(&pts);
608 let cells = voronoi_from_delaunay(&pts, &tris);
609 for t in &tris {
610 if let Some((center, r2)) = circumcircle_2d(pts[t.a], pts[t.b], pts[t.c]) {
611 let ra = center.dist_sq(pts[t.a]);
612 let rb = center.dist_sq(pts[t.b]);
613 assert!((ra - r2).abs() < 1e-8);
614 assert!((rb - r2).abs() < 1e-8);
615 }
616 }
617 assert_eq!(cells.len(), 3);
618 }
619}