pub struct Perimeter {
    pub roads: Vec<RoadSideID>,
    pub interior: BTreeSet<RoadID>,
Expand description

A sequence of roads in order, beginning and ending at the same place. No “crossings” – tracing along this sequence should geometrically yield a simple polygon.


roads: Vec<RoadSideID>interior: BTreeSet<RoadID>

These roads exist entirely within the perimeter


Starting at any lane, snap to the nearest side of that road, then begin tracing a single block, with no interior roads. This will fail if a map boundary is reached. The results are unusual when crossing the entrance to a tunnel or bridge, and so skip is used to avoid tracing there.

This calculates all single block perimeters for the entire map. The resulting list does not cover roads near the map boundary.

Blockfinding is specialized for the LTN tool, so non-driveable roads (cycleways and light rail) are considered invisible and can’t be on a perimeter. Previously, there were also some heuristics here to try to skip certain bridges/tunnels that break the planarity of blocks.

A perimeter has the first and last road matching up, but that’s confusing to work with. Temporarily undo that.

Restore the first=last invariant. Methods may temporarily break this, but must restore it before returning.

Try to merge two blocks. Returns true if this is successful, which will only be when the blocks are adjacent, but the merge wouldn’t create an interior “hole”.

Note this may modify both perimeters and still return false. The modification is just to rotate the order of the road loop; this doesn’t logically change the perimeter.

TODO Due to, it seems like rotation sometimes breaks to_block, so for now, always revert to the original upon failure.

Should we reverse one perimeter to match the winding order?

This is only meant to be called in the middle of try_to_merge. It assumes both perimeters have already been rotated so the common roads are at the end. The invariant of first=last is not true.

Try to merge all given perimeters. If successful, only one perimeter will be returned. Perimeters are never “destroyed” – if not merged, they’ll appear in the results. If stepwise_debug is true, returns after performing just one merge.

If the perimeter follows any dead-end roads, “collapse” them and instead make the perimeter contain the dead-end.

Consider the perimeters as a graph, with adjacency determined by sharing any road in common. Partition adjacent perimeters, subject to the predicate. Each partition should produce a single result with merge_all.

Assign each perimeter one of num_colors, such that no two adjacent perimeters share the same color. May fail. The resulting colors are expressed as [0, num_colors).

Does this perimeter completely enclose the other?

Shrinks or expands the perimeter by tracing the opposite side of the road.

Looks for perimeters that’re completely surrounded by other perimeters, aka, holes. Attempts to merge them with the surrounding perimeter. This can be useful for applications trying to incrementally merge adjacent blocks without creating splits, because it’s often impossible to do this in one merge when there are holes.

This should never “lose” any of the input. It may not be fast or guaranteed to find and fix every hole.

Trait Implementations

Returns a copy of the value. Read more
Performs copy-assignment from source. Read more
Formats the value using the given formatter. Read more
Deserialize this value from the given Serde deserializer. Read more
Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
Instruments this type with the current Span, returning an Instrumented wrapper. Read more

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The resulting type after obtaining ownership.
Creates owned data from borrowed data, usually by cloning. Read more
Uses borrowed data to replace owned data, usually by cloning. Read more
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.