mvt/
encoder.rs

1// encoder.rs
2//
3// Copyright (c) 2019-2024  Minnesota Department of Transportation
4//
5//! Encoder for Mapbox Vector Tile (MVT) geometry.
6//!
7use crate::error::{Error, Result};
8use pointy::{BBox, Float, Pt, Seg, Transform};
9
10/// Path commands
11#[derive(Copy, Clone, Debug, Eq, PartialEq)]
12enum Command {
13    /// Move to new position
14    MoveTo = 1,
15
16    /// Line to new position
17    LineTo = 2,
18
19    /// Close current path
20    ClosePath = 7,
21}
22
23/// Integer command
24#[derive(Copy, Clone, Debug, Eq, PartialEq)]
25struct CommandInt {
26    /// Path command
27    id: Command,
28
29    /// Command count
30    count: u32,
31}
32
33/// Integer parameter
34#[derive(Copy, Clone, Debug, Eq, PartialEq)]
35struct ParamInt {
36    /// Parameter value
37    value: i32,
38}
39
40/// Geometry types for [Features](struct.Feature.html).
41#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
42pub enum GeomType {
43    /// Point or Multipoint
44    #[default]
45    Point,
46
47    /// Linestring or Multilinestring
48    Linestring,
49
50    /// Polygon or Multipolygon
51    Polygon,
52}
53
54/// Encoder for [Feature](struct.Feature.html) geometry.
55///
56/// This can consist of Point, Linestring or Polygon data.
57///
58/// # Example
59/// ```
60/// # use mvt::{Error, GeomEncoder, GeomType};
61/// # use pointy::Transform;
62/// # fn main() -> Result<(), Error> {
63/// let geom_data = GeomEncoder::new(GeomType::Point)
64///     .point(0.0, 0.0)?
65///     .point(10.0, 0.0)?
66///     .encode()?;
67/// # Ok(()) }
68/// ```
69#[derive(Default)]
70pub struct GeomEncoder<F>
71where
72    F: Float,
73{
74    /// Geometry type
75    geom_tp: GeomType,
76
77    /// X,Y position at end of linestring/polygon geometry
78    xy_end: Option<Pt<F>>,
79
80    /// Transform to MVT coordinates
81    transform: Transform<F>,
82
83    /// Bounding box
84    bbox: BBox<F>,
85
86    /// Minimum X value
87    x_min: i32,
88
89    /// Maximum X value
90    x_max: i32,
91
92    /// Minimum Y value
93    y_min: i32,
94
95    /// Maximum Y value
96    y_max: i32,
97
98    /// Previous tile point
99    pt0: Option<(i32, i32)>,
100
101    /// Current tile point
102    pt1: Option<(i32, i32)>,
103
104    /// Command offset
105    cmd_offset: usize,
106
107    /// Count of geometry data
108    count: u32,
109
110    /// Encoded geometry data
111    data: Vec<u32>,
112}
113
114/// Validated geometry data for [Feature](struct.Feature.html)s.
115///
116/// Use [GeomEncoder](struct.GeomEncoder.html) to encode.
117///
118/// # Example
119/// ```
120/// # use mvt::{Error, GeomEncoder, GeomType};
121/// # use pointy::Transform;
122/// # fn main() -> Result<(), Error> {
123/// let geom_data = GeomEncoder::new(GeomType::Point)
124///     .point(0.0, 0.0)?
125///     .point(10.0, 0.0)?
126///     .encode()?;
127/// # Ok(()) }
128/// ```
129pub struct GeomData {
130    /// Geometry type
131    geom_tp: GeomType,
132
133    /// Encoded geometry data
134    data: Vec<u32>,
135}
136
137impl CommandInt {
138    /// Create a new integer command
139    fn new(id: Command, count: u32) -> Self {
140        debug_assert!(count <= 0x1FFF_FFFF);
141        CommandInt { id, count }
142    }
143
144    /// Encode command
145    fn encode(&self) -> u32 {
146        ((self.id as u32) & 0x7) | (self.count << 3)
147    }
148
149    /// Decode command
150    fn decode(code: u32) -> Self {
151        let id = match code & 0x7 {
152            1 => Command::MoveTo,
153            2 => Command::LineTo,
154            7 => Command::ClosePath,
155            _ => panic!("Invalid code: {code}"),
156        };
157        let count = code >> 3;
158        CommandInt { id, count }
159    }
160}
161
162impl ParamInt {
163    /// Create a new integer parameter
164    fn new(value: i32) -> Self {
165        ParamInt { value }
166    }
167
168    /// Encode the parameter
169    fn encode(&self) -> u32 {
170        ((self.value << 1) ^ (self.value >> 31)) as u32
171    }
172}
173
174impl<F> GeomEncoder<F>
175where
176    F: Float,
177{
178    /// Create a new geometry encoder.
179    ///
180    /// * `geom_tp` Geometry type.
181    pub fn new(geom_tp: GeomType) -> Self {
182        GeomEncoder {
183            geom_tp,
184            x_min: i32::MIN,
185            x_max: i32::MAX,
186            y_min: i32::MIN,
187            y_max: i32::MAX,
188            ..Default::default()
189        }
190    }
191
192    /// Adjust min/max values
193    fn adjust_minmax(mut self) -> Self {
194        if self.bbox != BBox::default() {
195            let p = self.transform * (self.bbox.x_min(), self.bbox.y_min());
196            let x0 = p.x.round().to_i32().unwrap_or(i32::MIN);
197            let y0 = p.y.round().to_i32().unwrap_or(i32::MIN);
198            let p = self.transform * (self.bbox.x_max(), self.bbox.y_max());
199            let x1 = p.x.round().to_i32().unwrap_or(i32::MAX);
200            let y1 = p.y.round().to_i32().unwrap_or(i32::MAX);
201            self.x_min = x0.min(x1);
202            self.y_min = y0.min(y1);
203            self.x_max = x0.max(x1);
204            self.y_max = y0.max(y1);
205        }
206        self
207    }
208
209    /// Add a bounding box
210    pub fn bbox(mut self, bbox: BBox<F>) -> Self {
211        self.bbox = bbox;
212        self.adjust_minmax()
213    }
214
215    /// Add a transform
216    pub fn transform(mut self, transform: Transform<F>) -> Self {
217        self.transform = transform;
218        self.adjust_minmax()
219    }
220
221    /// Push a Command
222    fn push_command(&mut self, cmd: Command) {
223        log::trace!("push_command: {cmd:?}");
224        self.cmd_offset = self.data.len();
225        self.data.push(CommandInt::new(cmd, 1).encode());
226    }
227
228    /// Set count of the most recent Command.
229    fn set_command_count(&mut self, count: u32) {
230        let off = self.cmd_offset;
231        let mut cmd = CommandInt::decode(self.data[off]);
232        cmd.count = count;
233        self.data[off] = cmd.encode();
234    }
235
236    /// Push one point with relative coörindates.
237    fn push_point(&mut self, x: i32, y: i32) {
238        log::trace!("push_point: {x},{y}");
239        self.pt0 = self.pt1;
240        let (px, py) = self.pt0.unwrap_or((0, 0));
241        self.data.push(ParamInt::new(x.saturating_sub(px)).encode());
242        self.data.push(ParamInt::new(y.saturating_sub(py)).encode());
243        self.pt1 = Some((x, y));
244        self.count += 1;
245    }
246
247    /// Pop most recent point.
248    fn pop_point(&mut self) {
249        log::trace!("pop_point");
250        self.data.pop();
251        self.data.pop();
252        self.pt1 = self.pt0;
253        self.count -= 1;
254    }
255
256    /// Add a point, taking ownership (for method chaining).
257    pub fn point(mut self, x: F, y: F) -> Result<Self> {
258        self.add_point(x, y)?;
259        Ok(self)
260    }
261
262    /// Add a point.
263    pub fn add_point(&mut self, x: F, y: F) -> Result<()> {
264        self.add_boundary_points(x, y)?;
265        self.add_tile_point(x, y)
266    }
267
268    /// Add one or two boundary points (if needed).
269    fn add_boundary_points(&mut self, x: F, y: F) -> Result<()> {
270        if let Some(pxy) = self.xy_end {
271            let xy = Pt::from((x, y));
272            let seg = Seg::new(pxy, xy);
273            if let Some(seg) = seg.clip(self.bbox) {
274                if seg.p0 != pxy {
275                    self.add_tile_point(seg.p0.x, seg.p0.y)?;
276                }
277                if seg.p1 != xy {
278                    self.add_tile_point(seg.p1.x, seg.p1.y)?;
279                }
280            }
281        }
282        match self.geom_tp {
283            GeomType::Linestring | GeomType::Polygon => {
284                self.xy_end = Some(Pt::from((x, y)));
285            }
286            _ => (),
287        }
288        Ok(())
289    }
290
291    /// Add a tile point.
292    fn add_tile_point(&mut self, x: F, y: F) -> Result<()> {
293        let pt = self.make_point(x, y)?;
294        if let Some((px, py)) = self.pt1 {
295            if pt.0 == px && pt.1 == py {
296                if self.count == 0 {
297                    // If the first point of a line in a multilinestring (or multipolygon) is the same as the last of the previous line,
298                    // we skip the MoveTo command and increase the count so the next point correctly gets a LineTo.
299                    self.count += 1;
300                } else {
301                    // Redundant points other than the first are unexpected, and entirely skipped.
302                    log::trace!("redundant point: {px},{py}");
303                }
304                return Ok(());
305            }
306        }
307        match self.geom_tp {
308            GeomType::Point => {
309                if self.count == 0 {
310                    self.push_command(Command::MoveTo);
311                }
312            }
313            GeomType::Linestring => match self.count {
314                0 => self.push_command(Command::MoveTo),
315                1 => self.push_command(Command::LineTo),
316                _ => (),
317            },
318            GeomType::Polygon => {
319                match self.count {
320                    0 => self.push_command(Command::MoveTo),
321                    1 => self.push_command(Command::LineTo),
322                    _ => (),
323                }
324                if self.count >= 2 && self.should_simplify_point(pt.0, pt.1) {
325                    self.pop_point();
326                }
327            }
328        }
329        self.push_point(pt.0, pt.1);
330        Ok(())
331    }
332
333    /// Make point with tile coörindates.
334    fn make_point(&self, x: F, y: F) -> Result<(i32, i32)> {
335        let p = self.transform * (x, y);
336        let mut x = p.x.round().to_i32().ok_or(Error::InvalidValue())?;
337        let mut y = p.y.round().to_i32().ok_or(Error::InvalidValue())?;
338        x = x.clamp(self.x_min, self.x_max);
339        y = y.clamp(self.y_min, self.y_max);
340        Ok((x, y))
341    }
342
343    /// Check if point should be simplified.
344    fn should_simplify_point(&self, x: i32, y: i32) -> bool {
345        if let (Some((p0x, p0y)), Some((p1x, p1y))) = (self.pt0, self.pt1) {
346            if p0x == p1x && p1x == x {
347                return (p0y < p1y && p1y < y) || (p0y > p1y && p1y > y);
348            }
349            if p0y == p1y && p1y == y {
350                return (p0x < p1x && p1x < x) || (p0x > p1x && p1x > x);
351            }
352        }
353        false
354    }
355
356    /// Complete the current geometry (for multilinestring / multipolygon).
357    pub fn complete_geom(&mut self) -> Result<()> {
358        // FIXME: return Error::InvalidGeometry
359        //        if "MUST" rules in the spec are violated
360        match self.geom_tp {
361            GeomType::Point => {
362                self.set_command_count(self.count);
363                // early return skips geometry reset
364                return Ok(());
365            }
366            GeomType::Linestring => {
367                if self.count > 1 {
368                    self.set_command_count(self.count - 1);
369                }
370            }
371            GeomType::Polygon => {
372                if self.count > 1 {
373                    self.set_command_count(self.count - 1);
374                    self.push_command(Command::ClosePath);
375                }
376            }
377        }
378        // reset linestring / polygon geometry state
379        self.count = 0;
380        self.xy_end = None;
381        self.pt0 = None;
382        Ok(())
383    }
384
385    /// Complete the current geometry (for multilinestring / multipolygon).
386    pub fn complete(mut self) -> Result<Self> {
387        self.complete_geom()?;
388        Ok(self)
389    }
390
391    /// Encode the geometry data, consuming the encoder.
392    pub fn encode(mut self) -> Result<GeomData> {
393        // FIXME: return Error::InvalidGeometry
394        //        if "MUST" rules in the spec are violated
395        self = self.complete()?;
396        Ok(GeomData::new(self.geom_tp, self.data))
397    }
398}
399
400impl GeomData {
401    /// Create new geometry data.
402    ///
403    /// * `geom_tp` Geometry type.
404    /// * `data` Validated geometry.
405    fn new(geom_tp: GeomType, data: Vec<u32>) -> Self {
406        GeomData { geom_tp, data }
407    }
408
409    /// Get the geometry type
410    pub(crate) fn geom_type(&self) -> GeomType {
411        self.geom_tp
412    }
413
414    /// Check if data is empty
415    pub fn is_empty(&self) -> bool {
416        self.data.is_empty()
417    }
418
419    /// Get length of data
420    pub fn len(&self) -> usize {
421        self.data.len()
422    }
423
424    /// Get the geometry data
425    pub(crate) fn into_vec(self) -> Vec<u32> {
426        self.data
427    }
428}
429
430#[cfg(test)]
431mod test {
432    use super::*;
433
434    // Examples from MVT spec:
435    #[test]
436    fn test_point() {
437        let v = GeomEncoder::new(GeomType::Point)
438            .point(25.0, 17.0)
439            .unwrap()
440            .encode()
441            .unwrap()
442            .into_vec();
443        assert_eq!(v, vec!(9, 50, 34));
444    }
445
446    #[test]
447    fn test_multipoint() {
448        let v = GeomEncoder::new(GeomType::Point)
449            .point(5.0, 7.0)
450            .unwrap()
451            .point(3.0, 2.0)
452            .unwrap()
453            .encode()
454            .unwrap()
455            .into_vec();
456        assert_eq!(v, vec!(17, 10, 14, 3, 9));
457    }
458
459    #[test]
460    fn test_linestring() {
461        let v = GeomEncoder::new(GeomType::Linestring)
462            .point(2.0, 2.0)
463            .unwrap()
464            .point(2.0, 10.0)
465            .unwrap()
466            .point(10.0, 10.0)
467            .unwrap()
468            .encode()
469            .unwrap()
470            .into_vec();
471        assert_eq!(v, vec!(9, 4, 4, 18, 0, 16, 16, 0));
472    }
473
474    #[test]
475    fn test_multilinestring() {
476        let v = GeomEncoder::new(GeomType::Linestring)
477            .point(2.0, 2.0)
478            .unwrap()
479            .point(2.0, 10.0)
480            .unwrap()
481            .point(10.0, 10.0)
482            .unwrap()
483            .complete()
484            .unwrap()
485            .point(1.0, 1.0)
486            .unwrap()
487            .point(3.0, 5.0)
488            .unwrap()
489            .encode()
490            .unwrap()
491            .into_vec();
492        assert_eq!(v, vec!(9, 4, 4, 18, 0, 16, 16, 0, 9, 17, 17, 10, 4, 8));
493    }
494
495    #[test]
496    fn test_multilinestring_with_redundant_points() {
497        let v = GeomEncoder::new(GeomType::Linestring)
498            .point(2.0, 2.0)
499            .unwrap()
500            .point(2.0, 2.0)
501            .unwrap()
502            .point(10.0, 10.0)
503            .unwrap()
504            .complete()
505            .unwrap()
506            .point(10.0, 10.0)
507            .unwrap()
508            .point(13.0, 15.0)
509            .unwrap()
510            .point(10.0, 10.0)
511            .unwrap()
512            .complete()
513            .unwrap()
514            .point(2.0, 2.0)
515            .unwrap()
516            .point(10.0, 10.0)
517            .unwrap()
518            .encode()
519            .unwrap()
520            .into_vec();
521        assert_eq!(
522            v,
523            vec!(9, 4, 4, 10, 16, 16, 18, 6, 10, 5, 9, 9, 15, 15, 10, 16, 16)
524        );
525    }
526
527    #[test]
528    fn test_polygon() {
529        let v = GeomEncoder::new(GeomType::Polygon)
530            .point(3.0, 6.0)
531            .unwrap()
532            .point(8.0, 12.0)
533            .unwrap()
534            .point(20.0, 34.0)
535            .unwrap()
536            .encode()
537            .unwrap()
538            .into_vec();
539        assert_eq!(v, vec!(9, 6, 12, 18, 10, 12, 24, 44, 15));
540    }
541
542    #[test]
543    fn test_multipolygon() {
544        let v = GeomEncoder::new(GeomType::Polygon)
545            // positive area => exterior ring
546            .point(0.0, 0.0)
547            .unwrap()
548            .point(10.0, 0.0)
549            .unwrap()
550            .point(10.0, 10.0)
551            .unwrap()
552            .point(0.0, 10.0)
553            .unwrap()
554            .complete()
555            .unwrap()
556            // positive area => exterior ring
557            .point(11.0, 11.0)
558            .unwrap()
559            .point(20.0, 11.0)
560            .unwrap()
561            .point(20.0, 20.0)
562            .unwrap()
563            .point(11.0, 20.0)
564            .unwrap()
565            .complete()
566            .unwrap()
567            // negative area => interior ring
568            .point(13.0, 13.0)
569            .unwrap()
570            .point(13.0, 17.0)
571            .unwrap()
572            .point(17.0, 17.0)
573            .unwrap()
574            .point(17.0, 13.0)
575            .unwrap()
576            .encode()
577            .unwrap()
578            .into_vec();
579        assert_eq!(
580            v,
581            vec!(
582                9, 0, 0, 26, 20, 0, 0, 20, 19, 0, 15, 9, 22, 2, 26, 18, 0, 0,
583                18, 17, 0, 15, 9, 4, 13, 26, 0, 8, 8, 0, 0, 7, 15
584            )
585        );
586    }
587}
mvt/encoder.rs

mvt/
encoder.rs
