Thoughts on algorithms for trait-based geometries

[kylebarron]

A continuation of previous trait-based geometry discussions #838, #1021, #1019.

Just putting some words down on the page because @urschrei nerdsniped me! On discord we were talking about coordinate representations for geo and geo-types and @urschrei asked what the blockers were on trait-based geometries. I responded that I thought figuring out the best way to implement algorithms on top of geometries was hard.

I started to play around with a bit of scratch traits, got something to compile, and figured I should jot down some notes in case it resonates with anyone else.

The main idea is having algorithm traits per geometry type that rely on that type's geometry trait definition. Then a blanket implementation over every geometry type that implements that trait.

use crate::geo_traits::{self, GeometryTrait, PointTrait};
use arrow_array::OffsetSizeTrait;
use geo::CoordNum;

pub trait AreaPoint<T>: PointTrait
where
    T: CoordNum,
{
    fn signed_area(&self) -> T {
        // signed area implemented solely in terms of PointTrait's methods
        todo!()
    }

    fn unsigned_area(&self) -> T {
        todo!()
    }
}

impl<T: CoordNum, P: PointTrait<T = T>> AreaPoint<T> for P {}

to keep a top-level Area trait as well, we could have

pub trait Area<'a, T>: GeometryTrait<'a, T = T>
where
    T: CoordNum,
{
    fn signed_area(&'a self) -> T {
        use geo_traits::GeometryType::*;
        match self.as_type() {
            Point(x) => AreaPoint::signed_area(x),
            _ => todo!(),
        }
    }

    fn unsigned_area(&'a self) -> T {
        use geo_traits::GeometryType::*;
        match self.as_type() {
            Point(x) => AreaPoint::unsigned_area(x),
            _ => todo!(),
        }
    }
}

impl<'a, T: CoordNum, P: GeometryTrait<'a, T = T>> Area<'a, T> for P {}

The main downside of this might be the proliferation of public traits? Is there a way to get around AreaPoint, AreaLineString, etc? The blanket implementation over GeometryTrait would also mean that it's impossible to implement GeometryTrait on, say, a geo::Point, because then there would be two trait options? The other option would opt in to implementing GeometryTrait on structs like geo::Point, so that people could keep using Area for all geometry types like they are now.

Who knows, this might fall apart on more complex traits like Intersection that require two geometries? Idk, thoughts?