engeom 0.5.0

Library for working with geometry with a focus on engineering metrology applications.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
//! This module contains support functionality for curve-to-curve alignment, including the core
//! building blocks consumed by the other curve alignment routines in the `align2` module tree. All
//! public items are re-exported directly from `align2`, so callers interact with them through that
//! parent module. If you are implementing your own alignment routines, you may find that you want
//! to use some functionality contained here.
//!
//! This is the 2D counterpart of `geom3::align3::mesh`, and is deliberately structured similarly
//! to it. The differences that are not simply a matter of dimension are called out below.
//!
//! # What this module provides
//!
//! ## Sample point container
//!
//! [`CurveSurfPoint`] is an owned sample taken from a `Curve2`, the counterpart of `MeshSurfPoint`
//! in 3D. It exists because `CurveStation2` borrows its parent curve and so cannot be stored
//! across the transforms a multi-body solve applies.
//!
//! # What was deliberately left out
//!
//! There is no per-vertex uncertainty and no residual weighting machinery here, even though the
//! 3D mirror (`geom3::align3::mesh`) has both. In 3D they have a producer: `Mesh3::point_stdev`
//! carries real measurement uncertainty from scan data. In 2D nothing produces such data today -
//! a `Curve2` has no stdev attribute, and a mesh section does not interpolate its parent's - so
//! the plumbing was removed rather than carried speculatively. If a producer appears, mirror the
//! machinery back from the 3D side.

use crate::common::points::dist;
use crate::common::vec_f64::mean_and_stdev;
use crate::geom2::align2::target::is_curve_endpoint;
use crate::geom2::curve2::CurveStation2;
use crate::geom2::{Curve2, CurveGroup2, Iso2, SurfacePoint2};
use std::f64::consts::PI;

// ===============================================================================================
// Sample point container
// ===============================================================================================

/// An owned sample point taken from a curve within a [`crate::geom2::CurveGroup2`], holding
/// which member it sits on, where on that member it sits, and the surface point itself.
///
/// This is the 2D counterpart of `MeshSurfPoint`. Where that struct locates a sample by face index
/// and barycentric coordinates, this one locates it by edge index and the fraction along that
/// edge, which is the same idea in one dimension fewer. What has no 3D counterpart is `member`: a
/// multi-component mesh is still one `Mesh3` with one face index space, while a group of curves
/// keeps its members separate, so the member index is part of the sample's address.
///
/// `index`, `fraction`, and `length_along` are all local to the member curve, not to the group.
///
/// `length_along` is redundant with `index` and `fraction` but is kept because arc length is the
/// natural coordinate for a curve, and recovering it later would require the parent curve, which
/// consumers of an owned sample do not have. Every field is filled in by
/// [`CurveSurfPoint::from_station`], so they stay consistent by construction.
#[derive(Debug, Clone, Copy)]
pub struct CurveSurfPoint {
    /// The index of the member curve this point belongs to, within its owning group. A sample
    /// taken from a lone curve uses `0`, matching the group of one that `CurveGroup2::from`
    /// builds.
    pub member: usize,

    /// The index of the vertex in the member's underlying polyline which directly precedes this
    /// point.
    pub index: usize,

    /// The fraction of the distance between the vertex at `index` and the next one at which this
    /// point is located, in the range `[0, 1]`.
    pub fraction: f64,

    /// The distance along the member curve from its start to this point.
    pub length_along: f64,

    /// The surface point (position and normal) corresponding to this location on the curve.
    pub sp: SurfacePoint2,
}

impl CurveSurfPoint {
    /// Captures a station on a curve as an owned sample point, recording which member of its
    /// group the curve is.
    pub fn from_station(station: &CurveStation2, member: usize) -> Self {
        Self {
            member,
            index: station.index(),
            fraction: station.fraction(),
            length_along: station.length_along(),
            sp: station.surface_point(),
        }
    }
}

// ===============================================================================================
// Alignment point sampling
// ===============================================================================================

/// Curve-alignment-point parameters, controlling [`generate_alignment_points`].
///
/// This is the 2D counterpart of `GAPParams` ("generate-alignment-points parameters") in
/// `align3`, named differently only so that the two can be glob-imported together. The two flatness criteria that 3D applies to a sampled
/// neighborhood (`out_of_plane_ratio` and `centroid_ratio`) have no 2D counterpart: a curve is
/// already an ordered one-dimensional path, so there is no neighborhood to fit a basis to and no
/// mesh edge to fall off. What replaces them is [`CAPParams::max_corner_angle`], which rejects
/// samples sitting on a sharp turn, and [`CAPParams::end_margin`], which keeps samples away from
/// the ends of an open curve.
#[derive(Debug, Clone, Copy)]
pub struct CAPParams {
    /// The arc length spacing between samples taken along the test curve. It also sets the
    /// distance at which the turn of the curve is examined on either side of a sample.
    pub sample_spacing: f64,

    /// The maximum permissible angle, in radians, between the normal at a sample and the normals
    /// one sample spacing to either side of it, on both the test and the reference curve.
    ///
    /// This is what rejects samples on or beside a corner, where the closest point on the other
    /// curve jumps rather than slides as the bodies move. A value of `PI / 3.0` (60 degrees) is a
    /// reasonable starting point; leave it large for a noisy curve.
    pub max_corner_angle: f64,

    /// The distance from either end of an open curve within which samples are discarded, in the
    /// units of the geometry.
    ///
    /// A projection past the end of an open curve clamps to the endpoint, which produces a
    /// confident-looking correspondence to a place the curve does not actually go. Both the test
    /// and the reference side are kept clear of this. A closed curve has no ends and ignores it.
    pub end_margin: f64,

    /// An optional value that, if provided, will result in a filtering operation of the final
    /// selected candidates based on the distance between them and the reference curve. A value of
    /// `Some(3.0)` will filter out candidates that are more than 3 standard deviations above the
    /// mean candidate distance to the reference curve. This can be used to remove outlying areas
    /// of the test curve as the two curves begin to converge towards alignment.
    pub filter_distances: Option<f64>,
}

impl CAPParams {
    /// Creates a new set of parameters for the curve sampling algorithm.
    ///
    /// # Arguments
    ///
    /// * `sample_spacing`: The arc length spacing between samples on the test curve. Smaller
    ///   values mean a denser sampling, but also more points to check and more influence from
    ///   smaller features in the curve.
    /// * `max_corner_angle`: The maximum permissible angle between the normal at a sample and the
    ///   normals one sample spacing to either side of it.
    /// * `end_margin`: The distance from either end of an open curve within which samples are
    ///   discarded.
    /// * `filter_distances`: An optional number of standard deviations above the mean
    ///   candidate-to-reference distance beyond which candidates are discarded.
    ///
    /// returns: CAPParams
    pub fn new(
        sample_spacing: f64,
        max_corner_angle: f64,
        end_margin: f64,
        filter_distances: Option<f64>,
    ) -> Self {
        Self {
            sample_spacing,
            max_corner_angle,
            end_margin,
            filter_distances,
        }
    }

    /// Creates a new set of default parameters for the curve sampling algorithm, requiring only
    /// the sample spacing to be specified.
    ///
    /// # Arguments
    ///
    /// * `sample_spacing`: The arc length spacing between samples on the test curve.
    ///
    /// returns: CAPParams
    pub fn defaults(sample_spacing: f64) -> Self {
        Self {
            sample_spacing,
            max_corner_angle: PI / 3.0,
            end_margin: 2.0 * sample_spacing,
            filter_distances: Some(3.0),
        }
    }
}

/// A sampling algorithm that finds a set of good alignment points on a test body which can be
/// used to align it with a reference body. Pay close attention to the parameters.
///
/// The method walks every member of the test group at a uniform arc length spacing and keeps the
/// samples which look like they will behave during a solve. Each check runs against the member
/// curve that owns the position being checked, so a group mixing closed loops and open segments
/// is treated at every position like the single curve that position belongs to. A sample is
/// retained when:
///
/// 1. It is at least `end_margin` from either end of its own member, if that member is open.
/// 2. The normals one sample spacing to either side of it, along its own member, are within
///    `max_corner_angle` of its own.
/// 3. After being moved by `iso`, its closest point on any member of the reference group is not
///    a clamped endpoint of an open member.
/// 4. The normal at that closest point faces the same way as the moved sample's normal.
/// 5. The owning reference member satisfies the same corner and end-margin checks at the closest
///    point.
///
/// At the very end, if a sigma value is provided in `filter_distances`, the mean and standard
/// deviation of the distance from each candidate to its corresponding projected point are
/// computed, and any candidates further than `sigma` standard deviations above the mean are
/// discarded. The filter is pooled across the whole body rather than run per member, because it
/// measures body-to-body convergence.
///
/// # Arguments
///
/// * `test`: The body which will be sampled for alignment points: the resulting points will be
///   on this group's members, in the group's own coordinates.
/// * `reference`: The body which is used as a reference for the alignment. The resulting points
///   will be good points to use when aligning the test body to this reference body.
/// * `iso`: An initial transform that will be applied to the test body's points before
///   projecting them onto the reference. This would represent an initial guess of the alignment
///   that is to follow, and takes the test body's coordinates into the reference's.
/// * `params`: The parameters for the sampling algorithm.
///
/// returns: Vec<CurveSurfPoint, Global>
pub fn generate_alignment_points(
    test: &CurveGroup2,
    reference: &CurveGroup2,
    iso: &Iso2,
    params: &CAPParams,
) -> Vec<CurveSurfPoint> {
    let mut candidates = Vec::new();

    for (member, test_curve) in test.curves().iter().enumerate() {
        for cp in sample_curve(test_curve, params.sample_spacing, member) {
            if !clear_of_the_ends(test_curve, cp.length_along, params.end_margin) {
                continue;
            }
            if !turns_gently(test_curve, &cp, params) {
                continue;
            }

            // Move the sample into the reference body's frame and find where it lands, on
            // whichever member is nearest.
            let moved = cp.sp.transformed_by(iso);
            let (ref_m, station) = reference.at_closest_to_point(&moved.point);
            let ref_curve = &reference.curves()[ref_m];

            // A projection past the end of an open member clamps to the endpoint, which is not a
            // real correspondence.
            if !ref_curve.is_closed() && is_curve_endpoint(&station, ref_curve) {
                continue;
            }

            let ref_cp = CurveSurfPoint::from_station(&station, ref_m);
            if ref_cp.sp.normal.dot(&moved.normal) < 0.0 {
                continue;
            }
            if !clear_of_the_ends(ref_curve, ref_cp.length_along, params.end_margin) {
                continue;
            }
            if !turns_gently(ref_curve, &ref_cp, params) {
                continue;
            }

            candidates.push((dist(&moved.point, &ref_cp.sp.point), cp));
        }
    }

    // Lastly, filter out candidates with distances more than a specified number of standard
    // deviations above the mean distance.
    //
    // A zero spread is left alone rather than filtered. With no variation there is no outlier to
    // find, and the threshold would land exactly on the mean and so discard every candidate. Two
    // coincident curves are the case that reaches this, which is rare in measured data but is
    // precisely what a synthetic test looks like.
    if let Some(sigma) = params.filter_distances
        && candidates.len() > 10
    {
        let distances = candidates.iter().map(|(d, _)| *d).collect::<Vec<_>>();
        if let Some((mean, st_dev)) = mean_and_stdev(&distances)
            && st_dev > 0.0
        {
            let threshold = mean + sigma * st_dev;
            candidates.retain(|(d, _)| *d < threshold);
        }
    }

    candidates.into_iter().map(|(_, cp)| cp).collect()
}

/// Walks a member curve at a uniform arc length spacing, offset by half a spacing so that
/// samples do not land on the vertices of a regularly shaped polyline, where the normal is
/// ambiguous. The samples are stamped with the member index they belong to.
fn sample_curve(curve: &Curve2, spacing: f64, member: usize) -> Vec<CurveSurfPoint> {
    if !spacing.is_finite() || spacing <= 0.0 || curve.length() <= 0.0 {
        return Vec::new();
    }

    let count = (curve.length() / spacing).floor() as usize;
    (0..count)
        .filter_map(|k| {
            let l = (k as f64 + 0.5) * spacing;
            curve
                .at_length(l)
                .map(|s| CurveSurfPoint::from_station(&s, member))
        })
        .collect()
}

/// Whether a position along a curve is far enough from either end. A closed curve has no ends.
fn clear_of_the_ends(curve: &Curve2, length_along: f64, margin: f64) -> bool {
    curve.is_closed() || (length_along >= margin && length_along <= curve.length() - margin)
}

/// Whether the curve turns by no more than `max_corner_angle` within one sample spacing on either
/// side of a point. This is what keeps samples off corners, where the closest point on the other
/// curve jumps rather than slides as the bodies move.
fn turns_gently(curve: &Curve2, cp: &CurveSurfPoint, params: &CAPParams) -> bool {
    for delta in [-params.sample_spacing, params.sample_spacing] {
        let raw = cp.length_along + delta;
        let l = if curve.is_closed() {
            raw.rem_euclid(curve.length())
        } else {
            raw
        };

        // Off the end of an open curve, which `clear_of_the_ends` is responsible for.
        let Some(station) = curve.at_length(l) else {
            continue;
        };

        if station.normal().angle(&cp.sp.normal) > params.max_corner_angle {
            return false;
        }
    }
    true
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::geom2::{Point2, Vector2};
    use approx::assert_relative_eq;
    use std::f64::consts::PI;

    /// A counter-clockwise square with 2-unit sides, so the cumulative vertex lengths are
    /// 0, 2, 4, 6 and (when closed) 8.
    fn square(closed: bool) -> Curve2 {
        let points =
            [(0.0, 0.0), (2.0, 0.0), (2.0, 2.0), (0.0, 2.0)].map(|(x, y)| Point2::new(x, y));
        Curve2::from_points(&points, 1e-8, closed).unwrap()
    }

    fn sample_at(curve: &Curve2, length: f64) -> CurveSurfPoint {
        CurveSurfPoint::from_station(&curve.at_length(length).unwrap(), 0)
    }

    /// Wraps a fixture curve as a body of one for the container tests.
    fn group_of(curve: &Curve2) -> CurveGroup2 {
        CurveGroup2::from(curve.clone())
    }

    #[test]
    fn a_sample_records_where_it_came_from() {
        let curve = square(false);
        // One quarter of the way along the second edge, which runs from (2,0) to (2,2).
        let cp = sample_at(&curve, 2.5);

        assert_eq!(cp.member, 0);
        assert_eq!(cp.index, 1);
        assert_relative_eq!(cp.fraction, 0.25, epsilon = 1e-12);
        assert_relative_eq!(cp.length_along, 2.5, epsilon = 1e-12);
        assert_relative_eq!(cp.sp.point, Point2::new(2.0, 0.5), epsilon = 1e-12);
    }

    #[test]
    fn a_sample_carries_the_outward_normal() {
        // The curve is wound counter-clockwise, so the normal on the bottom edge points down.
        let curve = square(true);
        let cp = sample_at(&curve, 1.0);

        assert_relative_eq!(
            cp.sp.normal.into_inner(),
            Vector2::new(0.0, -1.0),
            epsilon = 1e-12
        );
    }

    // ============================================================================================
    // Alignment point sampling
    // ============================================================================================

    /// A closed counter-clockwise rectangle 10 by 6, centered on the origin. Its corners sit at
    /// arc lengths 0, 10, 16 and 26 out of a perimeter of 32.
    fn rect_curve() -> Curve2 {
        let points =
            [(-5.0, -3.0), (5.0, -3.0), (5.0, 3.0), (-5.0, 3.0)].map(|(x, y)| Point2::new(x, y));
        Curve2::from_points(&points, 1e-8, true).unwrap()
    }

    /// A straight open line along x, so it has ends but no corners at all.
    fn open_line() -> Curve2 {
        Curve2::from_points(
            &[Point2::new(0.0, 0.0), Point2::new(10.0, 0.0)],
            1e-8,
            false,
        )
        .unwrap()
    }

    #[test]
    fn samples_are_spaced_along_the_curve_and_miss_the_vertices() {
        let curve = rect_curve();
        let samples = sample_curve(&curve, 0.5, 0);

        // A perimeter of 32 at a spacing of 0.5 gives 64 samples, offset by half a spacing so
        // that none of them land on a corner.
        assert_eq!(samples.len(), 64);
        assert_relative_eq!(samples[0].length_along, 0.25, epsilon = 1e-12);
        assert_relative_eq!(samples[1].length_along, 0.75, epsilon = 1e-12);
        for s in &samples {
            for corner in [0.0, 10.0, 16.0, 26.0, 32.0] {
                assert!((s.length_along - corner).abs() > 1e-9);
            }
        }
    }

    #[test]
    fn a_degenerate_spacing_samples_nothing() {
        let curve = rect_curve();
        assert!(sample_curve(&curve, 0.0, 0).is_empty());
        assert!(sample_curve(&curve, -1.0, 0).is_empty());
        assert!(sample_curve(&curve, f64::NAN, 0).is_empty());
    }

    #[test]
    fn the_corner_check_rejects_samples_beside_a_corner() {
        let curve = rect_curve();
        let params = CAPParams::defaults(0.5);

        // Well inside the bottom edge, with both neighbors on the same edge.
        assert!(turns_gently(&curve, &sample_at(&curve, 5.0), &params));

        // A quarter spacing short of the corner at 10.0, so the neighbor one spacing ahead has
        // already turned the 90 degree corner.
        assert!(!turns_gently(&curve, &sample_at(&curve, 9.75), &params));
        assert!(!turns_gently(&curve, &sample_at(&curve, 10.25), &params));

        // A closed curve wraps, so the seam at 0.0 is treated like any other corner.
        assert!(!turns_gently(&curve, &sample_at(&curve, 0.25), &params));
        assert!(!turns_gently(&curve, &sample_at(&curve, 31.75), &params));
    }

    #[test]
    fn the_end_margin_only_applies_to_open_curves() {
        let closed = rect_curve();
        let open = open_line();

        // A closed curve has no ends, so nothing is ever near one.
        assert!(clear_of_the_ends(&closed, 0.0, 2.0));
        assert!(clear_of_the_ends(&closed, closed.length(), 2.0));

        assert!(!clear_of_the_ends(&open, 0.5, 2.0));
        assert!(!clear_of_the_ends(&open, 9.5, 2.0));
        assert!(clear_of_the_ends(&open, 5.0, 2.0));
        // The margin itself is inclusive at both ends.
        assert!(clear_of_the_ends(&open, 2.0, 2.0));
        assert!(clear_of_the_ends(&open, 8.0, 2.0));
    }

    #[test]
    fn generated_points_avoid_the_corners_of_a_closed_curve() {
        let test = rect_curve();
        let reference = rect_curve();
        let params = CAPParams::defaults(0.5);

        let points = generate_alignment_points(
            &group_of(&test),
            &group_of(&reference),
            &Iso2::identity(),
            &params,
        );

        // Two of the 64 samples beside each of the four corners are rejected on the test curve,
        // and the reference curve rejects the same ones, leaving 56.
        assert_eq!(points.len(), 56);
        for p in &points {
            for corner in [0.0, 10.0, 16.0, 26.0, 32.0] {
                assert!(
                    (p.length_along - corner).abs() > 0.5,
                    "a sample at {} is too close to the corner at {corner}",
                    p.length_along
                );
            }
        }
    }

    #[test]
    fn coincident_curves_still_produce_correspondences() {
        // Every candidate distance is zero here, so the mean is zero and the spread is zero. If
        // the distance filter were applied anyway its threshold would land on the mean and throw
        // away every candidate, leaving the solve with nothing to work with.
        let test = rect_curve();
        let reference = rect_curve();
        let params = CAPParams::defaults(0.5);
        assert!(params.filter_distances.is_some());

        let points = generate_alignment_points(
            &group_of(&test),
            &group_of(&reference),
            &Iso2::identity(),
            &params,
        );
        assert!(!points.is_empty());
    }

    #[test]
    fn the_distance_filter_drops_the_furthest_candidates() {
        // Two straight lines fanning apart, so the distance from the test curve to the reference
        // grows steadily along its length and the far end is what the filter should remove.
        // Straight lines keep the corner check out of the way entirely.
        let test = open_line();
        let reference = Curve2::from_points(
            &[Point2::new(0.0, 0.0), Point2::new(10.0, 2.0)],
            1e-8,
            false,
        )
        .unwrap();

        let unfiltered = CAPParams::new(0.25, PI / 3.0, 0.5, None);
        let filtered = CAPParams::new(0.25, PI / 3.0, 0.5, Some(1.0));

        let test = group_of(&test);
        let reference = group_of(&reference);
        let a = generate_alignment_points(&test, &reference, &Iso2::identity(), &unfiltered);
        let b = generate_alignment_points(&test, &reference, &Iso2::identity(), &filtered);

        assert!(
            b.len() < a.len(),
            "the filter should have dropped the far samples: {} unfiltered, {} filtered",
            a.len(),
            b.len()
        );

        // What survives is the near end of the curve, not an arbitrary subset of it.
        let worst_kept = b.iter().map(|p| p.length_along).fold(f64::MIN, f64::max);
        let worst_dropped = a.iter().map(|p| p.length_along).fold(f64::MIN, f64::max);
        assert!(worst_kept < worst_dropped);
    }

    #[test]
    fn samples_whose_normals_disagree_are_rejected() {
        // The same line twice, but the reference is wound the other way so its normal points the
        // opposite direction everywhere. Nothing should survive.
        let test = open_line();
        let reference = Curve2::from_points(
            &[Point2::new(10.0, 0.0), Point2::new(0.0, 0.0)],
            1e-8,
            false,
        )
        .unwrap();

        let params = CAPParams::new(0.5, PI / 3.0, 1.0, None);
        let points = generate_alignment_points(
            &group_of(&test),
            &group_of(&reference),
            &Iso2::identity(),
            &params,
        );

        assert!(points.is_empty());
    }

    #[test]
    fn samples_projecting_past_an_open_end_are_rejected() {
        // The reference covers only the first half of the test curve, so samples on the second
        // half clamp to its endpoint and must be discarded rather than matched there.
        let test = open_line();
        let reference =
            Curve2::from_points(&[Point2::new(0.0, 0.0), Point2::new(5.0, 0.0)], 1e-8, false)
                .unwrap();

        let params = CAPParams::new(0.5, PI / 3.0, 0.5, None);
        let points = generate_alignment_points(
            &group_of(&test),
            &group_of(&reference),
            &Iso2::identity(),
            &params,
        );

        assert!(!points.is_empty());
        for p in &points {
            assert!(
                p.length_along < 5.0,
                "a sample at {} matched past the end of the reference",
                p.length_along
            );
        }
    }

    #[test]
    fn samples_carry_their_member_and_respect_each_members_ends() {
        // A test body of two parallel open lines just off a common reference line. Samples must
        // come from both members, stamped with the right index, and each member's end margin is
        // measured along that member.
        let above = Curve2::from_points(
            &[Point2::new(0.0, 0.1), Point2::new(10.0, 0.1)],
            1e-8,
            false,
        )
        .unwrap();
        let below = Curve2::from_points(
            &[Point2::new(0.0, -0.1), Point2::new(10.0, -0.1)],
            1e-8,
            false,
        )
        .unwrap();
        let test = CurveGroup2::new(vec![above, below]).unwrap();
        let reference = group_of(&open_line());

        let params = CAPParams::new(0.5, PI / 3.0, 0.5, None);
        let points = generate_alignment_points(&test, &reference, &Iso2::identity(), &params);

        // Each 10-unit member yields 20 half-offset samples, of which the end margin removes the
        // first and last, leaving 18 per member.
        let from_0 = points.iter().filter(|p| p.member == 0).count();
        let from_1 = points.iter().filter(|p| p.member == 1).count();
        assert_eq!(from_0, 18);
        assert_eq!(from_1, 18);
        for p in &points {
            assert!(p.length_along >= 0.5 && p.length_along <= 9.5);
        }
    }

    #[test]
    fn reference_checks_run_against_the_owning_member() {
        // The reference body mixes a short open segment far away (member 0) with a closed
        // rectangle (member 1), and the test body coincides with the rectangle. Every match
        // lands on member 1, and the checks must be judged against it: if the endpoint clamp or
        // end margin were wrongly evaluated against the short open member 0, nearly every sample
        // would be rejected, because their arc lengths run far past its end.
        let far_segment = Curve2::from_points(
            &[Point2::new(0.0, 50.0), Point2::new(1.0, 50.0)],
            1e-8,
            false,
        )
        .unwrap();
        let reference = CurveGroup2::new(vec![far_segment, rect_curve()]).unwrap();
        let test = group_of(&rect_curve());

        let params = CAPParams::defaults(0.5);
        let points = generate_alignment_points(&test, &reference, &Iso2::identity(), &params);

        // The same count the single-curve corner test establishes: 64 samples minus two beside
        // each of the four corners.
        assert_eq!(points.len(), 56);
    }
}