Method and system of vectorial cartography

• US 6,873,943 B2
• Filed: 12/19/2001
• Issued: 03/29/2005
• Est. Priority Date: 03/13/2001
• Status: Expired due to Fees

• Current Assignee: Visteon Software Technologies
• Original Assignee: Visteon Software Technologies
• Inventors: Popovici, Lascar
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US10/020,965
• Publication Number:
  US 20030040893A1
• Time in Patent Office: 1,196 Days
• Field of Search: 703/2, 707/7, 707/100, 706/45, 345/619
• US Class Current: 703/2
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A method of retrieving an object contained in a domain δ within a space Δ containing a set of objects described in an initial matrix M, including construction of a subset ω of objects contained in the domain δ by extracting a matrix μ form the initial matrix M. A matrixing M of the space Δ is created by superimposing a large number of geometric matrices with different specifications ρ, each one of the meshes of each geometric matrix being identified by a unique and specific numerical value called a matrix code. The matrix M is sorted by matrix codes according to a predetermined order, with specifications ρ. Then the extraction matrix μ is constructed, describing only the objects affected by th meshes included in domain δ or intersected by domain δ.

Claims

1. A method of retrieving an object contained in a domain δ

within a space Δ

containing a set of objects described in an initial matrix M, comprising a construction of a subset ω

of objects contained in the said domain δ

by extraction of a matrix μ

from the initial matrix M, characterized in that it comprises the following steps;

creation of a matrixing M of the space Δ

by superimposing a number of geometric matrices with different specifications ρ

, representing coverage of the domain by a defined, homogeneous set of similar subdomains, each of the meshes of each geometric matrix being identified by a unique specific numerical value called the matrix code,

for the whole of the matrixing M, determination of all the meshes included in domain δ

or intersected by domain δ

, and the number of relevant objects as the sum of the numbers of objects of the relevant meshes,

sorting of matrix M by matrix codes following a predetermined order, increasing or decreasing, of the specifications ρ

, and

construction of the extraction matrix μ

describing just the objects affected by the said meshes included in domain δ

or intersected by domain δ

.

2. A method of retrieving an object according to claim 1, characterized in that the objects are sorted by increasing or decreasing matrix codes.

3. A method of retrieving an object according to claim 1, characterized in that it comprises in addition storage of a list of matrix codes with a pointer to the first object of each code.

4. A method of retrieving an object according to claim 1, characterized in that selection of the objects is effected by a cursor which passes through the list of matrix codes.

5. A method of retrieving an object according to claim 4, characterized in that, when the cursor encounters an active code, the said cursor then passes through the set of objects with that code, only the objects scanned by the said cursor being processed.

6. A method of retrieving an object according to claim 5, characterized in that the processing of the selected objects comprises a second sort to exclude from the said processing, those of the objects selected by the said cursor which do not necessarily intersect the domain δ

.

7. A method of retrieving an object according to claim 6, characterized in that the sort comprises reading of each object, then calculation of intersection with domain δ

.

8. A method of retrieving an object according to claim 1, characterized in that it comprises:

a first stage (1) comprising;

definition of a matrixing M, a sort of the objects of the set of objects of the set of the objects by increasing or decreasing order of their matrix code ∩

<sub>ρ

ij</sub>, with i=1, Π

(depth) and j=1, <sub>.ρ

i</sub> (number of the mesh in the grid of depth i),

definition of the matrixing M comprising selection of the grids;

sorting of the objects of the set by increasing or decreasing order of their matrix code ∩

<sub>ρ

ij</sub>, with i=1, Π

(depth) and j=1, <sub>.ρ

i</sub> (number of the mesh in the grid of depth i) and

a second stage (2) of searching for the v objects contained in the search domain δ

forming the subset ω

, comprising;

a search of the “

active”

meshes (active matrix codes), which are affected by the search domain δ

,

for each active matrix code ω

<sub>ρ

ij</sub>, a search of the corresponding objects and verification, for the said corresponding objects only, of membership of the search domain δ

.

9. A method of retrieving an object according to claim 1, characterized in that the stage (1) of the definition and sorting of objects is carried out once and for all in a data domain, the results of the said stage (1) of definition and sorting of objects being loaded into a reading device, and in that the search stage (2) is to be executed each time a search is requested.

10. A method of retrieving an object according to claim 9, characterized in that the search stage (2) is implemented in the form of an executable program stored within a user terminal.

11. A method of vectorial cartography, for mapping a territory Δ

comprising a set of objects described by a matrix M;

employing the method of object retrieval according to one of the preceding claims, characterized in that it comprises the following steps;

determination of the list of active meshes, comprising calculation of the set of matrix codes corresponding to the meshes that intersect the search domain δ

, and

selection of the objects and processing thereof if required.

12. A method of vectorial cartography according to claim 11, employed in a two-dimensional domain, characterized in that it comprises matrixing according to a large number of rectangular geometric matrices comprising regular meshes, each geometric matrix possessing a different specification including the length and the width of the meshes of the said matrix.

13. A method of vectorial cartography according to claim 11, employed in two-dimensional cartography extended to multiple levels, characterized in that it comprises the following sequences:

the initial set Ω

of N objects is broken down into a large number of Z subsets Ω

_ζ

of objects with the same level, with ζ

=1 to Z,

the initial matrix M is broken down into Z matrices M_ζ

,

matrixing is used independently for each subset.

14. Electronic apparatus, in particular equipment for communication and/or navigation, employing the method of vectorial cartography according to claim 11.

15. A data medium containing vectorial cartography data processed by the method of vectorial cartography according to claim 11.

16. A system of vectorial cartography, comprising means for processing objects contained in a domain δ

within a space Δ

containing a set of objects described in an initial matrix M, comprising construction of a subset ω

of objects contained in the said domain δ

by extraction of a matrix μ

from the initial matrix M, characterized in that it additionally comprises;

means for creating a matrixing M of the space Δ

by superimposing a large number of geometric matrices with different specifications ρ

, representing coverage of the domain with a defined, homogeneous set of similar subdomains, each one of the meshes of each geometric matrix being identified by unique specific index called a matrix code,

means for determining, for the whole of the matrixing M, all of the meshes included in domain δ

or intersected by domain δ and

the number of relevant objects as the sum of the numbers of objects of the relevant meshes,

means for sorting the matrix M by matrix codes according to a predetermined order, increasing or decreasing, of specifications ρ

, and

means for constructing the extraction matrix μ

describing only those objects affected by the said meshes included in domain δ

or intersected by domain δ

.