use super::{attr_f64, attr_i32, child, coverage, BakedRoad, Warning};
use crate::coords::Point;
use crate::junction::{
CrossPath, CrossPathEnd, Crossing, CrossingSection, ElevationGrid, GridRow, JunctionArea,
JunctionGroup, JunctionGroupKind,
};
use crate::network::Lane;
use crate::network::LaneId;
use crate::road::{Road, RoadSection, Transition};
use std::collections::HashMap;
const GAP_TOLERANCE: f32 = 0.1;
pub(super) fn place(
root: roxmltree::Node,
roads: &[(roxmltree::Node, BakedRoad)],
) -> (Vec<JunctionArea>, Vec<Warning>) {
let road = |id: &str| roads.iter().map(|(_, r)| &r.road).find(|r| r.od_id == id);
let (mut out, mut warnings) = (Vec::new(), Vec::new());
for junction in root.children().filter(|n| n.has_tag_name("junction")) {
let od_id = junction.attribute("id").unwrap_or_default().to_string();
let boundary = child(junction, "boundary");
let grid = child(junction, "elevationGrid").and_then(|g| {
let placed = grid(junction, g);
if placed.is_none() {
warnings.push(Warning::ElevationGridDropped {
junction_id: od_id.clone(),
});
}
placed
});
if boundary.is_none() && grid.is_none() {
continue;
}
let ring = boundary.map_or_else(Vec::new, |b| ring(&od_id, b, &road, &mut warnings));
out.push(JunctionArea {
od_id,
boundary: ring,
grid,
});
}
(out, warnings)
}
pub(super) fn groups(root: roxmltree::Node) -> (Vec<JunctionGroup>, Vec<Warning>) {
let junctions: Vec<&str> = root
.children()
.filter(|n| n.has_tag_name("junction"))
.filter_map(|n| n.attribute("id"))
.collect();
let (mut out, mut warnings) = (Vec::new(), Vec::new());
for node in root.children().filter(|n| n.has_tag_name("junctionGroup")) {
let text = |name| node.attribute(name).unwrap_or_default().to_string();
let od_id = text("id");
let kind = match node.attribute("type") {
Some("roundabout") => JunctionGroupKind::Roundabout,
Some("complexJunction") => JunctionGroupKind::ComplexJunction,
Some("highwayInterchange") => JunctionGroupKind::HighwayInterchange,
Some("unknown") => JunctionGroupKind::Unknown,
other => {
warnings.push(Warning::UnknownJunctionGroupType {
group_id: od_id.clone(),
kind: other.unwrap_or_default().to_string(),
});
JunctionGroupKind::Unknown
}
};
let mut members = Vec::new();
for reference in node
.children()
.filter(|n| n.has_tag_name("junctionReference"))
{
let junction = reference.attribute("junction").unwrap_or_default();
if members.iter().any(|m| m == junction) {
continue;
}
if junctions.contains(&junction) {
members.push(junction.to_string());
} else {
warnings.push(Warning::JunctionReferenceDropped {
group_id: od_id.clone(),
junction_id: junction.to_string(),
});
}
}
out.push(JunctionGroup {
od_id,
name: text("name"),
kind,
junctions: members,
});
}
(out, warnings)
}
pub(super) fn cross_paths(
root: roxmltree::Node,
roads: &[(roxmltree::Node, BakedRoad)],
) -> (
Vec<CrossPath>,
Vec<super::CrossPathProvenance>,
Vec<Warning>,
) {
let road = |id: Option<&str>| {
roads
.iter()
.map(|(_, r)| &r.road)
.find(|r| Some(r.od_id.as_str()) == id)
};
let (mut out, mut provenance, mut warnings) = (Vec::new(), Vec::new(), Vec::new());
for junction in root.children().filter(|n| n.has_tag_name("junction")) {
let junction_id = junction.attribute("id").unwrap_or_default();
for node in junction.children().filter(|n| n.has_tag_name("crossPath")) {
let crossing_id = node.attribute("crossingRoad");
let crossing = road(crossing_id);
let end = |at: &str, link: Option<roxmltree::Node>, last: bool| {
let at_id = node.attribute(at);
let crossing = crossing.ok_or(crossing_id.unwrap_or_default())?;
let at = road(at_id).ok_or(at_id.unwrap_or_default())?;
let link = link.ok_or(at_id.unwrap_or_default())?;
let s = attr_f64(link, "s")
.filter(|s| at.on_road(*s))
.ok_or(at_id.unwrap_or_default())?;
let lane = |section: &RoadSection, name: &str| -> Option<LaneId> {
let od_id = attr_i32(link, name)?;
section
.lanes
.iter()
.find(|(id, _)| *id == od_id)
.map(|&(_, l)| l)
};
let mut permanent = crossing
.sections
.iter()
.filter(|s| s.layer == crate::Layer::Permanent);
let crossing_end = if last {
permanent.next_back()
} else {
permanent.next()
};
Ok::<_, &str>(CrossPathEnd {
lane: at
.section_at(s)
.and_then(|section| lane(section, "from"))
.ok_or(at_id.unwrap_or_default())?,
s,
crossing_lane: crossing_end
.and_then(|section| lane(section, "to"))
.ok_or(crossing_id.unwrap_or_default())?,
})
};
let od_id = node.attribute("id").unwrap_or_default().to_string();
match (
crossing,
end("roadAtStart", child(node, "startLaneLink"), false),
end("roadAtEnd", child(node, "endLaneLink"), true),
) {
(Some(crossing), Ok(start), Ok(end)) => {
out.push(CrossPath {
crossing: crossing.id,
start,
end,
});
provenance.push(super::CrossPathProvenance {
junction_id: junction_id.to_string(),
od_id,
});
}
(_, start, end) => warnings.push(Warning::CrossPathDropped {
junction_id: junction_id.to_string(),
cross_path_id: od_id,
road_id: start.err().or(end.err()).unwrap_or_default().to_string(),
}),
}
}
}
(out, provenance, warnings)
}
pub(super) fn grid(junction: roxmltree::Node, node: roxmltree::Node) -> Option<ElevationGrid> {
let geometries: Vec<_> = child(junction, "planView")?
.children()
.filter(|n| n.has_tag_name("geometry"))
.collect();
let [line] = geometries[..] else {
return None;
};
child(line, "line")?;
let spacing = attr_f64(node, "gridSpacing").filter(|s| *s > 0.0)?;
let at = |name| attr_f64(line, name).unwrap_or(0.0);
let heading = at("hdg");
let (sin, cos) = heading.sin_cos();
let back = at("s");
let heights = |row: roxmltree::Node, name| -> Vec<f64> {
row.attribute(name)
.unwrap_or_default()
.split_whitespace()
.filter_map(|v| v.parse::<f64>().ok().filter(|v| v.is_finite()))
.collect()
};
Some(ElevationGrid {
origin: [at("x") - back * cos, at("y") - back * sin],
heading,
s_start: attr_f64(node, "sStart").unwrap_or(0.0),
spacing,
rows: node
.children()
.filter(|n| n.has_tag_name("elevation"))
.filter_map(|row| {
Some(GridRow {
center: attr_f64(row, "center")?,
left: heights(row, "left"),
right: heights(row, "right"),
})
})
.collect(),
})
}
fn ring<'a>(
junction_id: &str,
boundary: roxmltree::Node,
road: &impl Fn(&str) -> Option<&'a Road>,
warnings: &mut Vec<Warning>,
) -> Vec<Point> {
let mut segments: Vec<Vec<Point>> = Vec::new();
for node in boundary.children().filter(|n| n.has_tag_name("segment")) {
let road_id = node.attribute("roadId").unwrap_or_default();
let points = road(road_id).and_then(|r| match node.attribute("type") {
Some("lane") => along(r, node),
Some("joint") => across(r, node),
_ => None,
});
match points {
Some(points) if !points.is_empty() => segments.push(points),
_ => warnings.push(Warning::BoundarySegmentDropped {
junction_id: junction_id.to_string(),
road_id: road_id.to_string(),
}),
}
}
let mut ring: Vec<Point> = Vec::new();
let mut gap = 0.0_f32;
let reach = |p: Point, q: Point| (p.x - q.x).hypot(p.y - q.y);
for mut segment in segments.clone() {
let reverse = match ring.last() {
Some(&end) => reach(end, segment[segment.len() - 1]) < reach(end, segment[0]),
None => segments.get(1).is_some_and(|next| {
let ends = [next[0], next[next.len() - 1]];
let near = |p: Point| ends.iter().map(|&e| reach(p, e)).fold(f32::MAX, f32::min);
near(segment[0]) < near(segment[segment.len() - 1])
}),
};
if reverse {
segment.reverse();
}
if let Some(&end) = ring.last() {
gap = gap.max(reach(end, segment[0]));
}
for p in segment {
if ring.last().is_none_or(|&q| reach(p, q) > 1e-3) {
ring.push(p);
}
}
}
if let (Some(&first), Some(&last)) = (ring.first(), ring.last()) {
gap = gap.max(reach(last, first));
}
if ring.len() > 1 && reach(ring[0], ring[ring.len() - 1]) <= 1e-3 {
ring.pop();
}
if gap > GAP_TOLERANCE {
warnings.push(Warning::BoundaryNotClosed {
junction_id: junction_id.to_string(),
gap: f64::from(gap),
});
}
if signed_area(&ring) < 0.0 {
ring.reverse();
warnings.push(Warning::BoundaryClockwise {
junction_id: junction_id.to_string(),
});
}
ring
}
fn signed_area(ring: &[Point]) -> f64 {
let Some(&o) = ring.first() else {
return 0.0;
};
let rel = |p: &Point| (f64::from(p.x - o.x), f64::from(p.y - o.y));
ring.iter()
.zip(ring.iter().cycle().skip(1))
.map(|(a, b)| {
let ((ax, ay), (bx, by)) = (rel(a), rel(b));
ax * by - bx * ay
})
.sum()
}
const OFF_ROAD: f64 = 0.01;
fn station(road: &Road, value: Option<&str>) -> Option<f64> {
match value? {
"begin" | "start" => Some(0.0),
"end" => Some(road.length),
v => v
.trim()
.parse::<f64>()
.ok()
.filter(|s| (-OFF_ROAD..=road.length + OFF_ROAD).contains(s))
.map(|s| s.clamp(0.0, road.length)),
}
}
fn border(road: &Road, od_id: i32, s: f64) -> Option<Point> {
let section = road.section_at(s)?;
let t = if od_id == 0 {
road.base(s)
} else {
road.across(section, s).find(|a| a.od_id == od_id)?.outer_t
};
Some(road.lane_surface(section, od_id, s, t).0)
}
fn along(road: &Road, node: roxmltree::Node) -> Option<Vec<Point>> {
let od_id = attr_i32(node, "boundaryLane")?;
let from = station(road, node.attribute("sStart"))?;
let to = station(road, node.attribute("sEnd"))?;
let (low, high) = (from.min(to), from.max(to));
let mut stations: Vec<f64> = road
.sections
.iter()
.flat_map(|section| section.stations.iter().copied())
.filter(|&s| s > low && s < high)
.chain([low, high])
.collect();
stations.sort_by(f64::total_cmp);
stations.dedup_by(|a, b| (*a - *b).abs() < 1e-6);
if from > to {
stations.reverse();
}
stations
.into_iter()
.map(|s| border(road, od_id, s))
.collect()
}
fn across(road: &Road, node: roxmltree::Node) -> Option<Vec<Point>> {
let s = station(road, node.attribute("contactPoint"))?;
let section = road.section_at(s)?;
let lane = |name| attr_i32(node, name);
let ids: Vec<i32> = section
.right
.iter()
.rev()
.map(|l| l.id)
.chain([0])
.chain(section.left.iter().map(|l| l.id))
.collect();
let index = |id| ids.iter().position(|&i| i == id);
let borders = |id: i32| {
let at = index(id)?;
Some(match id.signum() {
-1 => (at, at + 1),
1 => (at - 1, at),
_ => (at, at),
})
};
let (from, to) = match (lane("jointLaneStart"), lane("jointLaneEnd")) {
(Some(a), Some(b)) => (borders(a)?, borders(b)?),
_ => ((0, 0), (ids.len() - 1, ids.len() - 1)),
};
let (low, high) = (from.0.min(to.0), from.1.max(to.1));
let mut points: Vec<Point> = ids[low..=high]
.iter()
.map(|&id| border(road, id, s))
.collect::<Option<_>>()?;
if from.0 > to.0 {
points.reverse();
}
Some(points)
}
pub(super) fn transitions(
root: roxmltree::Node,
roads: &[(roxmltree::Node, BakedRoad)],
grids: &HashMap<String, ElevationGrid>,
) -> (HashMap<String, Vec<Transition>>, Vec<Warning>) {
let road = |id: &str| roads.iter().map(|(_, r)| &r.road).find(|r| r.od_id == id);
let (mut out, mut warnings) = (HashMap::new(), Vec::new());
for junction in root.children().filter(|n| n.has_tag_name("junction")) {
let od_id = junction.attribute("id").unwrap_or_default();
let (Some(_), Some(boundary)) = (grids.get(od_id), child(junction, "boundary")) else {
continue;
};
let segments: Vec<(roxmltree::Node, Vec<Point>)> = boundary
.children()
.filter(|n| n.has_tag_name("segment"))
.filter_map(|node| {
let r = road(node.attribute("roadId")?)?;
let points = match node.attribute("type")? {
"lane" => along(r, node)?,
"joint" => across(r, node)?,
_ => return None,
};
(!points.is_empty()).then_some((node, points))
})
.collect();
let mut zones = Vec::new();
for (i, (node, joint)) in segments.iter().enumerate() {
let length = attr_f64(*node, "transitionLength").filter(|l| *l > 0.0);
let (Some(length), Some("joint")) = (length, node.attribute("type")) else {
continue;
};
let n = segments.len();
let sides = [&segments[(i + n - 1) % n], &segments[(i + 1) % n]];
let lanes: Vec<&[Point]> = sides
.iter()
.filter(|(s, _)| s.attribute("type") == Some("lane"))
.map(|(_, points)| &points[..])
.collect();
let incoming = node.attribute("roadId").and_then(road);
match (incoming, &lanes[..]) {
(Some(incoming), [a, b]) if n > 2 => {
let contact = node.attribute("contactPoint");
zones.extend(transition(incoming, contact, joint, [a, b], length));
}
_ => warnings.push(Warning::TransitionDropped {
junction_id: od_id.to_string(),
road_id: node.attribute("roadId").unwrap_or_default().to_string(),
}),
}
}
if !zones.is_empty() {
out.insert(od_id.to_string(), zones);
}
}
(out, warnings)
}
fn transition(
road: &Road,
contact: Option<&str>,
joint: &[Point],
lanes: [&[Point]; 2],
length: f64,
) -> Option<Transition> {
const STEPS: usize = 16;
let plan = |p: &Point| [f64::from(p.x), f64::from(p.y)];
let (p0, p1) = (plan(joint.first()?), plan(joint.last()?));
let reach = |a: [f64; 2], b: [f64; 2]| (a[0] - b[0]).hypot(a[1] - b[1]);
let nearest_end = |points: &[Point], to: [f64; 2]| {
let (first, last) = (plan(points.first()?), plan(points.last()?));
Some(reach(first, to).min(reach(last, to)))
};
let [a, b] = lanes;
let (by_p1, by_p0) = match nearest_end(a, p1)? <= nearest_end(b, p1)? {
true => (a, b),
false => (b, a),
};
let (p2, p3) = (walk(by_p1, p1, length)?, walk(by_p0, p0, length)?);
let at_end = station(road, contact).is_some_and(|s| s > road.length / 2.0);
let (s, into) = if at_end {
(road.length, 1.0)
} else {
(0.0, -1.0)
};
let station = road.station(s);
let (sin, cos) = station.heading.sin_cos();
let samples = (0..=STEPS)
.map(|k| {
let k = k as f64 / STEPS as f64;
let at =
|u: [f64; 2], v: [f64; 2]| [u[0] + (v[0] - u[0]) * k, u[1] + (v[1] - u[1]) * k];
let (a, b) = (at(p0, p1), at(p3, p2));
let t = (a[0] - station.x) * -sin + (a[1] - station.y) * cos;
let z = f64::from(road.raised(s, t, 0.0).0.z);
let across = reach(a, b).max(1e-9);
let toward = ((b[0] - a[0]) * cos + (b[1] - a[1]) * sin) * into / across;
(z, station.grade * into * toward)
})
.collect();
Some(Transition {
corners: [p0, p1, p2, p3],
road: samples,
})
}
fn walk(points: &[Point], from: [f64; 2], length: f64) -> Option<[f64; 2]> {
let plan = |p: &Point| [f64::from(p.x), f64::from(p.y)];
let reach = |a: [f64; 2], b: [f64; 2]| (a[0] - b[0]).hypot(a[1] - b[1]);
let mut path: Vec<[f64; 2]> = points.iter().map(plan).collect();
if reach(*path.last()?, from) < reach(path[0], from) {
path.reverse();
}
let mut left = length;
for w in path.windows(2) {
let step = reach(w[0], w[1]);
if step >= left && step > 0.0 {
let f = left / step;
return Some([
w[0][0] + (w[1][0] - w[0][0]) * f,
w[0][1] + (w[1][1] - w[0][1]) * f,
]);
}
left -= step;
}
path.last().copied()
}
pub(super) fn crossings(
root: roxmltree::Node,
roads: &[(roxmltree::Node, BakedRoad)],
lanes: &[Lane],
) -> (Vec<Crossing>, Vec<Warning>) {
let road = |id: &str| roads.iter().map(|(_, r)| &r.road).find(|r| r.od_id == id);
let (mut out, mut warnings) = (Vec::new(), Vec::new());
let junctions = root
.children()
.filter(|n| n.has_tag_name("junction") && n.attribute("type") == Some("crossing"));
for junction in junctions {
let od_id = junction.attribute("id").unwrap_or_default().to_string();
let mut sections = Vec::new();
for node in junction
.children()
.filter(|n| n.has_tag_name("roadSection"))
{
let road_id = node.attribute("roadId").unwrap_or_default();
let placed = road(road_id).and_then(|r| {
let on = |name| station(r, Some(node.attribute(name)?));
let (a, b) = (on("sStart")?, on("sEnd")?);
let (s_start, s_end) = (a.min(b), a.max(b));
Some(CrossingSection {
od_id: node.attribute("id").unwrap_or_default().to_string(),
road: r.id,
s_start,
s_end,
lanes: coverage(r, lanes, (s_start, s_end), &[]),
})
});
match placed {
Some(section) => sections.push(section),
None => warnings.push(Warning::RoadSectionDropped {
junction_id: od_id.clone(),
road_id: road_id.to_string(),
}),
}
}
out.push(Crossing {
name: junction.attribute("name").unwrap_or_default().to_string(),
od_id,
sections,
});
}
(out, warnings)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_ring_far_from_the_origin_keeps_its_winding() {
let (x, y) = (500_000.0, 5_000_000.0);
let ring: Vec<Point> = [(0.0, 0.0), (20.0, 0.0), (20.0, 20.0), (0.0, 20.0)]
.iter()
.map(|(u, v)| Point::new(x + u, y + v, 0.0))
.collect();
assert!((signed_area(&ring) - 800.0).abs() < 1.0);
let reversed: Vec<Point> = ring.iter().rev().copied().collect();
assert!((signed_area(&reversed) + 800.0).abs() < 1.0);
}
}