ToaKraka&a;s website
Modified relative&h;neighborhood&h;graph algorithm for generating road networks
Premise
A relative&h;neighborhood graph (an RNG) looks remarkably similar to a network of roads.
Problem
Because the RNG algorithm treats all nodes the same regardless of their age, it cannot be used to generate a road network in a realistic incremental fashion. (When a new node is added to the graph, existing edges are erased very often. In contrast, the abandonment of an existing road in a real&h;life road network is extremely rare.)
Solution
Instead of the standard RNG algorithm, use the following modified algorithm.
0
Start with (1) a target count of traffic&h;generating nodes and (2) a node placed in a random location and flagged as (a) old and (b) generating trips. (Such a node may represent a building, a neighborhood, a town, or a settled region.)
1
While the count of traffic&h;generating nodes is lower than than the target number:
a
At a random location, create a node that is flagged as (1) new and (2) generating trips.
b
(A node lies in the lens of two other nodes if the distances from the first node to the other nodes are both smaller than the distance between the other nodes. A node lies in the lens of an edge if it lies in the lens of the two nodes that define the edge.)
For each edge in whose lens a node that has been flagged as new lies:
1
Create a node, flagged as (1) new and (2) not generating trips, at the point on the edge that is closest to the node that is flagged as new. (Such a node may represent an intersection of roads, an interchange of highways, or a market town or warehouse complex that has sprung up at such an intersection or interchange.)
(This step is the only modification to the standard algorithm.)
2
Delete the edge.
c
For each pair of nodes that does not already define an edge: If no third node lies in the lens of the pair, then create an edge that is defined by the pair. (If, in the course of this step, none of the three nodes in a trio is flagged as new, then you can safely assume (without actually performing the measurement) that the third node does not lie within the lens of the first two nodes.)
d
For each node that is flagged as new: Flag the node as old.
This modified algorithm does not completely prevent eliminations of existing roads, but it does make those eliminations vastly less common, and even reduces many of them to partial realignments. It&a;s very funny to look at a generated road network and see a long, straight series of segments where neither of the endpoints is a traffic generator, because what used to be the rest of the series was realigned!
Example
Generation Options
:
Distribution of Traffic&h;Generating Nodes
(Warning: Computation time increases with the square of the number of points.)
Viewing Options
Edges
Nodes