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.
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
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 https://github.com/a-b-street/abstreet/issues/841, it seems like rotation
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
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
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.
Returns the argument unchanged.