METHOD AND APPARATUS FOR PREPARING MAP DATA

• US 20110087715A1
• Filed: 06/04/2008
• Published: 04/14/2011
• Est. Priority Date: 06/04/2008
• Status: Abandoned Application

• Current Assignee: TomTom International BV (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Martens, David, Spaan, Bert Jasper
• Application Number:
  US12/736,770
• Publication Number:
  US 20110087715A1
• Time in Patent Office: Days
• US Class Current: 708/200
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps

Abstract

A method is disclosed for using a suitably programmed computer to fit a circular arc to a plurality of points, which form map data representing a feature. In at least one embodiment, the method includes determining whether a region, in which a centre of a circle intersecting a first point and a region around at least one mid-point lies, intersects a perpendicular bisector of a line intersecting the first point and a second point. At least one embodiment of the method is suitable for preparing navigation maps and is applicable to any processing device configured to execute navigation software.

Claims

1. A method of using a suitably programmed computer to fit a circular arc to a plurality of points, comprising:

determining whether a region, in which a centre of a circle intersecting a first point and a region around at least one mid-point lies, intersects a perpendicular bisector of a line intersecting the first point and a second point.

2. The method of claim 1, comprising representing the plurality of points as the coordinates of the first and second points, and a distance d between the line intersecting the first and second points and the circular arc.

3. The method of claim 1, wherein the determining step is performed recursively and, for each recursion, the second point becomes a further mid-point and a new second point is introduced.

4. The method of claim 2, wherein the value d is determined by calculating a radius of the circle and a distance between the centre of the circle and the line intersecting the first and second points.

5. The method of claim 1, wherein the region is determined by determining an area formed by an intersection of a plurality of hyperbolas.

6. The method of claim 5, wherein each hyperbola is formed by a pair of loci representing lines along which lie centres of circles intersecting the first point and a circular region around a further point tangential to an inside and an outside of the circular region around the further point, respectively.

7. The method of claim 5, comprising determining an approximation for each of the plurality of hyperbolas.

8. The method of claim 7, wherein the approximation comprises an intersection between a pair of asymptotes and a tangent.

9. The method of claim 7, comprising limiting the approximation to a predetermined length along one of the asymptotes.

10. The method of claim 1, comprising determining whether a maximum deviation between the circular arc and a polyline formed between the plurality of points is less than a predetermined distance.

11. The method of claim 1, comprising determining whether a maximum angle between the arc a polyline formed between the plurality of points at the first and end points respectively is less than a predetermined angle.

12. The method of claim 1, wherein the plurality of points form map data representing a feature.

13. A non-transitory data storage medium comprising computer executable instructions which, when executed by a processor, cause the processor to perform the method of claim 1.

14. An apparatus comprising:

a processor; and

a memory operatively coupled to the processor,

the memory comprising coordinates of a plurality of points; and

the processor being arranged to determine whether a region, in which a centre of a circle intersecting a first point and a region around at least one mid-point lies, intersects a perpendicular bisector of a line intersecting the first point and a second point.

15. The apparatus of claim 14, wherein the processor is arranged to store in the memory a representation of the plurality of points formed by the coordinates of the first and second points, and a distance d between the line intersecting the first and second points and the circular arc.