Distance from point to a line

[cBournhonesque]

Hi, Thanks for the crate!

My use-case is that I'd like to compute the Euclidean distance from a point to a line.
It looks like R-tree could support this kind of queries: https://docs.rs/rstar/latest/rstar/trait.PointDistance.html

I'm not entirely sure how it would look like.
The tree leaves already seem to be rectangles (collapsed to be a single point). So it should be do-able to update the tree to be able to handle lines as well?

What do you think? I might start working on this, but i'd like to hear your input

[laundmo]

Thank you for showing interest in contributing!

You can definitely start working on it if you want, though i'd like a solution which can be expanded to more shapes and implementations.

i'd probably go with a trait which can be implemented for multiple spatial structures - with the rstar PointDistance and RTreeObject traits being a implementation detail hidden behind this trait. For now this trait should probably just be similar to a SpatialAccess specific to lines, containing the methods to query the tree for lines.

At some point i will likely need to come up with a more comprehensive solution to this, but that would require a bigger change and i haven't had the time for that lately.

If you do start working on this i'd really appreciate a Draft PR right away.

[laundmo]

Thinking on this some more, you might need to change the SpatialAccess to allow inserting lines - which might require some more work and a custom trait for any shape including points, complicating matters further. I'm afraid that will take some more consideration.

[cBournhonesque]

I think the solution is that instead of having EntityPoint2D or EntityPoint3D as the RTreeObj, the RTreeObj should be GeomWithData<Geometry, Entity>: https://github.com/georust/geo/blob/main/geo-types/src/geometry/mod.rs#L52

Then the RTreeObj and PointDistance trait can be implemented for all the different geometry types, with something like this:

impl RTreeObject for Geom {
    type Envelope = AABB<[f32; 2]>;

    fn envelope(&self) -> Self::Envelope {
        match self {
            Geom::Point(point) => AABB::from_point(point.into()),
            Geom::Line(line) => AABB::from_corners(line.start.into(), line.end.into()),
        }
    }
}


impl PointDistance for Geom {
    /// Euclidean distance between a Geom and a point
    /// Re-use the implementation from https://github.com/georust/geo/blob/geo-types-0.7.8/geo-types/src/private_utils.rs#L61
    /// Could do optimizations since our lines are only vertical or horizontal?
    fn distance_2(&self, point: &<Self::Envelope as Envelope>::Point) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar {
        match self {
            Geom::Point(geo_point) => geo_point.euclidean_distance(point),
            Geom::Line(line) => line.euclidean_distance(point),
        }
    }
}

I think the hard part is how to allow users to convert their own entities into a GeomObject (similar to what you are doing in the update_moved and add_added systems).
I see a few potential solutions:

• bevy gets updated with some geometry-related components (similar to Transform, but related to a geometry). We could then expect that users are using those bevy-provided components for their shapes, and just write the systems for these components. This is the ideal long-term solution I think?
• let the users provide their own WorldQuery struct like this: https://github.com/laundmo/bevy-spatial/blob/main/src/spatial_access.rs#L10 . We could request each WorldQueryItem to have a method to_geom or to_RTreeObject to convert the world query into something that can be inserted in the RTree. I think this could maybe work? It could add a lot of complexity/overhead though.

Something like this:

#[derive(WorldQuery)]
#[world_query(mutable)]
pub struct TrackedQuery<'a, TComp>
where
    TComp: Sync + Send + 'static,
{
    pub entity: Entity,
    // USER-PROVIDED QUERIES
    pub transform: &'a Transform,
    pub radius: &'a Radius,
    pub tracker: &'static mut MovementTracked<TComp>,
}

fn TrackedQueryItem(&self) -> Geometry {
    Geometry::Circle(self.transform, self.radius)
}

Right now I'm testing this idea in my project, where I only have points/segments. (and i need the distance from a point to a segment)

[laundmo]

let the users provide their own WorldQuery struct like this: main/src/spatial_access.rs#L10 . We could request each WorldQueryItem to have a method to_geom or to_RTreeObject to convert the world query into something that can be inserted in the RTree. I think this could maybe work? It could add a lot of complexity/overhead though.

this is along the lines of what ive been thinking too, i started on a redesign of that handling over in the coordinate-handling-redesign branch. I'll try to come up with a plan for that part in a bit which also considers my other thoughts on the matter.

[cBournhonesque]

Just sharing an example implementation for arbitrary geoms.
Users just have to create a WorldQuery for each geom, with 2 methods:

• is_moved: how to detect that the entity moved
• to_tree_object: how to transform the queried entity into an envelope (bounding-box) for r-star

/// Module with traits related to querying/tracking spatial entities
use std::marker::PhantomData;
use geo_types::{Line, Point as GeoPoint};
use rstar::RTreeObject;
use crate::ecs::query::{ReadOnlyWorldQuery, WorldQuery};
use crate::prelude::*;


/// Component that marks an entity as being tracked (added/updated to the r-tree)
#[derive(Component, Clone, Copy, Default)]
pub struct SpatialTracker;
// pub struct SpatialTracker<P: Point> {
    // /// tracks the last envelope at which the entity was updated in the tree.
    // pub last_envelope: Option<Envelope<Point=Point>>,
// }


pub type MySpatialTracker = SpatialTracker;
// pub type MySpatialTracker = SpatialTracker<MyRPoint>;
pub type PointTrackedSpatialQuery = TrackedSpatialQuery<PointSpatialWorldQuery, MyRTreeObject>;
pub type SegmentTrackedSpatialQuery = TrackedSpatialQuery<SegmentSpatialWorldQuery, MyRTreeObject>;


#[derive(WorldQuery)]
pub struct TrackedSpatialQuery<SubQuery, RObj>
    where
        SubQuery: SpatialWorldQuery<RObj>,
        RObj: RTreeObject + Send + Sync,
{
    pub entity: Entity,
    pub subquery: SubQuery,
    pub added_tracker: ChangeTrackers<SpatialTracker>,
    pub spatial_tracker: &'static SpatialTracker,
    // pub spatial_tracker: &'static mut SpatialTracker<Point>

    #[world_query(ignore)]
    _phantom: PhantomData<RObj>
}


impl<'a, SubQuery, RObj> TrackedSpatialQueryItem<'a, SubQuery, RObj>
    where
        SubQuery: SpatialWorldQuery<RObj>,
        // <SubQuery as WorldQuery>::Item: SpatialWorldQueryItem<RObj>,
        RObj: RTreeObject + Send + Sync
{
    /// Returns true if the spatial `Marker` has been newly added
    pub fn is_added(&self) -> bool {
        self.added_tracker.is_added()
    }

    /// Returns true if the entity is not new, and has moved
    pub fn is_moved(&self) -> bool
        where <SubQuery as WorldQuery>::Item<'a>: SpatialWorldQueryItem<'a, RObj> {

        !self.is_added() && self.subquery.is_moved()
    }

    /// Return the corresponding tree object
    pub fn to_tree_object(self) -> RObj
        where <SubQuery as WorldQuery>::Item<'a>: SpatialWorldQueryItem<'a, RObj> {
        self.subquery.to_tree_object(self.entity)
    }
}



/// A WorldQuery to query for entities that need to be inserted into an r-tree
pub trait SpatialWorldQuery<RObj>: ReadOnlyWorldQuery
    where RObj: RTreeObject + Send + Sync {
    type Item<'a>: SpatialWorldQueryItem<'a, RObj>;
}

/// The WorldQueryItem needs to satisfy certain requirements
pub trait SpatialWorldQueryItem<'a, RObj>
    where RObj: RTreeObject + Send + Sync {
    /// Returns true if the queries entity has moved
    fn is_moved(&self) -> bool;

    /// Converts the query items into a `RObj` that can be inserted into an r-tree
    fn to_tree_object(self, entity: Entity) -> RObj;
}


#[derive(WorldQuery)]
/// Query for single-points that need to be inserted into the R-tree
pub struct PointSpatialWorldQuery {
    pub position: &'static Position,
    pub moved_tracker: ChangeTrackers<Position>
}

impl SpatialWorldQuery<MyRTreeObject> for PointSpatialWorldQuery {
    type Item<'a> = PointSpatialWorldQueryItem<'a>;
}

impl SpatialWorldQueryItem<'_, MyRTreeObject> for PointSpatialWorldQueryItem<'_> {
    fn is_moved(&self) -> bool {
        self.moved_tracker.is_changed()
    }

    fn to_tree_object(self, entity: Entity) -> MyRTreeObject {
        MyRTreeObject::new(Geom::Point(self.position.into()), entity)
    }
}

#[derive(WorldQuery)]
/// Query for segments that need to be inserted into the R-tree
pub struct SegmentSpatialWorldQuery {
    pub segment: SegmentQuery,
    // A segment that moves always has their position moving, so we only need to check if
    // the `Position` component got updated
    pub moved_tracker: ChangeTrackers<Position>
}

impl SpatialWorldQuery<MyRTreeObject> for SegmentSpatialWorldQuery {
    type Item<'a> = SegmentSpatialWorldQueryItem<'a>;
}

impl SpatialWorldQueryItem<'_, MyRTreeObject> for SegmentSpatialWorldQueryItem<'_> {
    fn is_moved(&self) -> bool {
        self.moved_tracker.is_changed()
    }

    fn to_tree_object(self, entity: Entity) -> MyRTreeObject {
        let segment: Segment = self.segment.into();
        let (start, end) = segment.to_pair();
        let line = Line::new::<GeoPoint<f32>>(start.into(), end.into());
        MyRTreeObject::new(Geom::Line(line), entity)
    }
}