1use std::{fs, path::Path};
4
5use rstar::{AABB, RTree, RTreeObject};
6
7use crate::{
8 error::{CoordinateParseError, Error},
9 store::{Area, read_data},
10};
11
12#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Address {
15 pub province: AdministrativeArea,
16 pub city: AdministrativeArea,
17 pub county: AdministrativeArea,
18}
19
20#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct AdministrativeArea {
23 pub name: String,
24 pub code: String,
25}
26
27pub struct ReverseGeocoder {
29 provinces: Layer,
30 cities: Layer,
31 counties: Layer,
32}
33
34impl ReverseGeocoder {
35 pub fn embedded() -> Result<Self, Error> {
38 Self::from_bytes(include_bytes!("../cn_admin.bin"))
39 }
40
41 pub fn open(path: impl AsRef<Path>) -> Result<Self, Error> {
43 Self::from_bytes(&fs::read(path)?)
44 }
45
46 pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
48 let data = read_data(bytes)?;
49 Ok(Self {
50 provinces: Layer::new(data.provinces),
51 cities: Layer::new(data.cities),
52 counties: Layer::new(data.counties),
53 })
54 }
55
56 pub fn reverse_geocode(&self, latitude: f64, longitude: f64) -> Option<Address> {
59 if !(-90.0..=90.0).contains(&latitude) || !(-180.0..=180.0).contains(&longitude) {
60 return None;
61 }
62 self.lookup([longitude, latitude])
63 }
64
65 pub fn reverse_geocode_degree_minutes(
71 &self,
72 latitude: &str,
73 longitude: &str,
74 ) -> Result<Option<Address>, CoordinateParseError> {
75 let latitude = parse_coordinate(latitude, true)?;
76 let longitude = parse_coordinate(longitude, false)?;
77 let point = [longitude, latitude];
78 Ok(self.lookup(point))
79 }
80
81 fn lookup(&self, point: [f64; 2]) -> Option<Address> {
82 Some(Address {
83 province: self.provinces.find(point)?.public(),
84 city: self.cities.find(point)?.public(),
85 county: self.counties.find(point)?.public(),
86 })
87 }
88}
89
90fn parse_coordinate(token: &str, latitude: bool) -> Result<f64, CoordinateParseError> {
91 let hemisphere = token
92 .chars()
93 .last()
94 .ok_or(CoordinateParseError("empty coordinate"))?
95 .to_ascii_uppercase();
96 let valid_direction = if latitude {
97 matches!(hemisphere, 'N' | 'S')
98 } else {
99 matches!(hemisphere, 'E' | 'W')
100 };
101 if !valid_direction {
102 return Err(CoordinateParseError(if latitude {
103 "latitude must end in N or S"
104 } else {
105 "longitude must end in E or W"
106 }));
107 }
108 let value = token[..token.len() - hemisphere.len_utf8()].trim_end_matches(['\'', '′', '’']);
109 let (degrees, minutes) = value.split_once('°').ok_or(CoordinateParseError(
110 "coordinate is missing the degree symbol",
111 ))?;
112 let degrees = degrees
113 .parse::<u16>()
114 .map_err(|_| CoordinateParseError("invalid degrees"))?;
115 let minutes = minutes
116 .parse::<f64>()
117 .map_err(|_| CoordinateParseError("invalid minutes"))?;
118 let maximum = if latitude { 90 } else { 180 };
119 if !(0.0..60.0).contains(&minutes) || degrees > maximum || (degrees == maximum && minutes > 0.0)
120 {
121 return Err(CoordinateParseError("coordinate is out of range"));
122 }
123 let decimal = f64::from(degrees) + minutes / 60.0;
124 Ok(if matches!(hemisphere, 'S' | 'W') {
125 -decimal
126 } else {
127 decimal
128 })
129}
130
131struct IndexedArea {
132 index: usize,
133 bbox: AABB<[f64; 2]>,
134}
135impl RTreeObject for IndexedArea {
136 type Envelope = AABB<[f64; 2]>;
137 fn envelope(&self) -> Self::Envelope {
138 self.bbox
139 }
140}
141struct Layer {
142 areas: Vec<Area>,
143 index: RTree<IndexedArea>,
144}
145impl Layer {
146 fn new(areas: Vec<Area>) -> Self {
147 let index = RTree::bulk_load(
148 areas
149 .iter()
150 .enumerate()
151 .map(|(index, area)| IndexedArea {
152 index,
153 bbox: AABB::from_corners(
154 [area.bbox[0], area.bbox[1]],
155 [area.bbox[2], area.bbox[3]],
156 ),
157 })
158 .collect(),
159 );
160 Self { areas, index }
161 }
162 fn find(&self, point: [f64; 2]) -> Option<&Area> {
163 self.index
164 .locate_in_envelope_intersecting(AABB::from_point(point))
165 .find_map(|item| {
166 self.areas
167 .get(item.index)
168 .filter(|area| contains(area, point))
169 })
170 }
171}
172
173fn contains(area: &Area, point: [f64; 2]) -> bool {
174 area.polygons.iter().any(|polygon| {
175 polygon
176 .first()
177 .is_some_and(|outer| point_in_ring(point, outer))
178 && polygon
179 .iter()
180 .skip(1)
181 .all(|hole| !point_in_ring(point, hole))
182 })
183}
184fn point_in_ring(point: [f64; 2], ring: &[[f64; 2]]) -> bool {
185 if ring.len() < 3 {
186 return false;
187 }
188 let mut inside = false;
189 for index in 0..ring.len() {
190 let (a, b) = (ring[index], ring[(index + 1) % ring.len()]);
191 if on_segment(point, a, b) {
192 return true;
193 }
194 if (a[1] > point[1]) != (b[1] > point[1])
195 && point[0] < (b[0] - a[0]) * (point[1] - a[1]) / (b[1] - a[1]) + a[0]
196 {
197 inside = !inside;
198 }
199 }
200 inside
201}
202fn on_segment(p: [f64; 2], a: [f64; 2], b: [f64; 2]) -> bool {
203 const EPSILON: f64 = 1e-10;
204 let cross = (p[1] - a[1]) * (b[0] - a[0]) - (p[0] - a[0]) * (b[1] - a[1]);
205 cross.abs() <= EPSILON
206 && p[0] >= a[0].min(b[0]) - EPSILON
207 && p[0] <= a[0].max(b[0]) + EPSILON
208 && p[1] >= a[1].min(b[1]) - EPSILON
209 && p[1] <= a[1].max(b[1]) + EPSILON
210}
211
212#[cfg(test)]
213mod tests {
214 use super::*;
215 #[test]
216 fn embedded_data_resolves_tiananmen() {
217 let result = ReverseGeocoder::embedded()
218 .unwrap()
219 .reverse_geocode(39.9087, 116.3975)
220 .unwrap();
221 assert_eq!(result.county.code, "110101");
222 }
223
224 #[test]
225 fn degree_minute_coordinates_resolve_and_outside_china_returns_none() {
226 let geocoder = ReverseGeocoder::embedded().unwrap();
227 let jilin = geocoder
228 .reverse_geocode_degree_minutes("42°16.9552000'N", "126°36.5127000'E")
229 .unwrap()
230 .unwrap();
231 let south_china = geocoder
232 .reverse_geocode_degree_minutes("22°09.8935000'N", "113°33.4033000'E")
233 .unwrap()
234 .unwrap();
235 assert_eq!(jilin.province.name, "吉林省");
236 assert_eq!(jilin.city.code, "220600");
237 assert_eq!(jilin.county.code, "220622");
238 assert_eq!(south_china.province.code, "820000");
239 assert_eq!(south_china.county.name, "澳门特别行政区");
240 assert_eq!(geocoder.reverse_geocode(40.7128, -74.0060), None);
241 assert_eq!(
242 geocoder.reverse_geocode_degree_minutes("40°42.768'N", "74°00.36'W"),
243 Ok(None)
244 );
245 }
246
247 #[test]
248 fn invalid_degree_minute_coordinates_return_an_error() {
249 let geocoder = ReverseGeocoder::embedded().unwrap();
250 assert!(
251 geocoder
252 .reverse_geocode_degree_minutes("42°61'N", "126°36'E")
253 .is_err()
254 );
255 }
256}