Road height generation for a road network

• US 9,207,094 B2
• Filed: 08/31/2012
• Issued: 12/08/2015
• Est. Priority Date: 06/10/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pirwani, Imran A., McCarthy, Paul S.
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): Malhotra, Sanjeev
• Application Number:
  US13/601,689
• Publication Number:
  US 20130332063A1
• Time in Patent Office: 1,194 Days
• Field of Search: 701/200, 701/201, 701/207, 701/208, 701/210, 701/300, 701/533, 700/259, 345/419, 345/853, 606/69, 382/294, 382/307, 340/995.1
• US Class Current: 1/1
• 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 an 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, wherein, for each of the plurality of junctions, a height separation between the junction and all of its neighboring junctions is minimized in the cost function; and

transmitting, from the computing device to a display, data based on the height values for displaying, by the display, a three-dimensional map of a part of the road network area using the height values.

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, 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.

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

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

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

7. The method of claim 1, further comprising generating a plurality of polylines based on the data sets, wherein each polyline corresponds to a road of the road network.

8. The method of claim 7, further comprising dividing the plurality of polylines at junctions such that no pair of polylines cross.

9. The method of claim 7, 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.

10. A non-transitory 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, wherein, for each of the plurality of junctions, a height separation between the junction and all of its neighboring junctions is minimized in the cost function; and

transmitting, from the processing subsystem to a display of a portable device, data based on the height values for displaying, by the display a three-dimensional map of the road network area using the height values.

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

12. The computer-readable storage medium of claim 10, wherein the method further comprises generating a plurality of polylines based on the data sets, wherein each polyline corresponds to a road of the road network.

13. The computer-readable storage medium of claim 12, wherein the method further comprises dividing the plurality of polylines at junctions such that no pair of polylines cross.

14. The computer-readable storage medium of claim 12, wherein the method further comprises:

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.

15. A portable device comprising:

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;

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 a 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, wherein, for each of the plurality of junctions, a height separation between the junction and all of its neighboring junctions is minimized in the cost function; and

a display configured to display a three-dimensional map of the road network area using the height values.

16. The portable device of claim 15, 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.

17. The portable device of claim 15, wherein the processing subsystem is further configured to generate a plurality of polylines based on the data sets, wherein each polyline corresponds to a road of the road network.

18. The portable device of claim 17, wherein the processing subsystem is further configured to divide the plurality of polylines at junctions such that no pair of polylines cross.

19. The portable device of claim 17, wherein the processing subsystem is further configured to:

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

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

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