Method for stitching multiple converging paths

• US 7,987,045 B2
• Filed: 01/26/2007
• Issued: 07/26/2011
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Johnson, Eric, Bowman, Gordon Gregory
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Holwerda; Stephen
• Application Number:
  US11/627,558
• Publication Number:
  US 20070229311A1
• Time in Patent Office: 1,642 Days
• Field of Search: 340/995.1, 340/995.14, 701/200, 701/201, 701/202, 701/208, 701/211, 703/2, 345/619, 345/629, 345/648, 345/649
• US Class Current: 701/200
• 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
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/147 using display panels
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2219/004 Annotating, labelling
• CPC Class Codes: G08G 1/096805 where the transmitted instructions are used to compute a route
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: G09G 2340/0492 Change of orientation of the displayed image, e.g. upside-down, mirrored
• CPC Class Codes: G09G 2340/10 Mixing of images, i.e. displayed pixel being the result of an operation, e.g. adding, on the corresponding input pixels
• CPC Class Codes: G09G 2340/145 related to small screens
• CPC Class Codes: G09G 5/377 for mixing or overlaying two or more graphic patterns G09G5/02, G09G5/397 take precedence

Abstract

A method of stitching converging path segments to aesthetically label Y-intersections, path bifurcations or splits in roads or the like entails determining which pair of adjacent path segments subtend the largest angle. The path segments subtending the largest angle are reconstructed (stitched together) and a single instance of the label is then rendered along the reconstructed path. Although this stitching can be performed on the client device, pre-stitching server-side is even more efficient in terms of economizing over-the-air bandwidth and onboard processing resources.

Claims

1. A method of stitching multiple converging paths of a map displayed on a wireless communications device, the method comprising:

providing map data for rendering the map on a display of the device, the map data including label data for labelling paths on the map;

identifying at least three path segments that converge to a common point on the map, each of the path segments having an identical label;

determining an angle subtended by each pair of adjacent path segments;

identifying, using at least one determined angle, which pair of adjacent path segments subtends a largest angle;

generating a reconstructed path by stitching together the pair of adjacent path segments subtending the largest angle; and

displaying, on the device, the map with the reconstructed path.

2. The method as claimed in claim 1 further comprising rendering a single instance of the label along the reconstructed path.

3. The method as claimed in claim 1 wherein the identifying, determining and generating are performed on a server.

4. The method as claimed in claim 1 wherein the identifying, determining and generating are performed on the wireless communications device.

5. The method as claimed in claim 1 wherein determining the angle subtended by each pair of adjacent path segments comprises:

determining vector directions for each of the path segments at the common point where the path segments converge; and

computing angles between adjacent vectors.

6. The method as claimed in claim 2 wherein rendering a single instance of the label comprises:

determining a center of the reconstructed path; and

verifying whether placement of the label at the center of the reconstructed path interferes with any other label.

7. The method as claimed in claim 1 wherein identifying at least three path segments that converge to a common point on the map comprises identifying a Y-intersection having exactly three path segments.

8. The method as claimed in claim 1 wherein determining an angle in order to identify which pair of adjacent path segments subtends the largest angle comprises determining, in a case where two of the largest angles are equal, which of the adjacent path segments would result in a more horizontally level label.

9. A computer readable medium comprising code executable by a processor to perform the steps of:

providing map data for rendering the map on a display of the device, the map data including label data for labelling paths on the map;

identifying at least three path segments that converge to a common point on the map, each of the path segments having an identical label;

determining an angle subtended by each pair of adjacent path segments;

identifying, using at least one determined angle, which pair of adjacent path segments subtends a largest angle; and

generating a reconstructed path by stitching together the pair of adjacent path segments subtending the largest angle.

10. The computer readable medium as claimed in claim 9 wherein the code is configured to perform render a single instance of the label along the reconstructed path.

11. The computer readable medium as claimed in claim 9 wherein the identifying, determining and generating are performed on a server.

12. The computer readable medium as claimed in claim 9 wherein the identifying, determining and generating are performed on a wireless communications device.

13. The computer readable medium as claimed in claim 9 wherein determining the angle subtended by each pair of adjacent path segments comprises:

determining vector directions for each of the path segments at the common point where the path segments converge; and

computing angles between adjacent vectors.

14. The computer readable medium as claimed in claim 10 wherein rendering a single instance of the label comprises:

determining a center of the reconstructed path; and

verifying whether placement of the label at the center of the reconstructed path interferes with any other label.

15. The computer readable medium as claimed in claim 9 wherein identifying at least three path segments that converge to a common point on the map comprises identifying a Y-intersection having exactly three path segments.

16. The computer readable medium as claimed in claim 9 wherein determining an angle in order to identify which pair of adjacent path segments subtends the largest angle comprises determining, in a case where two of the largest angles are equal, which of the adjacent path segments would result in a more horizontally level label.

17. A wireless communications device for displaying a map on the device, the wireless communications device comprising:

an input device for causing the device to obtain map data for rendering the map to be displayed on a display of the device, the map data including label data for labelling paths on the map; and

a memory for storing code to instruct a processor to;

identify at least three path segments that converge to a common point on the map, each of the path segments having an identical label;

determine an angle subtended by each pair of adjacent path segments;

identify, using at least one determined angle, which pair of adjacent path segments subtends a largest angle;

generate a reconstructed path by stitching together the pair of adjacent path segments subtending the largest angle; and

render a single instance of the label along the reconstructed path.

18. The wireless communications device as claimed in claim 17 wherein the processor determines the angle subtended by each pair of adjacent path segments by:

determining vector directions for each of the path segments at the common point where the path segments converge; and

computing angles between adjacent vectors.

19. The wireless communications device as claimed in claim 17 wherein the processor renders a single instance of the label comprises by:

determining a center of the reconstructed path; and

verifying whether placement of the label at the center of the reconstructed path interferes with any other label.

20. The wireless communications device as claimed in claim 17 wherein the processor identifies at least three path segments that converge to a common point on the map by identifying a Y-intersection having exactly three path segments.

21. The wireless communications device as claimed in claim 17 wherein the processor further determines, in a case where two of the largest angles are equal, which of the adjacent path segments would result in a more horizontally level label.