ROAD HEIGHT GENERATION FOR A ROAD NETWORK

• US 20130332063A1
• Filed: 08/31/2012
• Published: 12/12/2013
• Est. Priority Date: 06/10/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pirwani, Imran A., McCarthy, Paul S.
• Granted Patent: US 9,207,094 B2
• Time in Patent Office: Days
• US Class Current: 701/409
• CPC Class Codes: G01C 21/3638 including 3D objects and buildings three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05
• CPC Class Codes: G01C 21/3822 Road feature data, e.g. slope data

Abstract

Road height values for a road network area are generated based on locations of junctions and stacking orders of roads in junctions in which at least one road passes over another road. A cost function can be optimized to obtain height values for each road of each junction. The cost function can be constrained such that roads of the grade separated crossings satisfy the stacking order designated for the roads and to have a minimum distance between roads having consecutive stacking order values. The obtained height values can be used for rendering a three-dimensional map of a part of the road network area.

Claims

1. A method for generating road height values for a road network area that includes a plurality of junctions, the method comprising:

receiving, by a computing device, a data set for each junction in the road network area, wherein each data set includes a road designation, a first coordinate, a second coordinate, and a stacking order for each road of a respective junction, wherein the plurality of junctions include a plurality of grade separated crossings, a grade separated crossing including at least two roads having a different stacking order signifying that the at least two roads have different heights;

determining, by the computing device, height variables that provide on optimal value for a cost function based on the road data set for each junction, wherein height values of roads of a grade separated crossing are constrained;

to satisfy the stacking order of each road in the junction, and

to have a minimum distance between roads having consecutive stacking order values; and

transmitting, from the computing device to a controller, the height values to the controller for rendering a three-dimensional map of a part of the road network area.

2. The method of claim 1, wherein the first coordinate is a latitude and the second coordinate is a longitude.

3. The method of claim 1, wherein, for all junctions, the height separation between a junction and all of its neighboring junctions is minimized in the cost function.

4. The method of claim 1, further comprising receiving data sets at non-junction locations along the roads, wherein a data set at a non junction location includes at least a road designation, a first location coordinate, and a second location coordinate.

5. The method of claim 1, further comprising generating height values at non junction locations along the roads.

6. The method of claim 5, wherein a slope of height values between junctions is constrained in the cost function.

7. The method of claim 5, wherein a monotonicity constraint is applied to the height values between junctions.

8. A method for generating road height values for a road network area that includes a plurality of junctions, the method comprising:

receiving, by a computing device, a plurality of data sets including a road data set for each junction in the road network area, wherein each data set includes at least one of a road designation, a first coordinate, a second coordinate, and a stacking order for each road of a junction;

wherein the plurality of junctions include a plurality of grade separated crossings, a grade separated crossing including at least two roads having a different stacking order signifying that the at least two roads have different heights;

generating a plurality of polylines based on the data sets, wherein each polyline corresponds to a road of the road network;

dividing polylines at junctions such that no pair of polylines cross;

determining height variables that provide an optimal value for a cost function based on the data sets, wherein height values of roads of a grade separated crossing are constrained;

to satisfy the stacking order of each road in the junction, and

to have a minimum distance between roads having consecutive stacking order values; and

transmitting, from the computing device to a controller, the height values to the controller for rendering a three-dimensional map of the road network area.

9. The method of claim 8, wherein the first coordinate is a latitude and the second coordinate is a longitude.

10. The method of claim 8, wherein, for all junctions, the height separation between a junction and all of its neighboring junctions is minimized in the cost function.

11. The method of claim 8, further comprising:

for each polyline in the road network area, determining whether an endpoint of the polyline is a grade separated crossing;

if an endpoint of the polyline is a grade separated crossing, resampling the polyline densely with respect to a first fixed parameter; and

if no endpoint of the polyline is a grade separated crossing, resampling the polyline sparsely with respect to a second fixed parameter.

12. The method of claim 11, wherein a slope of height values between junctions is constrained in the cost function.

13. The method of claim 12, wherein a bound used in constraining the slope is a function of distance along a polyline from the center of the polyline.

14. The method of claim 13, wherein the bound used in constraining the slope constrains the slope to be smaller at distances that are further from the center of the polyline.

15. The method of claim 8, wherein a monotonicity constraint is applied in the cost function to the height values along each polyline.

16. A method for generating road height values for a road network area that includes a plurality of junctions, the method comprising:

receiving a data set for each junction in the road network area, wherein each data set includes a road designation, a first coordinate, a second coordinate, and a stacking order for each road of a respective junction, wherein the plurality of junctions include a plurality of grade separated crossings, a grade separated crossing including at least two roads having a different stacking order signifying a difference in height of the at least two roads;

identifying spatially dense regions in a road network area;

dividing a road network area into sectors having edges designated at spatially dense regions that are equidistant from neighboring spatially dense regions;

applying an enforced height to junctions at the edges; and

,

for each sector;

determining height variables that provide on optimal value for a cost function based on the junction data set for each junction, wherein height values of roads of a grade separated crossing are constrained;

to satisfy the stacking order of each road in the junction, and

to have a minimum distance between roads having consecutive stacking order values;

reassembling sectors into a road network map; and

transmitting, from the computing device to a processor, the height values to the processor for rendering a three-dimensional map of the road network area.

17. A computer-readable storage medium having program code stored thereon, the program code including instructions that, when executed by a processing subsystem of an electronic device, cause the processing subsystem to perform a method, the method comprising:

receiving a data set for each junction in the road network area, wherein each data set includes a road designation, a first coordinate, a second coordinate, and a stacking order for each road of a respective junction;

wherein the plurality of junctions include a plurality of grade separated crossings, a grade separated crossing including at least two roads having a different stacking order signifying that the at least two roads have different heights;

determining height variables that provide on optimal value for a cost function based on the junction data set for each junction, wherein height values of roads of a grade separated crossing are constrained;

to satisfy the stacking order of each road in the junction, and

to have a minimum distance between roads having consecutive stacking order values; and

transmitting, from the processing subsystem to a controller of a portable device, the height values to the controller for rendering a three-dimensional map of the road network area.

18. The computer-readable storage medium of claim 17, wherein the processing subsystem is communicatively coupled to the portable device via a network interface.

19. A portable device comprising:

a user interface including a display, wherein the display is configured to display a navigation image;

a network interface including;

receiving components for receiving global positioning system (GPS) signals and transceiver components for communicatively coupling the portable device to a road height generation system; and

a controller configured to receive height values from the road height generation system via the network interface, wherein the height values are generated by a processing subsystem of the road height generation system, the processing subsystem configured to;

receive a data set for each junction in the road network area, wherein each at a set includes a road designation, a first coordinate, a second coordinate, and a stacking order for each road of a respective junction;

wherein the plurality of junctions include a plurality of grade separated crossings, a grade separated crossing including at least two roads having a different stacking order signifying that the at least two roads have different heights;

determine height variables that provide on optimal value for a cost function based on the junction data set for each junction, wherein height values of roads of a grade separated crossing are constrained;

to satisfy the stacking order of each road in the junction, and

to have a minimum distance between roads having consecutive stacking order values.

20. The controller of claim 19, further configured to:

determine a map segment to display, wherein the map segment corresponds to a location indicated by the received GPS signals;

render a navigation image of the map segment, wherein the navigation image is based on the received height values.