wilayah 0.5.1

Location lookup for Indonesian villages by GPS coordinates or name
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

//! Point-in-polygon algorithms and vertex serialization.

/// Epsilon tolerance for floating-point comparisons in PIP calculations.
const PIP_EPSILON: f64 = 1e-10;

/// Compute the axis-aligned bounding box of a polygon ring.
///
/// Returns `(min_lat, max_lat, min_lon, max_lon)`.
pub fn bbox(ring: &[(f64, f64)]) -> (f64, f64, f64, f64) {
    let mut min_lat = f64::MAX;
    let mut max_lat = f64::MIN;
    let mut min_lon = f64::MAX;
    let mut max_lon = f64::MIN;
    for &(lat, lon) in ring {
        min_lat = min_lat.min(lat);
        max_lat = max_lat.max(lat);
        min_lon = min_lon.min(lon);
        max_lon = max_lon.max(lon);
    }
    (min_lat, max_lat, min_lon, max_lon)
}

/// Result of a point-in-polygon test.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PipResult {
    /// The point is inside the polygon.
    Inside,
    /// The point is outside the polygon.
    Outside,
    /// The point lies exactly on a polygon edge or vertex.
    OnBoundary,
}

fn point_on_segment(px: f64, py: f64, x1: f64, y1: f64, x2: f64, y2: f64) -> bool {
    let cross = (py - y1) * (x2 - x1) - (px - x1) * (y2 - y1);
    if cross.abs() > PIP_EPSILON {
        return false;
    }
    let (min_x, max_x) = if x1 < x2 { (x1, x2) } else { (x2, x1) };
    let (min_y, max_y) = if y1 < y2 { (y1, y2) } else { (y2, y1) };
    px >= min_x - PIP_EPSILON
        && px <= max_x + PIP_EPSILON
        && py >= min_y - PIP_EPSILON
        && py <= max_y + PIP_EPSILON
}

fn ray_cast(px: f64, py: f64, ring: &[(f64, f64)]) -> bool {
    let mut inside = false;
    let n = ring.len();
    for i in 0..n {
        let (x1, y1) = ring[i];
        let (x2, y2) = ring[(i + 1) % n];
        if (y1 > py) != (y2 > py) && px < (x2 - x1) * (py - y1) / (y2 - y1) + x1 {
            inside = !inside;
        }
    }
    inside
}

/// Test whether a point lies inside, outside, or on the boundary of a polygon ring.
///
/// The ring must be closed (first point equals last point). Uses the ray-casting
/// algorithm with the "upward exclusive, downward inclusive" rule to handle vertex
/// edge cases. A separate on-boundary check catches points that lie exactly on an
/// edge or vertex.
pub fn point_in_ring(px: f64, py: f64, ring: &[(f64, f64)]) -> PipResult {
    let n = ring.len();
    if n < 3 {
        return PipResult::Outside;
    }
    for i in 0..n {
        let (x1, y1) = ring[i];
        let (x2, y2) = ring[(i + 1) % n];
        if point_on_segment(px, py, x1, y1, x2, y2) {
            return PipResult::OnBoundary;
        }
    }
    if ray_cast(px, py, ring) {
        PipResult::Inside
    } else {
        PipResult::Outside
    }
}

/// Test whether a point lies inside a polygon with optional interior rings (holes).
///
/// Returns `true` if the point is inside the exterior ring and outside all interior
/// rings. A point on the boundary of the exterior ring is considered inside; a point
/// on the boundary of an interior ring is considered outside (excluded by the hole).
pub fn point_in_polygon(
    px: f64,
    py: f64,
    exterior: &[(f64, f64)],
    interiors: &[&[(f64, f64)]],
) -> bool {
    match point_in_ring(px, py, exterior) {
        PipResult::Outside => return false,
        PipResult::OnBoundary => return true,
        PipResult::Inside => {}
    }
    for hole in interiors {
        match point_in_ring(px, py, hole) {
            PipResult::Outside => {}
            PipResult::OnBoundary | PipResult::Inside => return false,
        }
    }
    true
}

/// Serialize polygon ring vertices as compact binary (little-endian f64 pairs).
///
/// Each vertex is stored as `[lat_bytes, lon_bytes]` — 16 bytes per point.
/// The ring is stored without repeating the closing vertex.
pub fn serialize_vertices(ring: &[(f64, f64)]) -> Vec<u8> {
    let mut buf = Vec::with_capacity(ring.len() * 16);
    for &(lat, lon) in ring {
        buf.extend_from_slice(&lat.to_le_bytes());
        buf.extend_from_slice(&lon.to_le_bytes());
    }
    buf
}

/// Deserialize polygon ring vertices from compact binary (little-endian f64 pairs).
///
/// Each vertex is 16 bytes: `[lat, lon]`. The number of vertices is `blob.len() / 16`.
pub fn deserialize_vertices(blob: &[u8]) -> Vec<(f64, f64)> {
    let n = blob.len() / 16;
    let mut ring = Vec::with_capacity(n);
    for i in 0..n {
        let lat = f64::from_le_bytes(blob[i * 16..i * 16 + 8].try_into().unwrap());
        let lon = f64::from_le_bytes(blob[i * 16 + 8..i * 16 + 16].try_into().unwrap());
        ring.push((lat, lon));
    }
    ring
}