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
use crate::envelope::Envelope;
use crate::point::{Point, PointExt};
use crate::structures::aabb::AABB;
/// An object that can be inserted into an r-tree.
///
/// This trait must be implemented for any object that should be inserted into an r-tree.
/// Some simple objects that already implement this trait can be found in the
/// [primitives](mod.primitives.html) module.
///
/// The only property required of such an object is its [envelope](traits.Envelope.html).
/// Most simply, this method should return the [axis aligned bounding box](structs.AABB.html)
/// of the object, other envelope types may be supported in the future.
///
/// # Type parameters
/// `Envelope`: The objects envelope type. At the moment, only [AABB](structs.AABB.html) is
/// feasible.
///
/// # Example implementation
/// ```
/// use rstar::{RTreeObject, AABB};
///
/// struct Player
/// {
/// name: String,
/// x_coordinate: f64,
/// y_coordinate: f64
/// }
///
/// impl RTreeObject for Player
/// {
/// type Envelope = AABB<[f64; 2]>;
///
/// fn envelope(&self) -> Self::Envelope
/// {
/// AABB::from_point([self.x_coordinate, self.y_coordinate])
/// }
/// }
///
/// fn main()
/// {
/// use rstar::{RTree, AABB};
///
/// let mut tree = RTree::new();
///
/// // Insert a few players...
/// tree.insert(Player {
/// name: "Forlorn Freeman".into(),
/// x_coordinate: 1.,
/// y_coordinate: 0.
/// });
/// tree.insert(Player {
/// name: "Sarah Croft".into(),
/// x_coordinate: 0.5,
/// y_coordinate: 0.5,
/// });
/// tree.insert(Player {
/// name: "Geralt of Trivia".into(),
/// x_coordinate: 0.,
/// y_coordinate: 2.,
/// });
///
/// // Now we are ready to ask some questions!
/// let envelope = AABB::from_point([0.5, 0.5]);
/// let likely_sarah_croft = tree.locate_in_envelope(&envelope).next();
/// println!("Found {:?} lurking around at (0.5, 0.5)!", likely_sarah_croft.unwrap().name);
/// # assert!(likely_sarah_croft.is_some());
///
/// let unit_square = AABB::from_corners([-1.0, -1.0], [1., 1.]);
/// for player in tree.locate_in_envelope(&unit_square) {
/// println!("And here is {:?} spelunking in the unit square.", player.name);
/// }
/// # assert_eq!(tree.locate_in_envelope(&unit_square).count(), 2);
/// }
/// ```
pub trait RTreeObject {
/// The object's envelope type. Usually, [AABB](struct.AABB.html) will be the right choice.
/// This type also defines the objects dimensionality.
type Envelope: Envelope;
/// Returns the object's envelope.
///
/// Usually, this will return the object's [axis aligned bounding box](struct.AABB.html).
fn envelope(&self) -> Self::Envelope;
}
/// Defines objects which can calculate their minimal distance to a point.
///
/// This trait is most notably necessary for support of [nearest_neighbor](struct.RTree#method.nearest_neighbor)
/// queries.
///
/// # Example
/// ```
/// use rstar::{RTreeObject, PointDistance, AABB};
///
/// struct Circle
/// {
/// origin: [f32; 2],
/// radius: f32,
/// }
///
/// impl RTreeObject for Circle {
/// type Envelope = AABB<[f32; 2]>;
///
/// fn envelope(&self) -> Self::Envelope {
/// let corner_1 = [self.origin[0] - self.radius, self.origin[1] - self.radius];
/// let corner_2 = [self.origin[0] + self.radius, self.origin[1] + self.radius];
/// AABB::from_corners(corner_1, corner_2)
/// }
/// }
///
/// impl PointDistance for Circle
/// {
/// fn distance_2(&self, point: &[f32; 2]) -> f32
/// {
/// let d_x = self.origin[0] - point[0];
/// let d_y = self.origin[1] - point[1];
/// let distance_to_origin = (d_x * d_x + d_y * d_y).sqrt();
/// let distance_to_ring = distance_to_origin - self.radius;
/// let distance_to_circle = f32::max(0.0, distance_to_ring);
/// // We must return the squared distance!
/// distance_to_circle * distance_to_circle
/// }
///
/// // This implementation is not required but more efficient since it
/// // omits the calculation of a square root
/// fn contains_point(&self, point: &[f32; 2]) -> bool
/// {
/// let d_x = self.origin[0] - point[0];
/// let d_y = self.origin[1] - point[1];
/// let distance_to_origin_2 = (d_x * d_x + d_y * d_y);
/// let radius_2 = self.radius * self.radius;
/// distance_to_origin_2 <= radius_2
/// }
/// }
///
///
/// fn main() {
/// let circle = Circle {
/// origin: [1.0, 0.0],
/// radius: 1.0,
/// };
///
/// assert_eq!(circle.distance_2(&[-1.0, 0.0]), 1.0);
/// assert_eq!(circle.distance_2(&[-2.0, 0.0]), 4.0);
/// assert!(circle.contains_point(&[1.0, 0.0]));
/// }
/// ```
pub trait PointDistance: RTreeObject {
/// Returns the squared euclidean distance of an object to a point.
fn distance_2(
&self,
point: &<Self::Envelope as Envelope>::Point,
) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar;
/// Returns true if a point is contained within this object.
///
/// By default, any point returning a `distance_2` less than or equal to zero is considered to be
/// contained within `self`. Changing this default behavior is advised if calculating the squared distance
/// is more computational expensive a point containment check.
fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
self.distance_2(point) <= num_traits::zero()
}
}
impl<P> RTreeObject for P
where
P: Point,
{
type Envelope = AABB<P>;
fn envelope(&self) -> AABB<P> {
AABB::from_point(*self)
}
}
impl<P> PointDistance for P
where
P: Point,
{
fn distance_2(&self, point: &P) -> P::Scalar {
<Self as PointExt>::distance_2(self, point)
}
fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
self == point
}
}