tg_geom/

line.rs

//! Line string type representing a sequence of connected line segments.
//!
//! A line string is an ordered sequence of points connected by straight
//! segments. Unlike a [`Ring`](crate::Ring), a line string is not required
//! to be closed (first point ≠ last point).

use core::marker::PhantomData;
use core::ptr::NonNull;

use crate::error::{Error, Result};
use crate::{IndexKind, Point, Rect, Segment};

macro_rules! impl_line_methods {
    ($get_ptr:expr) => {
        #[inline]
        pub fn rect(&self) -> Rect {
            let ptr = $get_ptr(self);
            let r = unsafe { tg_geom_sys::tg_line_rect(ptr) };
            r.into()
        }

        #[inline]
        pub fn num_points(&self) -> usize {
            let ptr = $get_ptr(self);
            unsafe { tg_geom_sys::tg_line_num_points(ptr) as usize }
        }

        #[inline]
        pub fn point_at(&self, index: usize) -> Option<Point> {
            if index >= self.num_points() {
                None
            } else {
                let ptr = $get_ptr(self);
                let p = unsafe { tg_geom_sys::tg_line_point_at(ptr, index as libc::c_int) };
                Some(p.into())
            }
        }

        #[inline]
        pub fn points(&self) -> &[Point] {
            let ptr = $get_ptr(self);
            let raw = unsafe { tg_geom_sys::tg_line_points(ptr) };
            if raw.is_null() {
                &[]
            } else {
                unsafe { core::slice::from_raw_parts(raw as *const Point, self.num_points()) }
            }
        }

        #[inline]
        pub fn num_segments(&self) -> usize {
            let ptr = $get_ptr(self);
            unsafe { tg_geom_sys::tg_line_num_segments(ptr) as usize }
        }

        #[inline]
        pub fn segment_at(&self, index: usize) -> Option<Segment> {
            if index >= self.num_segments() {
                None
            } else {
                let ptr = $get_ptr(self);
                let s = unsafe { tg_geom_sys::tg_line_segment_at(ptr, index as libc::c_int) };
                Some(s.into())
            }
        }

        #[inline]
        pub fn clockwise(&self) -> bool {
            let ptr = $get_ptr(self);
            unsafe { tg_geom_sys::tg_line_clockwise(ptr) }
        }

        #[inline]
        pub fn length(&self) -> f64 {
            let ptr = $get_ptr(self);
            unsafe { tg_geom_sys::tg_line_length(ptr) }
        }
    };
}

/// An owned line string.
pub struct Line {
    ptr: NonNull<tg_geom_sys::tg_line>,
}

impl Line {
    impl_line_methods!(|s: &Self| s.ptr.as_ptr());

    crate::utils::impl_nearest_segment!(tg_geom_sys::tg_line_nearest_segment);

    pub fn new(points: &[Point]) -> Result<Self> {
        Self::new_ix(points, IndexKind::Default)
    }

    pub fn new_ix(points: &[Point], ix: IndexKind) -> Result<Self> {
        let ptr = unsafe {
            tg_geom_sys::tg_line_new_ix(
                points.as_ptr() as *const tg_geom_sys::tg_point,
                points.len() as libc::c_int,
                ix.into(),
            )
        };
        NonNull::new(ptr)
            .map(|ptr| Self { ptr })
            .ok_or(Error::OutOfMemory)
    }

    /// # Safety
    /// The pointer must be valid and not owned elsewhere.
    pub unsafe fn from_raw(ptr: *mut tg_geom_sys::tg_line) -> Option<Self> {
        NonNull::new(ptr).map(|ptr| Self { ptr })
    }

    #[inline]
    pub fn as_ptr(&self) -> *const tg_geom_sys::tg_line {
        self.ptr.as_ptr()
    }

    pub fn into_raw(self) -> *mut tg_geom_sys::tg_line {
        let ptr = self.ptr.as_ptr();
        core::mem::forget(self);
        ptr
    }

    pub fn copy(&self) -> Result<Self> {
        let ptr = unsafe { tg_geom_sys::tg_line_copy(self.ptr.as_ptr()) };
        NonNull::new(ptr)
            .map(|ptr| Self { ptr })
            .ok_or(Error::CopyFailed)
    }

    pub fn clone_ref(&self) -> Result<Self> {
        let ptr = unsafe { tg_geom_sys::tg_line_clone(self.ptr.as_ptr()) };
        NonNull::new(ptr)
            .map(|ptr| Self { ptr })
            .ok_or(Error::CopyFailed)
    }

    pub fn memsize(&self) -> usize {
        unsafe { tg_geom_sys::tg_line_memsize(self.ptr.as_ptr()) }
    }

    pub fn index_spread(&self) -> i32 {
        unsafe { tg_geom_sys::tg_line_index_spread(self.ptr.as_ptr()) }
    }

    pub fn index_num_levels(&self) -> i32 {
        unsafe { tg_geom_sys::tg_line_index_num_levels(self.ptr.as_ptr()) }
    }

    pub fn index_level_num_rects(&self, level: i32) -> i32 {
        unsafe { tg_geom_sys::tg_line_index_level_num_rects(self.ptr.as_ptr(), level) }
    }

    pub fn index_level_rect(&self, level: i32, rect_idx: i32) -> Rect {
        let r =
            unsafe { tg_geom_sys::tg_line_index_level_rect(self.ptr.as_ptr(), level, rect_idx) };
        r.into()
    }

    pub fn iter_points(&self) -> impl Iterator<Item = Point> + '_ {
        self.points().iter().copied()
    }

    pub fn iter_segments(&self) -> impl Iterator<Item = Segment> + '_ {
        (0..self.num_segments()).map(move |i| self.segment_at(i).unwrap())
    }

    /// Return `false` to stop iteration.
    pub fn line_search<F>(&self, other: &Line, mut iter: F)
    where
        F: FnMut(Segment, usize, Segment, usize) -> bool,
    {
        unsafe extern "C" fn trampoline<F>(
            aseg: tg_geom_sys::tg_segment, aidx: libc::c_int, bseg: tg_geom_sys::tg_segment,
            bidx: libc::c_int, udata: *mut libc::c_void,
        ) -> bool
        where
            F: FnMut(Segment, usize, Segment, usize) -> bool,
        {
            let iter = unsafe { &mut *(udata as *mut F) };
            iter(aseg.into(), aidx as usize, bseg.into(), bidx as usize)
        }

        unsafe {
            tg_geom_sys::tg_line_line_search(
                self.ptr.as_ptr(),
                other.as_ptr(),
                Some(trampoline::<F>),
                core::ptr::from_mut(&mut iter).cast(),
            );
        }
    }
}

impl Drop for Line {
    fn drop(&mut self) {
        unsafe { tg_geom_sys::tg_line_free(self.ptr.as_ptr()) }
    }
}

impl core::fmt::Debug for Line {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("Line")
            .field("num_points", &self.num_points())
            .field("num_segments", &self.num_segments())
            .field("rect", &self.rect())
            .finish()
    }
}

unsafe impl Send for Line {}
unsafe impl Sync for Line {}

/// A borrowed reference to a line string.
#[derive(Clone, Copy)]
pub struct LineRef<'a> {
    ptr: *const tg_geom_sys::tg_line,
    _marker: PhantomData<&'a ()>,
}

unsafe impl Send for LineRef<'_> {}
unsafe impl Sync for LineRef<'_> {}

impl LineRef<'_> {
    impl_line_methods!(|s: &Self| s.ptr);

    /// # Safety
    /// The pointer must be valid for the lifetime `'a`.
    #[inline]
    pub unsafe fn from_raw(ptr: *const tg_geom_sys::tg_line) -> Option<Self> {
        if ptr.is_null() {
            None
        } else {
            Some(Self {
                ptr,
                _marker: PhantomData,
            })
        }
    }

    #[inline]
    pub fn as_ptr(&self) -> *const tg_geom_sys::tg_line {
        self.ptr
    }

    pub fn to_owned(&self) -> Result<Line> {
        let ptr = unsafe { tg_geom_sys::tg_line_copy(self.ptr) };
        NonNull::new(ptr)
            .map(|ptr| Line { ptr })
            .ok_or(Error::CopyFailed)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn p(x: f64, y: f64) -> Point {
        Point::new(x, y)
    }

    fn r(min_x: f64, min_y: f64, max_x: f64, max_y: f64) -> Rect {
        Rect::from_coords(min_x, min_y, max_x, max_y)
    }

    fn u1() -> Vec<Point> {
        vec![p(0.0, 10.0), p(0.0, 0.0), p(10.0, 0.0), p(10.0, 10.0)]
    }

    fn v1() -> Vec<Point> {
        vec![p(0.0, 10.0), p(5.0, 0.0), p(10.0, 10.0)]
    }

    #[test]
    fn test_line_new() {
        let line = Line::new(&u1()).unwrap();
        assert_eq!(line.num_points(), 4);
        assert_eq!(line.num_segments(), 3);
    }

    #[test]
    fn test_line_rect() {
        let line = Line::new(&u1()).unwrap();
        assert_eq!(line.rect(), r(0.0, 0.0, 10.0, 10.0));
    }

    #[test]
    fn test_line_clockwise() {
        let cw = Line::new(&[
            p(0.0, 0.0),
            p(0.0, 10.0),
            p(10.0, 10.0),
            p(10.0, 0.0),
            p(0.0, 0.0),
        ])
        .unwrap();
        assert!(cw.clockwise());

        let ccw = Line::new(&[
            p(0.0, 0.0),
            p(10.0, 0.0),
            p(10.0, 10.0),
            p(0.0, 10.0),
            p(0.0, 0.0),
        ])
        .unwrap();
        assert!(!ccw.clockwise());

        let partial_cw = Line::new(&[p(0.0, 0.0), p(0.0, 10.0), p(10.0, 10.0)]).unwrap();
        assert!(partial_cw.clockwise());

        let partial_ccw = Line::new(&[p(0.0, 0.0), p(10.0, 0.0), p(10.0, 10.0)]).unwrap();
        assert!(!partial_ccw.clockwise());
    }

    #[test]
    fn test_line_length() {
        let line = Line::new(&u1()).unwrap();
        assert!((line.length() - 30.0).abs() < 1e-10);
    }

    #[test]
    fn test_line_points() {
        let line = Line::new(&u1()).unwrap();
        let points = line.points();
        assert_eq!(points.len(), 4);

        for (i, &p2) in points.iter().enumerate() {
            let p1 = line.point_at(i).unwrap();
            assert_eq!(p1, p2);
        }
    }

    #[test]
    fn test_line_point_at_bounds() {
        let line = Line::new(&u1()).unwrap();
        assert!(line.point_at(0).is_some());
        assert!(line.point_at(3).is_some());
        assert!(line.point_at(4).is_none());
        assert!(line.point_at(100).is_none());
    }

    #[test]
    fn test_line_segment_at() {
        let line = Line::new(&u1()).unwrap();
        assert_eq!(line.num_segments(), 3);

        let seg0 = line.segment_at(0).unwrap();
        assert_eq!(seg0.a, p(0.0, 10.0));
        assert_eq!(seg0.b, p(0.0, 0.0));

        assert!(line.segment_at(3).is_none());
    }

    #[test]
    fn test_line_copy() {
        let line = Line::new(&u1()).unwrap();
        let copy = line.copy().unwrap();
        assert_eq!(line.num_points(), copy.num_points());
        assert_eq!(line.length(), copy.length());
    }

    #[test]
    fn test_line_clone_ref() {
        let line = Line::new(&u1()).unwrap();
        let cloned = line.clone_ref().unwrap();
        assert_eq!(line.num_points(), cloned.num_points());
    }

    #[test]
    fn test_line_memsize() {
        let line = Line::new(&u1()).unwrap();
        assert!(line.memsize() > 0);
    }

    #[test]
    fn test_line_iter_points() {
        let line = Line::new(&u1()).unwrap();
        let points: Vec<Point> = line.iter_points().collect();
        assert_eq!(points.len(), 4);
    }

    #[test]
    fn test_line_iter_segments() {
        let line = Line::new(&u1()).unwrap();
        let segments: Vec<Segment> = line.iter_segments().collect();
        assert_eq!(segments.len(), 3);
    }

    #[test]
    fn test_line_line_search() {
        let line1 = Line::new(&[p(0.0, 0.0), p(10.0, 10.0)]).unwrap();
        let line2 = Line::new(&[p(0.0, 10.0), p(10.0, 0.0)]).unwrap();

        let mut found = false;
        line1.line_search(&line2, |_seg1, _idx1, _seg2, _idx2| {
            found = true;
            false
        });
        assert!(found);
    }

    #[test]
    fn test_line_line_search_no_intersection() {
        let line1 = Line::new(&[p(0.0, 0.0), p(1.0, 1.0)]).unwrap();
        let line2 = Line::new(&[p(10.0, 10.0), p(11.0, 11.0)]).unwrap();

        let mut count = 0;
        line1.line_search(&line2, |_seg1, _idx1, _seg2, _idx2| {
            count += 1;
            true
        });
        assert_eq!(count, 0);
    }

    #[test]
    fn test_line_debug() {
        let line = Line::new(&u1()).unwrap();
        let debug_str = format!("{line:?}");
        assert!(debug_str.contains("Line"));
        assert!(debug_str.contains("num_points"));
    }

    #[test]
    fn test_line_send_sync() {
        fn assert_send<T: Send>() {}
        fn assert_sync<T: Sync>() {}
        assert_send::<Line>();
        assert_sync::<Line>();
    }

    #[test]
    fn test_line_index_kinds() {
        let points = u1();
        let line_default = Line::new(&points).unwrap();
        let line_none = Line::new_ix(&points, IndexKind::None).unwrap();
        let line_natural = Line::new_ix(&points, IndexKind::Natural).unwrap();

        assert_eq!(line_default.num_points(), line_none.num_points());
        assert_eq!(line_default.num_points(), line_natural.num_points());
    }

    #[test]
    fn test_line_raw_pointer() {
        let line = Line::new(&u1()).unwrap();
        let num_points = line.num_points();
        let ptr = line.into_raw();
        let recovered = unsafe { Line::from_raw(ptr).unwrap() };
        assert_eq!(recovered.num_points(), num_points);
    }

    #[test]
    fn test_line_v_shape() {
        let line = Line::new(&v1()).unwrap();
        assert_eq!(line.num_points(), 3);
        assert_eq!(line.num_segments(), 2);
        assert_eq!(line.point_at(0).unwrap(), p(0.0, 10.0));
        assert_eq!(line.point_at(1).unwrap(), p(5.0, 0.0));
        assert_eq!(line.point_at(2).unwrap(), p(10.0, 10.0));
    }

    fn point_distance_rect(point: Point, rect: Rect) -> f64 {
        let x = point.x.clamp(rect.min.x, rect.max.x);
        let y = point.y.clamp(rect.min.y, rect.max.y);
        let dx = point.x - x;
        let dy = point.y - y;
        (dx * dx + dy * dy).sqrt()
    }

    fn point_distance_segment(point: Point, seg: Segment) -> f64 {
        let dx = seg.b.x - seg.a.x;
        let dy = seg.b.y - seg.a.y;
        let len_sq = dx * dx + dy * dy;

        if len_sq == 0.0 {
            let dx = point.x - seg.a.x;
            let dy = point.y - seg.a.y;
            return (dx * dx + dy * dy).sqrt();
        }

        let t = ((point.x - seg.a.x) * dx + (point.y - seg.a.y) * dy) / len_sq;
        let t = t.clamp(0.0, 1.0);

        let closest_x = seg.a.x + t * dx;
        let closest_y = seg.a.y + t * dy;
        let dx = point.x - closest_x;
        let dy = point.y - closest_y;
        (dx * dx + dy * dy).sqrt()
    }

    #[test]
    fn test_line_nearest_segment_basic() {
        let line = Line::new_ix(&u1(), IndexKind::Natural).unwrap();
        let test_point = p(5.0, 5.0);
        let num_segments = line.num_segments();

        let mut visited = vec![false; num_segments];
        let mut last_dist = -1.0f64;
        let mut count = 0usize;

        let completed = line.nearest_segment(
            |rect| {
                let dist = point_distance_rect(test_point, rect);
                (dist, false)
            },
            |seg| {
                let dist = point_distance_segment(test_point, seg);
                (dist, false)
            },
            |seg, dist, idx| {
                assert!(idx < num_segments);
                assert!(count == 0 || dist >= last_dist - 1e-10);
                assert!(!visited[idx]);
                visited[idx] = true;

                let original_seg = line.segment_at(idx).unwrap();
                assert_eq!(seg.a, original_seg.a);
                assert_eq!(seg.b, original_seg.b);

                last_dist = dist;
                count += 1;
                true
            },
        );

        assert!(completed);
        assert_eq!(count, num_segments);

        let visited_count = visited.iter().filter(|&&v| v).count();
        assert_eq!(visited_count, count);
    }

    #[test]
    fn test_line_nearest_segment_early_stop() {
        let line = Line::new_ix(&u1(), IndexKind::Natural).unwrap();
        let test_point = p(5.0, 5.0);
        let stop_at = 2;
        let mut count = 0;

        let success = line.nearest_segment(
            |rect| (point_distance_rect(test_point, rect), false),
            |seg| (point_distance_segment(test_point, seg), false),
            |_seg, _dist, _idx| {
                count += 1;
                count < stop_at
            },
        );

        assert!(success);
        assert_eq!(count, stop_at);
        assert!(count < line.num_segments());
    }

    #[test]
    fn test_line_nearest_segment_no_index() {
        let line = Line::new_ix(&u1(), IndexKind::None).unwrap();
        let test_point = p(5.0, 5.0);
        let mut count = 0;

        let completed = line.nearest_segment(
            |rect| (point_distance_rect(test_point, rect), false),
            |seg| (point_distance_segment(test_point, seg), false),
            |_seg, _dist, _idx| {
                count += 1;
                true
            },
        );

        assert!(completed);
        assert_eq!(count, line.num_segments());
    }

    #[test]
    fn test_line_nearest_segment_closest_first() {
        let line = Line::new(&u1()).unwrap();
        let test_point = p(5.0, 0.1);

        let mut first_dist: Option<f64> = None;

        line.nearest_segment(
            |rect| (point_distance_rect(test_point, rect), false),
            |seg| (point_distance_segment(test_point, seg), false),
            |_seg, dist, _idx| {
                if first_dist.is_none() {
                    first_dist = Some(dist);
                }
                false
            },
        );

        let dist = first_dist.expect("Should find at least one segment");
        assert!(dist < 0.2);
    }
}