mvt/
encoder.rs

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

mvt/
encoder.rs
