tg_geom/

ring.rs

//! Closed ring type for polygon boundaries and holes.

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

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

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

        #[inline]
        pub fn num_points(&self) -> usize {
            let ptr = $get_ptr(self);
            unsafe { tg_geom_sys::tg_ring_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_ring_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_ring_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_ring_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_ring_segment_at(ptr, index as libc::c_int) };
                Some(s.into())
            }
        }

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

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

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

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

/// An owned closed ring.
pub struct Ring {
    ptr: NonNull<tg_geom_sys::tg_ring>,
}

impl Ring {
    impl_ring_methods!(|s: &Self| s.ptr.as_ptr());

    crate::utils::impl_nearest_segment!(tg_geom_sys::tg_ring_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_ring_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_ring) -> Option<Self> {
        NonNull::new(ptr).map(|ptr| Self { ptr })
    }

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

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

    pub fn copy(&self) -> Result<Self> {
        let ptr = unsafe { tg_geom_sys::tg_ring_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_ring_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_ring_memsize(self.ptr.as_ptr()) }
    }

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

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

    pub fn index_level_num_rects(&self, level: i32) -> i32 {
        unsafe { tg_geom_sys::tg_ring_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_ring_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, line: &crate::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_ring_line_search(
                self.ptr.as_ptr(),
                line.as_ptr(),
                Some(trampoline::<F>),
                core::ptr::from_mut(&mut iter).cast(),
            );
        }
    }

    /// Return `false` to stop iteration.
    pub fn ring_search<F>(&self, other: &Ring, 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_ring_ring_search(
                self.ptr.as_ptr(),
                other.ptr.as_ptr(),
                Some(trampoline::<F>),
                core::ptr::from_mut(&mut iter).cast(),
            );
        }
    }
}

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

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

unsafe impl Send for Ring {}
unsafe impl Sync for Ring {}

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

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

impl RingRef<'_> {
    impl_ring_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_ring) -> Option<Self> {
        if ptr.is_null() {
            None
        } else {
            Some(Self {
                ptr,
                _marker: PhantomData,
            })
        }
    }

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

    pub fn to_owned(&self) -> Result<Ring> {
        let ptr = unsafe { tg_geom_sys::tg_ring_copy(self.ptr) };
        NonNull::new(ptr)
            .map(|ptr| Ring { 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 rectangle() -> Vec<Point> {
        vec![
            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),
        ]
    }

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

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

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

    #[test]
    fn test_ring_new() {
        let ring = Ring::new(&rectangle()).unwrap();
        assert_eq!(ring.num_points(), 5);
        assert_eq!(ring.num_segments(), 4);
    }

    #[test]
    fn test_ring_not_closed() {
        let points = vec![p(1.0, 1.0), p(2.0, 1.0), p(2.0, 2.0), p(1.0, 2.0)];
        let ring = Ring::new(&points).unwrap();
        assert!(ring.num_points() >= 4);
    }

    #[test]
    fn test_ring_rect() {
        let ring = Ring::new(&octagon()).unwrap();
        assert_eq!(ring.rect(), r(0.0, 0.0, 10.0, 10.0));
    }

    #[test]
    fn test_ring_clockwise() {
        let ccw = Ring::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 cw = Ring::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());
    }

    #[test]
    fn test_ring_convex() {
        let octagon_ring = Ring::new(&octagon()).unwrap();
        assert!(octagon_ring.convex());

        let concave_ring = Ring::new(&concave1()).unwrap();
        assert!(!concave_ring.convex());

        let triangle_ring = Ring::new(&triangle()).unwrap();
        assert!(triangle_ring.convex());
    }

    #[test]
    fn test_ring_area_perimeter() {
        let u1_ring = Ring::new(&[p(0.0, 10.0), p(0.0, 0.0), p(10.0, 0.0), p(10.0, 10.0)]).unwrap();
        assert_eq!(u1_ring.perimeter(), 40.0);
        assert_eq!(u1_ring.area(), 100.0);

        let rect_ring = Ring::new(&rectangle()).unwrap();
        assert_eq!(rect_ring.perimeter(), 40.0);
        assert_eq!(rect_ring.area(), 100.0);
    }

    #[test]
    fn test_ring_points() {
        let ring = Ring::new(&octagon()).unwrap();
        let points = ring.points();
        assert_eq!(points.len(), ring.num_points());

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

    #[test]
    fn test_ring_point_at_bounds() {
        let ring = Ring::new(&rectangle()).unwrap();
        assert!(ring.point_at(0).is_some());
        assert!(ring.point_at(4).is_some());
        assert!(ring.point_at(5).is_none());
        assert!(ring.point_at(100).is_none());
    }

    #[test]
    fn test_ring_segment_at() {
        let ring = Ring::new(&rectangle()).unwrap();
        assert_eq!(ring.num_segments(), 4);

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

        assert!(ring.segment_at(4).is_none());
    }

    #[test]
    fn test_ring_index_properties() {
        let ring = Ring::new_ix(&octagon(), IndexKind::Natural).unwrap();
        assert!(ring.memsize() > 0);
        assert!(ring.index_num_levels() >= 0);
    }

    #[test]
    fn test_ring_copy() {
        let ring = Ring::new(&octagon()).unwrap();
        let copy = ring.copy().unwrap();
        assert_eq!(ring.num_points(), copy.num_points());
        assert_eq!(ring.area(), copy.area());
    }

    #[test]
    fn test_ring_clone_ref() {
        let ring = Ring::new(&octagon()).unwrap();
        let cloned = ring.clone_ref().unwrap();
        assert_eq!(ring.num_points(), cloned.num_points());
    }

    #[test]
    fn test_ring_iter_points() {
        let ring = Ring::new(&rectangle()).unwrap();
        let points: Vec<Point> = ring.iter_points().collect();
        assert_eq!(points.len(), 5);
    }

    #[test]
    fn test_ring_iter_segments() {
        let ring = Ring::new(&rectangle()).unwrap();
        let segments: Vec<Segment> = ring.iter_segments().collect();
        assert_eq!(segments.len(), 4);
    }

    #[test]
    fn test_ring_ring_search() {
        let ring1 = Ring::new(&[
            p(0.0, 0.0),
            p(5.0, 0.0),
            p(5.0, 5.0),
            p(0.0, 5.0),
            p(0.0, 0.0),
        ])
        .unwrap();
        let ring2 = Ring::new(&[
            p(2.5, 2.5),
            p(7.5, 2.5),
            p(7.5, 7.5),
            p(2.5, 7.5),
            p(2.5, 2.5),
        ])
        .unwrap();

        let mut count = 0;
        ring1.ring_search(&ring2, |_seg1, _idx1, _seg2, _idx2| {
            count += 1;
            true
        });
        assert!(count > 0);
    }

    #[test]
    fn test_ring_debug() {
        let ring = Ring::new(&rectangle()).unwrap();
        let debug_str = format!("{ring:?}");
        assert!(debug_str.contains("Ring"));
        assert!(debug_str.contains("num_points"));
    }

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

    #[test]
    fn test_ring_index_kinds() {
        let points = octagon();

        let ring_default = Ring::new(&points).unwrap();
        let ring_none = Ring::new_ix(&points, IndexKind::None).unwrap();
        let ring_natural = Ring::new_ix(&points, IndexKind::Natural).unwrap();

        assert_eq!(ring_default.num_points(), ring_none.num_points());
        assert_eq!(ring_default.num_points(), ring_natural.num_points());
        assert_eq!(ring_default.area(), ring_none.area());
        assert_eq!(ring_default.area(), ring_natural.area());
    }

    #[test]
    fn test_ring_raw_pointer() {
        let ring = Ring::new(&rectangle()).unwrap();
        let num_points = ring.num_points();
        let ptr = ring.into_raw();
        let recovered = unsafe { Ring::from_raw(ptr).unwrap() };
        assert_eq!(recovered.num_points(), num_points);
    }

    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_ring_nearest_segment_basic() {
        let ring = Ring::new_ix(&octagon(), IndexKind::Natural).unwrap();
        let test_point = p(5.0, 5.0);
        let num_segments = ring.num_segments();

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

        let completed = ring.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 = ring.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_ring_nearest_segment_early_stop() {
        let ring = Ring::new_ix(&octagon(), IndexKind::Natural).unwrap();
        let test_point = p(5.0, 5.0);
        let stop_at = 3;
        let mut count = 0;

        let success = ring.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 < ring.num_segments());
    }

    #[test]
    fn test_ring_nearest_segment_no_index() {
        let ring = Ring::new_ix(&octagon(), IndexKind::None).unwrap();
        let test_point = p(5.0, 5.0);
        let mut count = 0;

        let completed = ring.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, ring.num_segments());
    }

    #[test]
    fn test_ring_nearest_segment_closest_first() {
        let ring = Ring::new(&rectangle()).unwrap();
        let test_point = p(5.0, 0.1);

        let mut first_dist: Option<f64> = None;

        ring.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);
    }
}