Warping geometric objects

• US 6,504,541 B1
• Filed: 10/21/1998
• Issued: 01/07/2003
• Est. Priority Date: 10/21/1998
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Liu, Hongche, Kuttikkad, Shyam
• Primary Examiner(s): Brier, Jeffery
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US09/176,522
• Time in Patent Office: 1,539 Days
• Field of Search: 345/433, 345/442, 345/419, 345/473, 345/418, 345/423, 345/474, 345/475, 345/127, 382/294, 382/154, 382/284, 382/173, 382/295, 382/297, 382/296, 382/298, 716/20
• US Class Current: 345/619
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

A system is disclosed for warping models made from geometric objects, such as electronic maps, to correct local distortions in the models without compromising model topology. A set of transformation functions are derived from relationships between points in a first model that match points in a second model. The transformation functions are then applied to the points in the first model to generate a new model with reduced distortion. In order to provide for reducing local distortions, warping is applied to selected corresponding regions of the first model and the second model by triangulating these regions and generating transformation functions for each corresponding pair of triangles. Topology preservation is achieved by identifying matching points in the first model and the second model that have a potential for causing topology deviations. Such matching points are then excluded from the process of developing transformation equations to be used in the warping process. Matching points with potential for causing topology deviations are identified by triangulating matching points in the selected regions of the first model and the second model and analyzing the resulting triangles.

Claims

1. A computer implemented method for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said method comprising the steps of:

(a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and

(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).

2. The method of claim 1, wherein said step (a) includes the steps of:

triangulating said second set of matching points to obtain a second set of triangles;

triangulating said third set of matching points to obtain a third set of triangles; and

making an initial identification of matching points in said second set of matching points and said third set of matching points that have potential for causing topology deviations in said first set of geometric objects.

3. The method of claim 2, wherein said step of making an initial identification includes the steps of:

selecting a pair of triangles, wherein said pair includes a second triangle in said second set of triangles and a third triangle that is in said third set of triangles and corresponds to said second triangle; and

analyzing said pair of triangles to determine whether vertices of triangles in said pair are matching points that have potential for causing topology deviations in said first set of geometric objects.

4. The method of claim 3, wherein said step of analyzing includes the step of:

determining whether said second triangle and said third triangle are inverted.

5. The method of claim 3, wherein said step of analyzing includes the step of:

determining whether either of said second triangle and said third triangle have acceptable dimensions.

6. The method of claim 5, wherein said step of determining whether either of said second triangle and said third triangle have acceptable dimensions, includes the step of:

determining whether either said second triangle or said third triangle has an area less than a minimum acceptable area.

7. The method of claim 5, wherein said step of determining whether either of said second triangle and said third triangle have acceptable dimensions, includes the step of:

determining whether either said second triangle or said third triangle has a height less than a minimum acceptable height.

8. The method of claim 2, wherein said step (a) further includes the step of:

removing matching status of a set of matching points identified in said step of making an initial identification.

9. The method of claim 8, wherein said step (a) further includes the step of:

replacing a point that had matching status removed in said step of removing matching status.

10. The method of claim 8, wherein said step (a) further includes the steps of:

triangulating said second set of matching points to obtain a new second set of triangles, after performing said step of removing matching status;

triangulating said third set of matching points to obtain a new third set of triangles, after performing said step of removing matching status; and

making an initial identification of matching points in said second set of matching points and said third set of matching points that have potential for causing topology deviations in said first set of geometric objects, after performing said step of removing matching status.

11. The method of claim 10, wherein said step (b) includes the steps of:

generating a set of transformation equations;

identifying a set of arc intersection points in said new second set of geometric objects; and

performing a point transformation on points and arc intersection points in said second set of geometric objects using said set of transformation equations to obtain points for said first set of geometric objects.

12. The method of claim 11, wherein said set of transformation equations includes transformation equations for each corresponding pair of triangles in said new second set of triangles and said new third set of triangles.

13. The method of claim 11, wherein said step (b) further includes the step of:

making arc connections between said points for said first set of geometric objects.

14. The method of claim 1, wherein said second set of geometric objects represents a physical area and said third set of geometric objects represents said physical area.

15. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said method comprising the steps of:

(a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and

(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).

16. The processor readable storage medium of claim 15, wherein said step (a) includes the steps of:

triangulating said second set of matching points to obtain a second set of triangles;

triangulating said third set of matching points to obtain a third set of triangles; and

making an initial identification of matching points in said second set of matching points and said third set of matching points that have potential for causing topology deviations in the first set of geometric objects.

17. The processor readable storage medium of claim 16, wherein said step of making an initial identification includes the steps of:

selecting a pair of triangles, wherein said pair includes a second triangle in said second set of triangles and a third triangle that is in said third set of triangles and corresponds to said second triangle; and

analyzing said pair of triangles to determine whether vertices of triangles in said pair are matching points that have potential for causing topology deviations in said first set of geometric objects.

18. The processor readable storage medium of claim 17, wherein said step of analyzing includes the step of:

determining whether said second triangle and said third triangle are inverted.

19. The processor readable storage medium of claim 17, wherein said step of analyzing includes the step of:

determining whether either of said second triangle and said third triangle have acceptable dimensions.

20. The processor readable storage medium of claim 19, wherein said step of determining whether either of said second triangle and said third triangle have acceptable dimensions, includes the step of:

determining whether either said second triangle or said third triangle has an area less than a minimum acceptable area.

21. The processor readable storage medium of claim 19, wherein said step of determining whether either of said second triangle and said third triangle have acceptable dimensions, includes the step of:

determining whether either said second triangle or said third triangle has a height less than a minimum acceptable height.

22. The processor readable storage medium of claim 16, wherein said step (a) further includes the step of:

removing matching status of a set of matching points identified in said step of making an initial identification.

23. The processor readable storage medium of claim 22, wherein said step (a) further includes the step of:

replacing a point that had matching status removed in said step of removing matching status.

24. The processor readable storage medium of claim 22, wherein said step (a) further includes the steps of:

triangulating said second set of matching points to obtain a new second set of triangles, after performing said step of removing matching status;

triangulating said third set of matching points to obtain a new third set of triangles, after performing said step of removing matching status; and

making an initial identification of matching points in said second set of matching points and said third set of matching points that have potential for causing topology deviations in said first set of geometric objects, after performing said step of removing matching status.

25. The processor readable storage medium of claim 24, wherein said step (b) includes the steps of:

generating a set of transformation equations;

identifying a set of arc intersection points in said new second set of geometric objects; and

performing a point transformation on points and arc intersection points in said second set of geometric objects using said set of transformation equations to obtain points for said first set of geometric objects.

26. The processor readable storage medium of claim 25, wherein said set of transformation equations includes transformation equations for each corresponding pair of triangles in said new second set of triangles and said new third set of triangles.

27. The processor readable storage medium of claim 25, wherein said step (b) further includes the step of:

making arc connections between said points for said first set of geometric objects.

28. The processor readable storage medium of claim 15, wherein said second set of geometric objects represents a physical area and said third set of geometric objects represents said physical area.

29. An apparatus for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said apparatus comprising:

a processor; and

a processor readable storage medium, in communication with said processor, said processor readable storage medium storing code for programming said processor to perform the steps of;

(a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and

(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).

30. The apparatus of claim 29, wherein said step (a) includes the steps of:

triangulating said second set of matching points to obtain a second set of triangles;

triangulating said third set of matching points to obtain a third set of triangles; and

making an initial identification of matching points in said second set of matching points and said third set of matching points that have potential for causing topology deviations in said first set of geometric objects.

31. The apparatus of claim 30, wherein said step of making an initial identification includes the steps of:

selecting a pair of triangles, wherein said pair includes a second triangle in said second set of triangles and a third triangle that is in said third set of triangles and corresponds to said second triangle; and

analyzing said pair of triangles to determine whether vertices of triangles in said pair are matching points that have potential for causing topology deviations in the first set of geometric objects.

32. The apparatus of claim 31, wherein said step of analyzing includes the step of:

determining whether said second triangle and said third triangle are inverted.

33. The apparatus of claim 31, wherein said step of analyzing includes the step of:

determining whether either of said second triangle and said third triangle have acceptable dimensions.

34. The apparatus of claim 33, wherein said step of determining whether either of said second triangle and said third triangle have acceptable dimensions, includes the step of:

determining whether either said second triangle or said third triangle has an area less than a minimum acceptable area.

35. The apparatus of claim 33, wherein said step of determining whether either of said second triangle and said third triangle have acceptable dimensions, includes the step of:

determining whether either said second triangle or said third triangle has a height less than a minimum acceptable height.

36. The apparatus of claim 30, wherein said step (a) further includes the step of:

removing matching status of a set of matching points identified in said step of making an initial identification.

37. The apparatus of claim 36, wherein said step (a) further includes the step of:

replacing a point that had matching status removed in said step of removing matching status.

38. The apparatus of claim 36, wherein said step (a) further includes the steps of:

triangulating said second set of matching points to obtain a new second set of triangles, after performing said step of removing matching status;

triangulating said third set of matching points to obtain a new third set of triangles, after performing said step of removing matching status; and

making an initial identification of matching points in said second set of matching points and said third set of matching points that have potential for causing topology deviations in said first set of geometric objects, after performing said step of removing matching status.

39. The apparatus of claim 38, wherein said step (b) includes the steps of:

generating a set of transformation equations;

identifying a set of arc intersection points in said new second set of geometric objects; and

performing a point transformation on points and arc intersection points in said second set of geometric objects using said set of transformation equations to obtain points for said first set of geometric objects.

40. The apparatus of claim 39, wherein said set of transformation equations includes transformation equations for each corresponding pair of triangles in said new second set of triangles and said new third set of triangles.

41. The apparatus of claim 39, wherein said step (b) further includes the step of:

making arc connections between said points for said first set of geometric objects.

42. The apparatus of claim 29, wherein said second set of geometric objects represents a physical area and said third set of geometric objects represents said physical area.