Method and system for generating a schematic map

Abstract

A method for automatically generating, in real-time, for display on a display, a simplified network layout from an initial network layout including one or more lines each connecting a plurality of nodes. Graph information is provided indicating vertices representing geographic positions of the nodes and edges representing connections between the nodes. The nodes are repositioned to optimize an objective function based on readability of the simplified network layout. Nodes and edges are discretized using interpolation to align a plurality of the nodes and connect the aligned nodes using simplified k-linear segments, where k-linear segments are parallel to one of k equidistant orientations whose angles are multiples of 180/k degrees, with k larger or equal to two. The simplified network layout is provided for a display.

What is claimed is: 
     
         1 . A method for automatically generating, in real-time, for display on a display a simplified network layout from an initial network layout, the initial network layout including one or more lines each connecting a plurality of nodes, the method comprising:
 providing graph information for the initial network layout indicating a plurality of vertices representing geographic positions of the plurality of nodes in the initial network layout and edges representing connections between the nodes, wherein each of the lines comprises a plurality of connected edges;   repositioning, using a processor, one or more of the nodes, wherein said repositioning comprising determining new positions for the one or more nodes to optimize an objective function based on readability of the simplified network layout;   discretizing the nodes and edges using interpolation to align a plurality of the nodes and connect the aligned nodes using simplified k-linear segments to generate the simplified network layout, where each of the k-linear segments is parallel to one of k equidistant orientations whose angles are multiples of 180/k degrees, where k is at least two; and   providing the simplified network layout for display.   
     
     
         2 . The method of  claim 1 , wherein the objective function comprises a cost function comprising:
 a first cost for displacing each node from its original or prior position to a new position in a modified network including the repositioned nodes;   a second cost representing a difference of each edge length in the modified network from an average edge length of the original or prior positions; and   a third cost of having non-smooth lines in a graph of the modified network;   wherein said optimizing the objective function comprises minimizing the cost function;   wherein said minimizing the cost function comprises:   computing first and second derivatives of the cost function; and   using a trust-region method to determine optimal positions for the one or more nodes.   
     
     
         3 . The method of  claim 1 , wherein said discretizing comprises, for each of the one or more lines:
 dividing the line into a plurality of segments at one or more anchor points; and   for each of the plurality of segments:
 simplifying the segment; 
 quantizing angles of parts of the simplified segment to the closest k-linear angle; 
 generating a segment simplification passing from start and end points of the segment that linearly interpolates segment points with the k-linear angle of corresponding subsegments from said quantizing; and 
 updating the anchor points based on the final segment. 
   
     
     
         4 . The method of  claim 1 , wherein the method further comprises:
 inserting a first additional k-linear segment in the simplified network layout connecting one of the aligned nodes to a virtual intermediate point; and   inserting a second additional k-linear segment in the simplified network layout connecting the virtual intermediate point to another of the aligned nodes.   
     
     
         5 . A non-transitory computer-readable medium having instructions stored thereon that, when executed by a computer, cause the computer to perform a method for automatically generating, in real-time, for display on a display a simplified network layout from an initial network layout, the initial network layout including one or more lines each connecting a plurality of nodes, the method comprising:
 providing directed graph information for the initial network layout indicating a plurality of vertices representing geographic positions of the plurality of nodes in the initial network layout and edges representing connections between the nodes, wherein each of the lines comprises a plurality of connected edges;   repositioning, using a processor, one or more of the nodes, wherein said repositioning comprising determining new positions for the one or more nodes to optimize an objective function based on readability of the simplified network layout,   discretizing the nodes and edges using interpolation to align a plurality of the nodes and connect the aligned nodes using simplified k-linear segments to generate the simplified network layout, where k-linear segments are parallel to one of k equidistant orientations whose angles are multiples of 180/k degrees, with k larger or equal two; and   providing the simplified network layout for display.   
     
     
         6 . The non-transitory computer-readable medium of  claim 5 , wherein the objective function comprises a cost function, the cost function comprising:
 a first cost for displacing each node from its original or prior position to a new position in a modified network including the repositioned nodes;   a second cost representing a difference of each edge length in the modified network from an average edge length of the original or prior positions; and   a third cost of having non-smooth lines in a graph of the modified network;   wherein said optimizing the objective function comprises minimizing the cost function;   wherein said minimizing the cost function comprises:   computing first and second derivatives of the cost function; and   using a trust-region method to determine optimal positions for the one or more nodes.   
     
     
         7 . The non-transitory computer-readable medium of  claim 5 , wherein said discretizing comprises, for each of the one or more lines:
 dividing the line into a plurality of segments at one or more anchor points; and   for each of the plurality of segments:
 simplifying the segment; 
 quantizing angles of parts of the simplified segment to the closest k-linear angle; 
 generating a segment simplification passing from start and end points of the segment that linearly interpolates segment points with the k-linear angle of corresponding subsegments from said quantizing; and 
 updating the anchor points based on the final segment. 
   
     
     
         8 . The non-transitory computer-readable medium of  claim 5 , wherein the method further comprises:
 inserting a first additional k-linear segment in the simplified network layout connecting one of the aligned nodes to a virtual intermediate point; and   inserting a second additional k-linear segment in the simplified network layout connecting the virtual intermediate point to another of the aligned nodes.