Design of arbitrary linear and non-linear maps

• US 7,649,534 B2
• Filed: 02/01/2006
• Issued: 01/19/2010
• Est. Priority Date: 02/01/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Salmre, Ivo William
• Primary Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US11/344,827
• Publication Number:
  US 20070176932A1
• Time in Patent Office: 1,448 Days
• Field of Search: 345/419, 345/647, 382/276, 382/248
• US Class Current: 345/441
• CPC Class Codes: G06T 3/153 using elastic snapping

Abstract

Various software mapping aspects are provided. They include, but are not limited to, providing linear map to non-linear map conversion or transformation (and vice versa) in a symmetric fashion, so that data in one map upon conversion is symmetric in another map with respect to the former map. One way this is accomplished is by the use of dual-triangles that are mapped into the former and latter map, by having, in one exemplary aspect, the same vertices in both maps. Additional features, such as selection regions for regions to be converted or not converted are used. Furthermore, dual-triangle subdivision or aggregation techniques can be used to provide a desired mapping scenario. Finally, APIs are presented that allow developers and users of such mapping technology to implement the various aspects disclosed herein.

Claims

1. A system for distortionless conversion between a first space and a second space, comprising:

a processor, wherein the processor is adapted to;

(a) receive the first space and the second space, wherein the first space and second space each respectively comprises one of a linear and non-linear mapping of a plurality of points in a coordinate system;

(b) determine a mapping from points in the first space to points in the second space by;

(c) determining at least one first triangular region of the first mapping, wherein each first triangular region is defined by a first set of three vertices (A1, B1, C1);

(d) determining each of a plurality of corresponding second triangular regions in the second mapping corresponding respectively to each of the first triangular regions of the first mapping, wherein each triangular region in the second mapping is defined by a second set of three vertices (A2, B2, C2), wherein each of the second set of three vertices respectively corresponds identically in location to the first set of three vertices (A1, B1, C1);

(e) for each first triangular region, determining a first point (P1) associated with the region;

(f) determining a first vector associated with the first point (VA1P1), wherein the first vector is defined by the first point (P1) and a vertex (A1) of the associated triangular region;

(g) determining a second vector (V′

A1P1) from the first point to a side of the triangular region opposite the vertex, the second vector intersecting the side of the triangular region at a second point (P′

) so as to subdivide the side into a first segment (B1P′

) and a second segment (C1P′

);

(h) determining a first ratio of a length of the first vector (VA1P1) to a length of the second vector (V′

A1P1);

(i) determining a second ratio of a length of the first segment (B1P′

) to a length of the second segment (C1P′

);

(j) determining a third point (P2′

) on a side of the second triangular region opposing the vertex (A2) using the second ratio;

(k) determining a third vector (VA2P2) in the second triangular region using the first ratio, wherein the third vector is defined by the vertex (A2) and the third point (P2′

); and

(l) determining a fourth point in the second triangular region (P2) using the point (P2′

) and the third vector corresponding respectively to the first point in the first triangular region.

2. The system according to claim 1, wherein the first mapping is an image.

3. The system according to claim 1, wherein the second mapping is an image.

4. The system according to claim 1, wherein the first space is subdivided into a conversion region, wherein only the conversion region is mapped to the second space.

5. The system according to claim 4, wherein a region on the first space is configured to be designated as avoiding conversion from the first space to the second space.

6. The system according to claim 1, wherein the at least one first triangular region is further subdivided into a plurality of sub-triangular regions.

7. The system according to claim 1, wherein the first space and second space represent geographic information respectively mapped by a linear and non-linear mapping from latitude and longitude information.

8. A method for designing and using arbitrary maps, comprising:

determining by a computer processor on a first map image a first triangle defined by a first vertex, a second vertex, and a third vertex;

determining by a computer processor on a second map image a second triangle defined by the first vertex, the second vertex, and the third vertex;

displaying by a computer processor on a display surface simultaneously the first and second triangle;

determining by a computer processor at least one point in the first triangle; and

determining by a computer processor in the second triangle at least one corresponding point to the at least one point, wherein the at least one point is transformed into the at least one corresponding point symmetrically relative to the first vertex, the second vertex, and the third vertex, wherein the corresponding point is determined by;

computing a first ratio of a length of a first vector from the first vertex of the first triangle to the point and a length of a second vector from the point to a side of the triangle opposite the first vertex of the first triangle, the first and second vertexes being in alignment;

computing a second ratio of a length of a first portion of the opposite side to a second portion of the opposite side, the first and second portions determined by a bisecting of the opposite side by the second vector;

determining a point on a side of the second triangle opposing the first vertex of the second triangle using the second ratio;

determining a third vector in the second triangle using the first ratio, wherein the third vector is defined by the first vertex of the second triangle and the point on the side of the second triangle; and

determining a position of the corresponding point in the second triangle using the point on the side of the second triangle and the third vector in the second triangle.

9. The method according to claim 8, further comprising selecting a region on the first map image to be transformed into a corresponding region on the second map image.

10. The method according to claim 9, wherein the selecting of the region on the first map image includes the selecting of the first triangle.

11. The method according to claim 8, wherein the first and second map images are respectively one of a street map and a subway map.

12. The method according to claim 11, wherein the map images are a set of points mapped into respective spaces from latitude and longitude data.

13. The method according to claim 11, further comprising displaying error distortion information based upon the first and second triangles.

14. The method according to claim 13, further comprising receiving input regarding further subdividing the first and second triangles into respective first and second sub-triangles based upon the distortion information.

15. The method according to claim 14, wherein information regarding the first and second triangles and first and second sub-triangles are stored an XML file for use at runtime.

16. The method according to claim 8, wherein the first and second map images represent telecommunication grids.

17. The method according to claim 8, wherein the first and second map images represent transportation maps.

18. A computer readable medium bearing tangible executable instructions for designing and using arbitrary maps, comprising instructions for:

receiving a definition of a plurality of dual-triangles corresponding to a first map image and to a second map image, wherein the plurality of dual-triangles comprises first and second triangles in the first and second map images, respectively, wherein the first and second triangles each having a corresponding first vertex, second vertex, and third vertex, wherein the plurality of dual-triangles allow for symmetric transformation of data between the first map image and the second map image for selected regions on one of the first map image and the second map image, wherein at least one point and at least one corresponding point in the dual triangles is determined, and the at least one corresponding point is determined by;

computing a first ratio of a length of a first vector from the first vertex of the first triangle to the point and a length of a second vector from the point to a side of the triangle opposite the first vertex of the first triangle, the first and second vertexes being in alignment;

computing a second ratio of a length of a first portion of the opposite side to a second portion of the opposite side, the first and second portions determined by a bisecting of the opposite side by the second vector;

determining a point on a side of the second triangle opposing the first vertex of the second triangle using the second ratio;

determining a third vector in the second triangle using the first ratio, wherein the third vector is defined by the first vertex of the second triangle and the point on the side of the second triangle;

determining a position of the corresponding point in the second triangle using the point on the side of the second triangle and the third vector in the second triangle; and

displaying error distortion information based upon the first and second triangles.

19. The computer readable medium according to claim 18, wherein the plurality of dual-triangles are defined at design-time.

20. The computer readable medium according to claim 18, wherein the plurality of dual-triangles are defined at run-time.