map-tile-toolkit 0.1.0

Clip integer polylines into per-tile pieces on a simple tile grid
Documentation 
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

//! Low-level polyline clipping against a single tile box (the engine behind the `Grid` slicer core).
//!
//! Clipping keeps the **original** vertices — never cutting new ones at the tile edge. Every
//! segment that touches the box contributes both of its endpoints, so a line shows up in every tile
//! it passes through, even ones it merely crosses with no vertex inside. A stretch that leaves the
//! box and re-enters splits into separate pieces only where a vertex is *dropped*: a single-segment
//! excursion out and back keeps both its (outside) endpoints, so it stays one connected piece.

use geo_types::Coord;

use crate::TileError;
use crate::vertex::Vertex;

/// Is coordinate `c` inside the closed rectangle `[min, max]`?
fn inside(c: Coord<i32>, min: Coord<i32>, max: Coord<i32>) -> bool {
    c.x >= min.x && c.x <= max.x && c.y >= min.y && c.y <= max.y
}

/// Does segment `a`–`b` touch the closed integer rectangle `[min, max]`?
///
/// Integer-only (no division, no floats): reject when the segment's bounding box is disjoint from
/// the box, accept when an endpoint is inside, otherwise test whether the box straddles the
/// segment's supporting line via i128 cross products (so full `i32` coordinates cannot overflow).
pub(crate) fn segment_intersects(
    a: Coord<i32>,
    b: Coord<i32>,
    min: Coord<i32>,
    max: Coord<i32>,
) -> bool {
    // Quick reject: the segment's bounding box is disjoint from the tile box.
    if a.x.min(b.x) > max.x || a.x.max(b.x) < min.x || a.y.min(b.y) > max.y || a.y.max(b.y) < min.y
    {
        return false;
    }
    // Quick accept: an endpoint lies inside the (closed) box.
    if inside(a, min, max) || inside(b, min, max) {
        return true;
    }
    // Both endpoints outside and the bounding boxes overlap: the segment meets the box iff its
    // corners are not all strictly on one side of the segment's supporting line.
    let (dx, dy) = (
        i128::from(b.x) - i128::from(a.x),
        i128::from(b.y) - i128::from(a.y),
    );
    let side = |x: i32, y: i32| {
        dx * (i128::from(y) - i128::from(a.y)) - dy * (i128::from(x) - i128::from(a.x))
    };
    let s = [
        side(min.x, min.y),
        side(max.x, min.y),
        side(min.x, max.y),
        side(max.x, max.y),
    ];
    !(s.iter().all(|&v| v > 0) || s.iter().all(|&v| v < 0))
}

/// Re-express vertex `v` in the tile-local frame whose `[0, 0]` corner is `origin`: its position
/// becomes `position − origin`, its payload unchanged. [`TileError::Overflow`] if the offset leaves the
/// `i32` range — possible only when a far crossing-segment endpoint lies more than a full `i32` span
/// from the tile.
pub(crate) fn to_local<V: Vertex>(v: V, origin: Coord<i32>) -> Result<V, TileError> {
    let p = v.position();
    Ok(v.with_position(Coord {
        x: p.x.checked_sub(origin.x).ok_or(TileError::Overflow)?,
        y: p.y.checked_sub(origin.y).ok_or(TileError::Overflow)?,
    }))
}