5006008836

Build Type

push

github

Committed by GitHub

Commit Message

Merge #785 #787

Run Details

936 of 936 new or added lines in 50 files covered. (100.0%)

96010 of 107707 relevant lines covered (89.14%)

72676.46 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.47

/operators/src/processing/line_simplification.rs

use crate::{
    engine::{
        CanonicOperatorName, ExecutionContext, InitializedSources, InitializedVectorOperator,
        Operator, OperatorName, QueryContext, QueryProcessor, SingleVectorSource,
        TypedVectorQueryProcessor, VectorOperator, VectorQueryProcessor, VectorResultDescriptor,
        WorkflowOperatorPath,
    },
    util::Result,
};
use async_trait::async_trait;
use futures::{stream::BoxStream, StreamExt, TryStreamExt};
use geoengine_datatypes::{
    collections::{
        FeatureCollection, GeoFeatureCollectionModifications, IntoGeometryIterator, VectorDataType,
    },
    error::{BoxedResultExt, ErrorSource},
    primitives::{
        BoundingBox2D, Geometry, MultiLineString, MultiLineStringRef, MultiPolygon,
        MultiPolygonRef, SpatialResolution, VectorQueryRectangle,
    },
    util::arrow::ArrowTyped,
};
use rayon::prelude::{IntoParallelIterator, ParallelIterator};
use serde::{Deserialize, Serialize};
use snafu::Snafu;

/// A `LineSimplification` operator simplifies the geometry of a `Vector` by removing vertices.
///
/// The simplification is performed on the geometry of the `Vector` and not on the data.
/// The `LineSimplification` operator is only available for (multi-)lines or (multi-)polygons.
///
pub type LineSimplification = Operator<LineSimplificationParams, SingleVectorSource>;

impl OperatorName for LineSimplification {
    const TYPE_NAME: &'static str = "LineSimplification";
}

#[typetag::serde]
#[async_trait]
impl VectorOperator for LineSimplification {
    async fn _initialize(
        self: Box<Self>,
        path: WorkflowOperatorPath,
        context: &dyn ExecutionContext,
    ) -> Result<Box<dyn InitializedVectorOperator>> {
        if self
            .params
            .epsilon
            .map_or(false, |e| !e.is_finite() || e <= 0.0)
        {
            return Err(LineSimplificationError::InvalidEpsilon.into());
        }

        let name = CanonicOperatorName::from(&self);

        let sources = self.sources.initialize_sources(path, context).await?;
        let source = sources.vector;

        if source.result_descriptor().data_type != VectorDataType::MultiLineString
            && source.result_descriptor().data_type != VectorDataType::MultiPolygon
        {
            return Err(LineSimplificationError::InvalidGeometryType.into());
        }

        let initialized_operator = InitializedLineSimplification {
            name,
            result_descriptor: source.result_descriptor().clone(),
            source,
            algorithm: self.params.algorithm,
            epsilon: self.params.epsilon,
        };

        Ok(initialized_operator.boxed())
    }

    span_fn!(LineSimplification);
}

#[derive(Debug, Serialize, Deserialize, Clone, Copy)]
#[serde(rename_all = "camelCase")]
pub struct LineSimplificationParams {
    pub algorithm: LineSimplificationAlgorithm,
    /// The epsilon parameter is used to determine the maximum distance between the original and the simplified geometry.
    /// If `None` is provided, the epsilon is derived by the query's [`SpatialResolution`].
    pub epsilon: Option<f64>,
}

#[derive(Debug, Serialize, Deserialize, Clone, Copy)]
#[serde(rename_all = "camelCase")]
pub enum LineSimplificationAlgorithm {
    DouglasPeucker,
    Visvalingam,
}

pub struct InitializedLineSimplification {
    name: CanonicOperatorName,
    result_descriptor: VectorResultDescriptor,
    source: Box<dyn InitializedVectorOperator>,
    algorithm: LineSimplificationAlgorithm,
    epsilon: Option<f64>,
}

impl InitializedVectorOperator for InitializedLineSimplification {
    fn result_descriptor(&self) -> &VectorResultDescriptor {
        &self.result_descriptor
    }

    fn query_processor(&self) -> Result<TypedVectorQueryProcessor> {
        match (self.source.query_processor()?, self.algorithm) {
            (
                TypedVectorQueryProcessor::Data(..) | TypedVectorQueryProcessor::MultiPoint(..),
                _,
            ) => Err(LineSimplificationError::InvalidGeometryType.into()),
            (
                TypedVectorQueryProcessor::MultiLineString(source),
                LineSimplificationAlgorithm::DouglasPeucker,
            ) => Ok(TypedVectorQueryProcessor::MultiLineString(
                LineSimplificationProcessor {
                    source,
                    _algorithm: DouglasPeucker,
                    epsilon: self.epsilon,
                }
                .boxed(),
            )),
            (
                TypedVectorQueryProcessor::MultiLineString(source),
                LineSimplificationAlgorithm::Visvalingam,
            ) => Ok(TypedVectorQueryProcessor::MultiLineString(
                LineSimplificationProcessor {
                    source,
                    _algorithm: Visvalingam,
                    epsilon: self.epsilon,
                }
                .boxed(),
            )),
            (
                TypedVectorQueryProcessor::MultiPolygon(source),
                LineSimplificationAlgorithm::DouglasPeucker,
            ) => Ok(TypedVectorQueryProcessor::MultiPolygon(
                LineSimplificationProcessor {
                    source,
                    _algorithm: DouglasPeucker,
                    epsilon: self.epsilon,
                }
                .boxed(),
            )),
            (
                TypedVectorQueryProcessor::MultiPolygon(source),
                LineSimplificationAlgorithm::Visvalingam,
            ) => Ok(TypedVectorQueryProcessor::MultiPolygon(
                LineSimplificationProcessor {
                    source,
                    _algorithm: Visvalingam,
                    epsilon: self.epsilon,
                }
                .boxed(),
            )),
        }
    }

    fn canonic_name(&self) -> CanonicOperatorName {
        self.name.clone()
    }
}

struct LineSimplificationProcessor<P, G, A>
where
    P: VectorQueryProcessor<VectorType = FeatureCollection<G>>,
    G: Geometry,
    for<'c> FeatureCollection<G>: IntoGeometryIterator<'c>,
    for<'c> A: LineSimplificationAlgorithmImpl<
        <FeatureCollection<G> as IntoGeometryIterator<'c>>::GeometryType,
        G,
    >,
{
    source: P,
    _algorithm: A,
    epsilon: Option<f64>,
}

pub trait LineSimplificationAlgorithmImpl<In, Out: Geometry>: Send + Sync {
    fn simplify(geometry_ref: In, epsilon: f64) -> Out;

    fn derive_epsilon(spatial_resolution: SpatialResolution) -> f64 {
        f64::sqrt(spatial_resolution.x.powi(2) + spatial_resolution.y.powi(2)) / f64::sqrt(2.)
    }
}

struct DouglasPeucker;
struct Visvalingam;

impl<'c> LineSimplificationAlgorithmImpl<MultiLineStringRef<'c>, MultiLineString>
    for DouglasPeucker
{
    fn simplify(geometry: MultiLineStringRef<'c>, epsilon: f64) -> MultiLineString {
        use geo::Simplify;

        let geo_geometry = geo::MultiLineString::<f64>::from(&geometry);
        let geo_geometry = geo_geometry.simplify(&epsilon);
        geo_geometry.into()
    }
}

impl<'c> LineSimplificationAlgorithmImpl<MultiPolygonRef<'c>, MultiPolygon> for DouglasPeucker {
    fn simplify(geometry: MultiPolygonRef<'c>, epsilon: f64) -> MultiPolygon {
        use geo::Simplify;

        let geo_geometry = geo::MultiPolygon::<f64>::from(&geometry);
        let geo_geometry = geo_geometry.simplify(&epsilon);
        geo_geometry.into()
    }
}

impl<'c> LineSimplificationAlgorithmImpl<MultiLineStringRef<'c>, MultiLineString> for Visvalingam {
    fn simplify(geometry: MultiLineStringRef<'c>, epsilon: f64) -> MultiLineString {
        use geo::SimplifyVWPreserve;

        let geo_geometry = geo::MultiLineString::<f64>::from(&geometry);
        let geo_geometry = geo_geometry.simplifyvw_preserve(&epsilon);
        geo_geometry.into()
    }

    fn derive_epsilon(spatial_resolution: SpatialResolution) -> f64 {
        // for visvalingam, the epsilon is squared since it reflects some triangle area
        // this is a heuristic, though
        spatial_resolution.x * spatial_resolution.y
    }
}

impl<'c> LineSimplificationAlgorithmImpl<MultiPolygonRef<'c>, MultiPolygon> for Visvalingam {
    fn simplify(geometry: MultiPolygonRef<'c>, epsilon: f64) -> MultiPolygon {
        use geo::SimplifyVWPreserve;

        let geo_geometry = geo::MultiPolygon::<f64>::from(&geometry);
        let geo_geometry = geo_geometry.simplifyvw_preserve(&epsilon);
        geo_geometry.into()
    }

    fn derive_epsilon(spatial_resolution: SpatialResolution) -> f64 {
        // for visvalingam, the epsilon is squared since it reflects some triangle area
        // this is a heuristic, though
        spatial_resolution.x * spatial_resolution.y
    }
}

impl<P, G, A> LineSimplificationProcessor<P, G, A>
where
    P: VectorQueryProcessor<VectorType = FeatureCollection<G>>,
    G: Geometry,
    for<'c> FeatureCollection<G>: IntoGeometryIterator<'c>
        + GeoFeatureCollectionModifications<G, Output = FeatureCollection<G>>,
    for<'c> A: LineSimplificationAlgorithmImpl<
        <FeatureCollection<G> as IntoGeometryIterator<'c>>::GeometryType,
        G,
    >,
{
    fn simplify(collection: &FeatureCollection<G>, epsilon: f64) -> Result<FeatureCollection<G>> {
        // TODO: chunk within parallelization to reduce overhead if necessary

        let simplified_geometries = collection
            .geometries()
            .into_par_iter()
            .map(|geometry| A::simplify(geometry, epsilon))
            .collect();

        Ok(collection
            .replace_geometries(simplified_geometries)
            .boxed_context(error::ErrorDuringSimplification)?)
    }
}

#[async_trait]
impl<P, G, A> QueryProcessor for LineSimplificationProcessor<P, G, A>
where
    P: QueryProcessor<Output = FeatureCollection<G>, SpatialBounds = BoundingBox2D>,
    G: Geometry + ArrowTyped + 'static,
    for<'c> FeatureCollection<G>: IntoGeometryIterator<'c>
        + GeoFeatureCollectionModifications<G, Output = FeatureCollection<G>>,
    for<'c> A: LineSimplificationAlgorithmImpl<
        <FeatureCollection<G> as IntoGeometryIterator<'c>>::GeometryType,
        G,
    >,
{
    type Output = FeatureCollection<G>;
    type SpatialBounds = BoundingBox2D;

    async fn _query<'a>(
        &'a self,
        query: VectorQueryRectangle,
        ctx: &'a dyn QueryContext,
    ) -> Result<BoxStream<'a, Result<Self::Output>>> {
        let chunks = self.source.query(query, ctx).await?;

        let epsilon = self
            .epsilon
            .unwrap_or_else(|| A::derive_epsilon(query.spatial_resolution));

        let simplified_chunks = chunks.and_then(move |chunk| async move {
            crate::util::spawn_blocking_with_thread_pool(ctx.thread_pool().clone(), move || {
                Self::simplify(&chunk, epsilon)
            })
            .await
            .boxed_context(error::UnexpectedInternal)?
        });

        Ok(simplified_chunks.boxed())
    }
}

#[derive(Debug, Snafu)]
#[snafu(visibility(pub(crate)), context(suffix(false)), module(error))]
pub enum LineSimplificationError {
    #[snafu(display("`epsilon` parameter must be greater than 0"))]
    InvalidEpsilon,
    #[snafu(display("Geometry must be of type `MultiLineString` or `MultiPolygon`"))]
    InvalidGeometryType,
    #[snafu(display("Error during simplification of geometry: {}", source))]
    ErrorDuringSimplification { source: Box<dyn ErrorSource> },
    #[snafu(display("Unexpected internal error: {}", source))]
    UnexpectedInternal { source: Box<dyn ErrorSource> },
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        engine::{MockExecutionContext, MockQueryContext, StaticMetaData},
        mock::MockFeatureCollectionSource,
        source::{
            OgrSource, OgrSourceColumnSpec, OgrSourceDataset, OgrSourceDatasetTimeType,
            OgrSourceErrorSpec, OgrSourceParameters,
        },
    };
    use geoengine_datatypes::{
        collections::{
            FeatureCollectionInfos, GeometryCollection, MultiLineStringCollection,
            MultiPointCollection, MultiPolygonCollection,
        },
        dataset::{DataId, DatasetId},
        primitives::{FeatureData, MultiLineString, MultiPoint, TimeInterval},
        spatial_reference::SpatialReference,
        test_data,
        util::{test::TestDefault, Identifier},
    };

    #[tokio::test]
    async fn test_ser_de() {
        let operator = LineSimplification {
            params: LineSimplificationParams {
                epsilon: Some(1.0),
                algorithm: LineSimplificationAlgorithm::DouglasPeucker,
            },
            sources: MockFeatureCollectionSource::<MultiPolygon>::multiple(vec![])
                .boxed()
                .into(),
        }
        .boxed();

        let serialized = serde_json::to_value(&operator).unwrap();

        assert_eq!(
            serialized,
            serde_json::json!({
                "type": "LineSimplification",
                "params": {
                    "epsilon": 1.0,
                    "algorithm": "douglasPeucker",
                },
                "sources": {
                    "vector": {
                        "type": "MockFeatureCollectionSourceMultiPolygon",
                        "params": {
                            "collections": [],
                            "spatialReference": "EPSG:4326",
                            "measurements": null,
                        }
                    }
                },
            })
        );

        let _operator: Box<dyn VectorOperator> = serde_json::from_value(serialized).unwrap();
    }

    #[tokio::test]
    async fn test_errors() {
        // zero epsilon
        assert!(LineSimplification {
            params: LineSimplificationParams {
                epsilon: Some(0.0),
                algorithm: LineSimplificationAlgorithm::DouglasPeucker,
            },
            sources: MockFeatureCollectionSource::<MultiPolygon>::single(
                MultiPolygonCollection::empty()
            )
            .boxed()
            .into(),
        }
        .boxed()
        .initialize(
            WorkflowOperatorPath::initialize_root(),
            &MockExecutionContext::test_default()
        )
        .await
        .is_err());

        // invalid epsilon
        assert!(LineSimplification {
            params: LineSimplificationParams {
                epsilon: Some(f64::NAN),
                algorithm: LineSimplificationAlgorithm::Visvalingam,
            },
            sources: MockFeatureCollectionSource::<MultiPolygon>::single(
                MultiPolygonCollection::empty()
            )
            .boxed()
            .into(),
        }
        .boxed()
        .initialize(
            WorkflowOperatorPath::initialize_root(),
            &MockExecutionContext::test_default()
        )
        .await
        .is_err());

        // not lines or polygons
        assert!(LineSimplification {
            params: LineSimplificationParams {
                epsilon: None,
                algorithm: LineSimplificationAlgorithm::DouglasPeucker,
            },
            sources: MockFeatureCollectionSource::<MultiPoint>::single(
                MultiPointCollection::empty()
            )
            .boxed()
            .into(),
        }
        .boxed()
        .initialize(
            WorkflowOperatorPath::initialize_root(),
            &MockExecutionContext::test_default()
        )
        .await
        .is_err());
    }

    #[tokio::test]
    async fn test_line_simplification() {
        let collection = MultiLineStringCollection::from_data(
            vec![
                MultiLineString::new(vec![vec![
                    (0.0, 0.0).into(),
                    (5.0, 4.0).into(),
                    (11.0, 5.5).into(),
                    (17.3, 3.2).into(),
                    (27.8, 0.1).into(),
                ]])
                .unwrap(),
                MultiLineString::new(vec![vec![(0.0, 0.0).into(), (5.0, 4.0).into()]]).unwrap(),
            ],
            vec![TimeInterval::new(0, 1).unwrap(); 2],
            [("foo".to_string(), FeatureData::Float(vec![0., 1.]))]
                .iter()
                .cloned()
                .collect(),
        )
        .unwrap();

        let source = MockFeatureCollectionSource::single(collection.clone()).boxed();

        let simplification = LineSimplification {
            params: LineSimplificationParams {
                epsilon: Some(1.0),
                algorithm: LineSimplificationAlgorithm::DouglasPeucker,
            },
            sources: source.into(),
        }
        .boxed();

        let initialized = simplification
            .initialize(
                WorkflowOperatorPath::initialize_root(),
                &MockExecutionContext::test_default(),
            )
            .await
            .unwrap();

        let processor = initialized
            .query_processor()
            .unwrap()
            .multi_line_string()
            .unwrap();

        let query_rectangle = VectorQueryRectangle {
            spatial_bounds: BoundingBox2D::new((0., 0.).into(), (4., 4.).into()).unwrap(),
            time_interval: TimeInterval::default(),
            spatial_resolution: SpatialResolution::one(),
        };

        let query_ctx = MockQueryContext::test_default();

        let stream = processor.query(query_rectangle, &query_ctx).await.unwrap();

        let collections: Vec<MultiLineStringCollection> =
            stream.map(Result::unwrap).collect().await;

        assert_eq!(collections.len(), 1);

        let expected = MultiLineStringCollection::from_data(
            vec![
                MultiLineString::new(vec![vec![
                    (0.0, 0.0).into(),
                    (5.0, 4.0).into(),
                    (11.0, 5.5).into(),
                    (27.8, 0.1).into(),
                ]])
                .unwrap(),
                MultiLineString::new(vec![vec![(0.0, 0.0).into(), (5.0, 4.0).into()]]).unwrap(),
            ],
            vec![TimeInterval::new(0, 1).unwrap(); 2],
            [("foo".to_string(), FeatureData::Float(vec![0., 1.]))]
                .iter()
                .cloned()
                .collect(),
        )
        .unwrap();

        assert_eq!(collections[0], expected);
    }

    #[tokio::test]
    async fn test_polygon_simplification() {
        let id: DataId = DatasetId::new().into();
        let mut exe_ctx = MockExecutionContext::test_default();
        exe_ctx.add_meta_data::<OgrSourceDataset, VectorResultDescriptor, VectorQueryRectangle>(
            id.clone(),
            Box::new(StaticMetaData {
                loading_info: OgrSourceDataset {
                    file_name: test_data!("vector/data/germany_polygon.gpkg").into(),
                    layer_name: "test_germany".to_owned(),
                    data_type: Some(VectorDataType::MultiPolygon),
                    time: OgrSourceDatasetTimeType::None,
                    default_geometry: None,
                    columns: Some(OgrSourceColumnSpec {
                        format_specifics: None,
                        x: String::new(),
                        y: None,
                        int: vec![],
                        float: vec![],
                        text: vec![],
                        bool: vec![],
                        datetime: vec![],
                        rename: None,
                    }),
                    force_ogr_time_filter: false,
                    force_ogr_spatial_filter: false,
                    on_error: OgrSourceErrorSpec::Abort,
                    sql_query: None,
                    attribute_query: None,
                },
                result_descriptor: VectorResultDescriptor {
                    data_type: VectorDataType::MultiPolygon,
                    spatial_reference: SpatialReference::epsg_4326().into(),
                    columns: Default::default(),
                    time: None,
                    bbox: None,
                },
                phantom: Default::default(),
            }),
        );

        let simplification = LineSimplification {
            params: LineSimplificationParams {
                epsilon: None,
                algorithm: LineSimplificationAlgorithm::Visvalingam,
            },
            sources: OgrSource {
                params: OgrSourceParameters {
                    data: id,
                    attribute_projection: None,
                    attribute_filters: None,
                },
            }
            .boxed()
            .into(),
        }
        .boxed()
        .initialize(WorkflowOperatorPath::initialize_root(), &exe_ctx)
        .await
        .unwrap();

        assert_eq!(
            simplification.result_descriptor().data_type,
            VectorDataType::MultiPolygon
        );

        let query_processor = simplification
            .query_processor()
            .unwrap()
            .multi_polygon()
            .unwrap();

        let query_bbox = BoundingBox2D::new((-180.0, -90.0).into(), (180.00, 90.0).into()).unwrap();

        let query_context = MockQueryContext::test_default();
        let query = query_processor
            .query(
                VectorQueryRectangle {
                    spatial_bounds: query_bbox,
                    time_interval: Default::default(),
                    spatial_resolution: SpatialResolution::new(1., 1.).unwrap(),
                },
                &query_context,
            )
            .await
            .unwrap();

        let result: Vec<MultiPolygonCollection> = query.try_collect().await.unwrap();

        assert_eq!(result.len(), 1);
        let result = result.into_iter().next().unwrap();

        assert_eq!(result.len(), 1);
        assert_eq!(result.feature_offsets().len(), 2);
        assert_eq!(result.polygon_offsets().len(), 23);
        assert_eq!(result.ring_offsets().len(), 23);
        assert_eq!(result.coordinates().len(), 98 /* was 3027 */);
    }
}

1	use crate::{
2	engine::{
3	CanonicOperatorName, ExecutionContext, InitializedSources, InitializedVectorOperator,
4	Operator, OperatorName, QueryContext, QueryProcessor, SingleVectorSource,
5	TypedVectorQueryProcessor, VectorOperator, VectorQueryProcessor, VectorResultDescriptor,
6	WorkflowOperatorPath,
7	},
8	util::Result,
9	};
10	use async_trait::async_trait;
11	use futures::{stream::BoxStream, StreamExt, TryStreamExt};
12	use geoengine_datatypes::{
13	collections::{
14	FeatureCollection, GeoFeatureCollectionModifications, IntoGeometryIterator, VectorDataType,
15	},
16	error::{BoxedResultExt, ErrorSource},
17	primitives::{
18	BoundingBox2D, Geometry, MultiLineString, MultiLineStringRef, MultiPolygon,
19	MultiPolygonRef, SpatialResolution, VectorQueryRectangle,
20	},
21	util::arrow::ArrowTyped,
22	};
23	use rayon::prelude::{IntoParallelIterator, ParallelIterator};
24	use serde::{Deserialize, Serialize};
25	use snafu::Snafu;
26
27	/// A `LineSimplification` operator simplifies the geometry of a `Vector` by removing vertices.
28	///
29	/// The simplification is performed on the geometry of the `Vector` and not on the data.
30	/// The `LineSimplification` operator is only available for (multi-)lines or (multi-)polygons.
31	///
32	pub type LineSimplification = Operator<LineSimplificationParams, SingleVectorSource>;
33
34	impl OperatorName for LineSimplification {
35	const TYPE_NAME: &'static str = "LineSimplification";
36	}
37
38	#[typetag::serde]	1✔
39	#[async_trait]
40	impl VectorOperator for LineSimplification {
41	async fn _initialize(	5✔
42	self: Box<Self>,	5✔
43	path: WorkflowOperatorPath,	5✔
44	context: &dyn ExecutionContext,	5✔
45	) -> Result<Box<dyn InitializedVectorOperator>> {	5✔
46	if self	5✔
47	.params	5✔
48	.epsilon	5✔
49	.map_or(false, \|e\| !e.is_finite() \|\| e <= 0.0)	5✔
50	{
51	return Err(LineSimplificationError::InvalidEpsilon.into());	2✔
52	}	3✔
53		3✔
54	let name = CanonicOperatorName::from(&self);	3✔
55
56	let sources = self.sources.initialize_sources(path, context).await?;	3✔
57	let source = sources.vector;	3✔
58		3✔
59	if source.result_descriptor().data_type != VectorDataType::MultiLineString	3✔
60	&& source.result_descriptor().data_type != VectorDataType::MultiPolygon	2✔
61	{
62	return Err(LineSimplificationError::InvalidGeometryType.into());	1✔
63	}	2✔
64		2✔
65	let initialized_operator = InitializedLineSimplification {	2✔
66	name,	2✔
67	result_descriptor: source.result_descriptor().clone(),	2✔
68	source,	2✔
69	algorithm: self.params.algorithm,	2✔
70	epsilon: self.params.epsilon,	2✔
71	};	2✔
72		2✔
73	Ok(initialized_operator.boxed())	2✔
74	}	10✔
75
76	span_fn!(LineSimplification);	×
77	}
78
79	#[derive(Debug, Serialize, Deserialize, Clone, Copy)]	5✔
80	#[serde(rename_all = "camelCase")]
81	pub struct LineSimplificationParams {
82	pub algorithm: LineSimplificationAlgorithm,
83	/// The epsilon parameter is used to determine the maximum distance between the original and the simplified geometry.
84	/// If `None` is provided, the epsilon is derived by the query's [`SpatialResolution`].
85	pub epsilon: Option<f64>,
86	}
87
88	#[derive(Debug, Serialize, Deserialize, Clone, Copy)]	4✔
89	#[serde(rename_all = "camelCase")]
90	pub enum LineSimplificationAlgorithm {
91	DouglasPeucker,
92	Visvalingam,
93	}
94
95	pub struct InitializedLineSimplification {
96	name: CanonicOperatorName,
97	result_descriptor: VectorResultDescriptor,
98	source: Box<dyn InitializedVectorOperator>,
99	algorithm: LineSimplificationAlgorithm,
100	epsilon: Option<f64>,
101	}
102
103	impl InitializedVectorOperator for InitializedLineSimplification {
104	fn result_descriptor(&self) -> &VectorResultDescriptor {	1✔
105	&self.result_descriptor	1✔
106	}	1✔
107
108	fn query_processor(&self) -> Result<TypedVectorQueryProcessor> {	2✔
109	match (self.source.query_processor()?, self.algorithm) {	2✔
110	(
111	TypedVectorQueryProcessor::Data(..) \| TypedVectorQueryProcessor::MultiPoint(..),
112	_,
113	) => Err(LineSimplificationError::InvalidGeometryType.into()),	×
114	(
115	TypedVectorQueryProcessor::MultiLineString(source),	1✔
116	LineSimplificationAlgorithm::DouglasPeucker,	1✔
117	) => Ok(TypedVectorQueryProcessor::MultiLineString(	1✔
118	LineSimplificationProcessor {	1✔
119	source,	1✔
120	_algorithm: DouglasPeucker,	1✔
121	epsilon: self.epsilon,	1✔
122	}	1✔
123	.boxed(),	1✔
124	)),	1✔
125	(
126	TypedVectorQueryProcessor::MultiLineString(source),	×
127	LineSimplificationAlgorithm::Visvalingam,	×
128	) => Ok(TypedVectorQueryProcessor::MultiLineString(	×
129	LineSimplificationProcessor {	×
130	source,	×
131	_algorithm: Visvalingam,	×
132	epsilon: self.epsilon,	×
133	}	×
134	.boxed(),	×
135	)),	×
136	(
137	TypedVectorQueryProcessor::MultiPolygon(source),	×
138	LineSimplificationAlgorithm::DouglasPeucker,	×
139	) => Ok(TypedVectorQueryProcessor::MultiPolygon(	×
140	LineSimplificationProcessor {	×
141	source,	×
142	_algorithm: DouglasPeucker,	×
143	epsilon: self.epsilon,	×
144	}	×
145	.boxed(),	×
146	)),	×
147	(
148	TypedVectorQueryProcessor::MultiPolygon(source),	1✔
149	LineSimplificationAlgorithm::Visvalingam,	1✔
150	) => Ok(TypedVectorQueryProcessor::MultiPolygon(	1✔
151	LineSimplificationProcessor {	1✔
152	source,	1✔
153	_algorithm: Visvalingam,	1✔
154	epsilon: self.epsilon,	1✔
155	}	1✔
156	.boxed(),	1✔
157	)),	1✔
158	}
159	}	2✔
160
161	fn canonic_name(&self) -> CanonicOperatorName {	×
162	self.name.clone()	×
163	}	×
164	}
165
166	struct LineSimplificationProcessor<P, G, A>
167	where
168	P: VectorQueryProcessor<VectorType = FeatureCollection<G>>,
169	G: Geometry,
170	for<'c> FeatureCollection<G>: IntoGeometryIterator<'c>,
171	for<'c> A: LineSimplificationAlgorithmImpl<
172	<FeatureCollection<G> as IntoGeometryIterator<'c>>::GeometryType,
173	G,
174	>,
175	{
176	source: P,
177	_algorithm: A,
178	epsilon: Option<f64>,
179	}
180
181	pub trait LineSimplificationAlgorithmImpl<In, Out: Geometry>: Send + Sync {
182	fn simplify(geometry_ref: In, epsilon: f64) -> Out;
183
184	fn derive_epsilon(spatial_resolution: SpatialResolution) -> f64 {	×
185	f64::sqrt(spatial_resolution.x.powi(2) + spatial_resolution.y.powi(2)) / f64::sqrt(2.)	×
186	}	×
187	}
188
189	struct DouglasPeucker;
190	struct Visvalingam;
191
192	impl<'c> LineSimplificationAlgorithmImpl<MultiLineStringRef<'c>, MultiLineString>
193	for DouglasPeucker
194	{
195	fn simplify(geometry: MultiLineStringRef<'c>, epsilon: f64) -> MultiLineString {	2✔
196	use geo::Simplify;	2✔
197		2✔
198	let geo_geometry = geo::MultiLineString::<f64>::from(&geometry);	2✔
199	let geo_geometry = geo_geometry.simplify(&epsilon);	2✔
200	geo_geometry.into()	2✔
201	}	2✔
202	}
203
204	impl<'c> LineSimplificationAlgorithmImpl<MultiPolygonRef<'c>, MultiPolygon> for DouglasPeucker {
205	fn simplify(geometry: MultiPolygonRef<'c>, epsilon: f64) -> MultiPolygon {	×
206	use geo::Simplify;	×
207		×
208	let geo_geometry = geo::MultiPolygon::<f64>::from(&geometry);	×
209	let geo_geometry = geo_geometry.simplify(&epsilon);	×
210	geo_geometry.into()	×
211	}	×
212	}
213
214	impl<'c> LineSimplificationAlgorithmImpl<MultiLineStringRef<'c>, MultiLineString> for Visvalingam {
215	fn simplify(geometry: MultiLineStringRef<'c>, epsilon: f64) -> MultiLineString {	×
216	use geo::SimplifyVWPreserve;	×
217		×
218	let geo_geometry = geo::MultiLineString::<f64>::from(&geometry);	×
219	let geo_geometry = geo_geometry.simplifyvw_preserve(&epsilon);	×
220	geo_geometry.into()	×
221	}	×
222
223	fn derive_epsilon(spatial_resolution: SpatialResolution) -> f64 {	×
224	// for visvalingam, the epsilon is squared since it reflects some triangle area	×
225	// this is a heuristic, though	×
226	spatial_resolution.x * spatial_resolution.y	×
227	}	×
228	}
229
230	impl<'c> LineSimplificationAlgorithmImpl<MultiPolygonRef<'c>, MultiPolygon> for Visvalingam {
231	fn simplify(geometry: MultiPolygonRef<'c>, epsilon: f64) -> MultiPolygon {	1✔
232	use geo::SimplifyVWPreserve;	1✔
233		1✔
234	let geo_geometry = geo::MultiPolygon::<f64>::from(&geometry);	1✔
235	let geo_geometry = geo_geometry.simplifyvw_preserve(&epsilon);	1✔
236	geo_geometry.into()	1✔
237	}	1✔
238
239	fn derive_epsilon(spatial_resolution: SpatialResolution) -> f64 {	1✔
240	// for visvalingam, the epsilon is squared since it reflects some triangle area	1✔
241	// this is a heuristic, though	1✔
242	spatial_resolution.x * spatial_resolution.y	1✔
243	}	1✔
244	}
245
246	impl<P, G, A> LineSimplificationProcessor<P, G, A>
247	where
248	P: VectorQueryProcessor<VectorType = FeatureCollection<G>>,
249	G: Geometry,
250	for<'c> FeatureCollection<G>: IntoGeometryIterator<'c>
251	+ GeoFeatureCollectionModifications<G, Output = FeatureCollection<G>>,
252	for<'c> A: LineSimplificationAlgorithmImpl<
253	<FeatureCollection<G> as IntoGeometryIterator<'c>>::GeometryType,
254	G,
255	>,
256	{
257	fn simplify(collection: &FeatureCollection<G>, epsilon: f64) -> Result<FeatureCollection<G>> {	2✔
258	// TODO: chunk within parallelization to reduce overhead if necessary	2✔
259		2✔
260	let simplified_geometries = collection	2✔
261	.geometries()	2✔
262	.into_par_iter()	2✔
263	.map(\|geometry\| A::simplify(geometry, epsilon))	3✔
264	.collect();	2✔
265		2✔
266	Ok(collection	2✔
267	.replace_geometries(simplified_geometries)	2✔
268	.boxed_context(error::ErrorDuringSimplification)?)	2✔
269	}	2✔
270	}
271
272	#[async_trait]
273	impl<P, G, A> QueryProcessor for LineSimplificationProcessor<P, G, A>
274	where
275	P: QueryProcessor<Output = FeatureCollection<G>, SpatialBounds = BoundingBox2D>,
276	G: Geometry + ArrowTyped + 'static,
277	for<'c> FeatureCollection<G>: IntoGeometryIterator<'c>
278	+ GeoFeatureCollectionModifications<G, Output = FeatureCollection<G>>,
279	for<'c> A: LineSimplificationAlgorithmImpl<
280	<FeatureCollection<G> as IntoGeometryIterator<'c>>::GeometryType,
281	G,
282	>,
283	{
284	type Output = FeatureCollection<G>;
285	type SpatialBounds = BoundingBox2D;
286
287	async fn _query<'a>(	2✔
288	&'a self,	2✔
289	query: VectorQueryRectangle,	2✔
290	ctx: &'a dyn QueryContext,	2✔
291	) -> Result<BoxStream<'a, Result<Self::Output>>> {	2✔
292	let chunks = self.source.query(query, ctx).await?;	2✔
293
294	let epsilon = self	2✔
295	.epsilon	2✔
296	.unwrap_or_else(\|\| A::derive_epsilon(query.spatial_resolution));	2✔
297		2✔
298	let simplified_chunks = chunks.and_then(move \|chunk\| async move {	2✔
299	crate::util::spawn_blocking_with_thread_pool(ctx.thread_pool().clone(), move \|\| {	2✔
300	Self::simplify(&chunk, epsilon)	2✔
301	})	2✔
302	.await	2✔
303	.boxed_context(error::UnexpectedInternal)?	2✔
304	});	2✔
305		2✔
306	Ok(simplified_chunks.boxed())	2✔
307	}	4✔
308	}
309
310	#[derive(Debug, Snafu)]	×
311	#[snafu(visibility(pub(crate)), context(suffix(false)), module(error))]
312	pub enum LineSimplificationError {
313	#[snafu(display("`epsilon` parameter must be greater than 0"))]
314	InvalidEpsilon,
315	#[snafu(display("Geometry must be of type `MultiLineString` or `MultiPolygon`"))]
316	InvalidGeometryType,
317	#[snafu(display("Error during simplification of geometry: {}", source))]
318	ErrorDuringSimplification { source: Box<dyn ErrorSource> },
319	#[snafu(display("Unexpected internal error: {}", source))]
320	UnexpectedInternal { source: Box<dyn ErrorSource> },
321	}
322
323	#[cfg(test)]
324	mod tests {
325	use super::*;
326	use crate::{
327	engine::{MockExecutionContext, MockQueryContext, StaticMetaData},
328	mock::MockFeatureCollectionSource,
329	source::{
330	OgrSource, OgrSourceColumnSpec, OgrSourceDataset, OgrSourceDatasetTimeType,
331	OgrSourceErrorSpec, OgrSourceParameters,
332	},
333	};
334	use geoengine_datatypes::{
335	collections::{
336	FeatureCollectionInfos, GeometryCollection, MultiLineStringCollection,
337	MultiPointCollection, MultiPolygonCollection,
338	},
339	dataset::{DataId, DatasetId},
340	primitives::{FeatureData, MultiLineString, MultiPoint, TimeInterval},
341	spatial_reference::SpatialReference,
342	test_data,
343	util::{test::TestDefault, Identifier},
344	};
345
346	#[tokio::test]	1✔
347	async fn test_ser_de() {	1✔
348	let operator = LineSimplification {	1✔
349	params: LineSimplificationParams {	1✔
350	epsilon: Some(1.0),	1✔
351	algorithm: LineSimplificationAlgorithm::DouglasPeucker,	1✔
352	},	1✔
353	sources: MockFeatureCollectionSource::<MultiPolygon>::multiple(vec![])	1✔
354	.boxed()	1✔
355	.into(),	1✔
356	}	1✔
357	.boxed();	1✔
358		1✔
359	let serialized = serde_json::to_value(&operator).unwrap();	1✔
360		1✔
361	assert_eq!(	1✔
362	serialized,	1✔
363	serde_json::json!({	1✔
364	"type": "LineSimplification",	1✔
365	"params": {	1✔
366	"epsilon": 1.0,	1✔
367	"algorithm": "douglasPeucker",	1✔
368	},	1✔
369	"sources": {	1✔
370	"vector": {	1✔
371	"type": "MockFeatureCollectionSourceMultiPolygon",	1✔
372	"params": {	1✔
373	"collections": [],	1✔
374	"spatialReference": "EPSG:4326",	1✔
375	"measurements": null,	1✔
376	}	1✔
377	}	1✔
378	},	1✔
379	})	1✔
380	);	1✔
381
382	let _operator: Box<dyn VectorOperator> = serde_json::from_value(serialized).unwrap();	1✔
383	}
384
385	#[tokio::test]	1✔
386	async fn test_errors() {	1✔
387	// zero epsilon
388	assert!(LineSimplification {	1✔
389	params: LineSimplificationParams {	1✔
390	epsilon: Some(0.0),	1✔
391	algorithm: LineSimplificationAlgorithm::DouglasPeucker,	1✔
392	},	1✔
393	sources: MockFeatureCollectionSource::<MultiPolygon>::single(	1✔
394	MultiPolygonCollection::empty()	1✔
395	)	1✔
396	.boxed()	1✔
397	.into(),	1✔
398	}	1✔
399	.boxed()	1✔
400	.initialize(	1✔
401	WorkflowOperatorPath::initialize_root(),	1✔
402	&MockExecutionContext::test_default()	1✔
403	)	1✔
404	.await	×
405	.is_err());	1✔
406
407	// invalid epsilon
408	assert!(LineSimplification {	1✔
409	params: LineSimplificationParams {	1✔
410	epsilon: Some(f64::NAN),	1✔
411	algorithm: LineSimplificationAlgorithm::Visvalingam,	1✔
412	},	1✔
413	sources: MockFeatureCollectionSource::<MultiPolygon>::single(	1✔
414	MultiPolygonCollection::empty()	1✔
415	)	1✔
416	.boxed()	1✔
417	.into(),	1✔
418	}	1✔
419	.boxed()	1✔
420	.initialize(	1✔
421	WorkflowOperatorPath::initialize_root(),	1✔
422	&MockExecutionContext::test_default()	1✔
423	)	1✔
424	.await	×
425	.is_err());	1✔
426
427	// not lines or polygons
428	assert!(LineSimplification {	1✔
429	params: LineSimplificationParams {	1✔
430	epsilon: None,	1✔
431	algorithm: LineSimplificationAlgorithm::DouglasPeucker,	1✔
432	},	1✔
433	sources: MockFeatureCollectionSource::<MultiPoint>::single(	1✔
434	MultiPointCollection::empty()	1✔
435	)	1✔
436	.boxed()	1✔
437	.into(),	1✔
438	}	1✔
439	.boxed()	1✔
440	.initialize(	1✔
441	WorkflowOperatorPath::initialize_root(),	1✔
442	&MockExecutionContext::test_default()	1✔
443	)	1✔
444	.await	×
445	.is_err());	1✔
446	}
447
448	#[tokio::test]	1✔
449	async fn test_line_simplification() {	1✔
450	let collection = MultiLineStringCollection::from_data(	1✔
451	vec![	1✔
452	MultiLineString::new(vec![vec![	1✔
453	(0.0, 0.0).into(),	1✔
454	(5.0, 4.0).into(),	1✔
455	(11.0, 5.5).into(),	1✔
456	(17.3, 3.2).into(),	1✔
457	(27.8, 0.1).into(),	1✔
458	]])	1✔
459	.unwrap(),	1✔
460	MultiLineString::new(vec![vec![(0.0, 0.0).into(), (5.0, 4.0).into()]]).unwrap(),	1✔
461	],	1✔
462	vec![TimeInterval::new(0, 1).unwrap(); 2],	1✔
463	[("foo".to_string(), FeatureData::Float(vec![0., 1.]))]	1✔
464	.iter()	1✔
465	.cloned()	1✔
466	.collect(),	1✔
467	)	1✔
468	.unwrap();	1✔
469		1✔
470	let source = MockFeatureCollectionSource::single(collection.clone()).boxed();	1✔
471		1✔
472	let simplification = LineSimplification {	1✔
473	params: LineSimplificationParams {	1✔
474	epsilon: Some(1.0),	1✔
475	algorithm: LineSimplificationAlgorithm::DouglasPeucker,	1✔
476	},	1✔
477	sources: source.into(),	1✔
478	}	1✔
479	.boxed();	1✔
480
481	let initialized = simplification	1✔
482	.initialize(	1✔
483	WorkflowOperatorPath::initialize_root(),	1✔
484	&MockExecutionContext::test_default(),	1✔
485	)	1✔
486	.await	×
487	.unwrap();	1✔
488		1✔
489	let processor = initialized	1✔
490	.query_processor()	1✔
491	.unwrap()	1✔
492	.multi_line_string()	1✔
493	.unwrap();	1✔
494		1✔
495	let query_rectangle = VectorQueryRectangle {	1✔
496	spatial_bounds: BoundingBox2D::new((0., 0.).into(), (4., 4.).into()).unwrap(),	1✔
497	time_interval: TimeInterval::default(),	1✔
498	spatial_resolution: SpatialResolution::one(),	1✔
499	};	1✔
500		1✔
501	let query_ctx = MockQueryContext::test_default();	1✔
502
503	let stream = processor.query(query_rectangle, &query_ctx).await.unwrap();	1✔
504
505	let collections: Vec<MultiLineStringCollection> =	1✔
506	stream.map(Result::unwrap).collect().await;	1✔
507
508	assert_eq!(collections.len(), 1);	1✔
509
510	let expected = MultiLineStringCollection::from_data(	1✔
511	vec![	1✔
512	MultiLineString::new(vec![vec![	1✔
513	(0.0, 0.0).into(),	1✔
514	(5.0, 4.0).into(),	1✔
515	(11.0, 5.5).into(),	1✔
516	(27.8, 0.1).into(),	1✔
517	]])	1✔
518	.unwrap(),	1✔
519	MultiLineString::new(vec![vec![(0.0, 0.0).into(), (5.0, 4.0).into()]]).unwrap(),	1✔
520	],	1✔
521	vec![TimeInterval::new(0, 1).unwrap(); 2],	1✔
522	[("foo".to_string(), FeatureData::Float(vec![0., 1.]))]	1✔
523	.iter()	1✔
524	.cloned()	1✔
525	.collect(),	1✔
526	)	1✔
527	.unwrap();	1✔
528		1✔
529	assert_eq!(collections[0], expected);	1✔
530	}
531
532	#[tokio::test]	1✔
533	async fn test_polygon_simplification() {	1✔
534	let id: DataId = DatasetId::new().into();	1✔
535	let mut exe_ctx = MockExecutionContext::test_default();	1✔
536	exe_ctx.add_meta_data::<OgrSourceDataset, VectorResultDescriptor, VectorQueryRectangle>(	1✔
537	id.clone(),	1✔
538	Box::new(StaticMetaData {	1✔
539	loading_info: OgrSourceDataset {	1✔
540	file_name: test_data!("vector/data/germany_polygon.gpkg").into(),	1✔
541	layer_name: "test_germany".to_owned(),	1✔
542	data_type: Some(VectorDataType::MultiPolygon),	1✔
543	time: OgrSourceDatasetTimeType::None,	1✔
544	default_geometry: None,	1✔
545	columns: Some(OgrSourceColumnSpec {	1✔
546	format_specifics: None,	1✔
547	x: String::new(),	1✔
548	y: None,	1✔
549	int: vec![],	1✔
550	float: vec![],	1✔
551	text: vec![],	1✔
552	bool: vec![],	1✔
553	datetime: vec![],	1✔
554	rename: None,	1✔
555	}),	1✔
556	force_ogr_time_filter: false,	1✔
557	force_ogr_spatial_filter: false,	1✔
558	on_error: OgrSourceErrorSpec::Abort,	1✔
559	sql_query: None,	1✔
560	attribute_query: None,	1✔
561	},	1✔
562	result_descriptor: VectorResultDescriptor {	1✔
563	data_type: VectorDataType::MultiPolygon,	1✔
564	spatial_reference: SpatialReference::epsg_4326().into(),	1✔
565	columns: Default::default(),	1✔
566	time: None,	1✔
567	bbox: None,	1✔
568	},	1✔
569	phantom: Default::default(),	1✔
570	}),	1✔
571	);	1✔
572
573	let simplification = LineSimplification {	1✔
574	params: LineSimplificationParams {	1✔
575	epsilon: None,	1✔
576	algorithm: LineSimplificationAlgorithm::Visvalingam,	1✔
577	},	1✔
578	sources: OgrSource {	1✔
579	params: OgrSourceParameters {	1✔
580	data: id,	1✔
581	attribute_projection: None,	1✔
582	attribute_filters: None,	1✔
583	},	1✔
584	}	1✔
585	.boxed()	1✔
586	.into(),	1✔
587	}	1✔
588	.boxed()	1✔
589	.initialize(WorkflowOperatorPath::initialize_root(), &exe_ctx)	1✔
590	.await	×
591	.unwrap();	1✔
592		1✔
593	assert_eq!(	1✔
594	simplification.result_descriptor().data_type,	1✔
595	VectorDataType::MultiPolygon	1✔
596	);	1✔
597
598	let query_processor = simplification	1✔
599	.query_processor()	1✔
600	.unwrap()	1✔
601	.multi_polygon()	1✔
602	.unwrap();	1✔
603		1✔
604	let query_bbox = BoundingBox2D::new((-180.0, -90.0).into(), (180.00, 90.0).into()).unwrap();	1✔
605		1✔
606	let query_context = MockQueryContext::test_default();	1✔
607	let query = query_processor	1✔
608	.query(	1✔
609	VectorQueryRectangle {	1✔
610	spatial_bounds: query_bbox,	1✔
611	time_interval: Default::default(),	1✔
612	spatial_resolution: SpatialResolution::new(1., 1.).unwrap(),	1✔
613	},	1✔
614	&query_context,	1✔
615	)	1✔
616	.await	1✔
617	.unwrap();	1✔
618
619	let result: Vec<MultiPolygonCollection> = query.try_collect().await.unwrap();	3✔
620		1✔
621	assert_eq!(result.len(), 1);	1✔
622	let result = result.into_iter().next().unwrap();	1✔
623		1✔
624	assert_eq!(result.len(), 1);	1✔
625	assert_eq!(result.feature_offsets().len(), 2);	1✔
626	assert_eq!(result.polygon_offsets().len(), 23);	1✔
627	assert_eq!(result.ring_offsets().len(), 23);	1✔
628	assert_eq!(result.coordinates().len(), 98 /* was 3027 */);	1✔
629	}
630	}

geo-engine / geoengine / 5006008836

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous