Positioning map views to show more optimal route information

• US 8,676,489 B2
• Filed: 02/07/2008
• Issued: 03/18/2014
• Est. Priority Date: 02/07/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cheung, Matthew, Jansen, Markus Ludwig
• Primary Examiner(s): Danneman, Paul
• Application Number:
  US12/027,278
• Publication Number:
  US 20090204892A1
• Time in Patent Office: 2,231 Days
• Field of Search: None
• US Class Current: 701/400
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker

Abstract

Described is a technology by which a more optimal map view with respect to route information is returned in response to an online mapping request. A start or end location is positioned away from the map center as appropriate to show as much route information as possible within the map view, given view size and zoom constraints. In one example, various-sized bounding boxes that contain the start or end location and one or more routes may be evaluated to determine a largest bounding box that meets the mapping size constraint; the center of that bounding box is the center of the map view. In one alternative, map views at various zoom levels may be scored against one another to determine which map view contains the most important route information, such as the most maneuver points and/or landmarks within each map view; the map view with the best score is returned.

Claims

1. A computer-implemented method comprising:

employing at least one processor to perform steps comprising, obtaining a critical element to be provided in a map view having size and zoom constraints, the critical element associated with a route set containing at least one route; and

computing a map view by positioning the map view relative to the critical element so that more of the route set appears within the map view than appears in a non-positioned map view including by;

determining where each route of the route set reaches a straight line distance from the critical element;

determining a bounding box that includes the critical element and each point that corresponds to where each route reached the straight line distance, and each point of that route between the critical element and the point where the straight line distance was reached; and

computing at least one additional map view at a different zoom level, computing a best score for the map view and each additional map view, and returning the map view or an additional map view based on its computed score relative to the score computed for each other map view.

2. The computer-implemented method of claim 1 wherein obtaining the critical element comprises receiving data corresponding to a start or end location.

3. The computer-implemented method of claim 1 wherein the bounding box comprises a bounding rectangle that includes the critical element and each point that corresponds to where each route reached the straight line distance, and each point of that route between the critical element and the point where the straight line distance was reached.

4. The computer-implemented method of claim 1, further comprising changing the straight line distance into a changed straight line distance and determining where each route of the route set reaches the changed straight line distance.

5. The computer-implemented method of claim 4 wherein changing the straight line distance into a changed straight line distance comprises increasing the straight line distance, and wherein computing the map view further comprises determining a previous bounding rectangle that includes the critical element, each point that corresponds to where each route reached the straight line distance, and each point in between, determining a next bounding rectangle that includes the critical element and each point that corresponds to where each route reached the changed straight line distance, and if the other next rectangle does not meet the size constraint, using the previous bounding rectangle to determine the map view.

6. The computer-implemented method of claim 1 wherein computing the score comprises determining how many important elements are within the map view and the additional map view.

7. The computer-implemented method of claim 1 wherein computing the score comprises determining weights for important elements within the map view and the additional map view.

8. In a computing environment, a system comprising, at least one processor, a memory communicatively coupled to the at least one processor and including instructions configured to provide:

an online mapping service that receives configured to receive a request for a map, the mapping service coupled to a data store configured to provide map data comprising a critical element and route information in response to the request, the mapping service further including map positioning logic configured to generate a plurality of potential map views at different zoom levels and configured to select the map view from among the potential map views by scoring each potential map view with a best score with respect to one or more maneuver points therein including by determining a straight line distance from the critical element to the one or more maneuver points and configured to provide the map data as a map view in which the critical element is positioned so as to appear in the map view along with more route information to or from the critical element relative to route information that appears when the critical element is centered in the map view.

9. The system of claim 8 wherein the route information comprises at least two roads and data corresponding to a maneuver point for turning from one road to another.

10. The system of claim 8 wherein the route information includes at least one landmark/point of interest.

11. One or more computer storage devices, having computer-executable instructions, which when executed, perform steps, comprising, returning a map view in response to an online request, including computing a map view based on a critical element that appears as a critical element representation within the map view and route data that appears as at least one route representation within the map view, including by positioning the critical element relative to the map view to have more of each route representation appear in the map view than if the critical element is not positioned, and wherein computing the map view further comprises using different distances from the critical element to determine a set of differently-sized bounding boxes that each contain the critical element and a different amount of route data, and determining the map view based on a largest bounding rectangle that does not exceed a size constraint associated with the map view, and computing a best score for the map view.

12. The one or more computer storage devices of claim 11 wherein the different distances are each straight line distances from the critical element, and wherein using the different distances comprises, for each straight line distance, traversing each route to determine a point on that route that reaches that straight line distance.

13. The one or more computer storage devices of claim 11 wherein computing the map view comprises:

selecting each zoom level from a plurality of zoom levels, and for each zoom level, using different distances from the critical element to determine the set of differently-sized bounding boxes that each contain the critical element and route data, and determining the largest bounding box that does not exceed the size constraint associated with the map view to provide a candidate for that zoom level;

scoring each of the candidates for the plurality of zoom levels; and

determining the map view based on the candidate having the best score.

14. The one or more computer storage devices of claim 13 wherein scoring each of the candidates comprises computing an importance value corresponding to the route data within each candidate.

15. The one or more computer storage devices of claim 14 wherein computing the importance value for each candidate comprises evaluating each maneuver point within that candidate, or each landmark or other point of interest within that candidate, or any combination of each maneuver point and each landmark or other point of interest within that candidate.