Finding a hexagonal cell containing an X, Y position

• US 20070005550A1
• Filed: 06/24/2005
• Published: 01/04/2007
• Est. Priority Date: 06/24/2005
• Status: Abandoned Application

• Current Assignee: Alexander Klein
• Original Assignee: Alexander Klein
• Inventors: Klein, Alexander
• Application Number:
  US11/165,252
• Publication Number:
  US 20070005550A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G08G 5/0095 Aspects of air-traffic control not provided for in the other subgroups of this main group

Abstract

Disclosed is a mechanism for partitioning an area such as airspace. An area of interest may be overlaid with a grid such as a hexagonal grid. Data related to a metric may be collected in the area of interest. A cell location is then determined for each piece of data. A metric value is then calculated for cells in the grid using the data. Then sub-areas, consisting of one or more cells, may be grown by appending adjacent cells in an attempt to equalize the total metric value between sub-areas.

Claims

1. A tangible computer-readable medium encoded with a computer program, wherein execution of said “

computer program”

by one or more processors causes said “

one or more processors”

to execute the steps of;

a) creating a rectangular grid, said “

rectangular grid”

containing at least two rectangular cells arranged in rows and columns;

b) locating an encapsulating rectangular cell for at least one x,y position using a rectangular cell location mechanism, said “

encapsulating rectangular cell”

containing said “

x,y position;

”

c) generating a hexagonal grid from said “

rectangular grid,”

said “

hexagonal grid”

containing a multitude of hexagonal cells;

d) locating a hexagonal cell triplet containing said “

x,y position”

using said “

encapsulating rectangular cell” and

a rectangular cell to hexagonal cell triplet conversion mechanism; and

e) locating an encapsulating hexagonal cell using said “

hexagonal cell triplet” and

a hexagonal cell triplet to hexagonal cell conversion mechanism;

said “

encapsulating hexagonal cell”

containing said “

x,y position;

”

wherein said “

hexagonal grid” and

said “

rectangular grid”

cover a geographical map area and said “

hexagonal cell triplet”

consists of three adjacent hexagonal cells.

3. A tangible computer-readable medium according to claim 1, wherein at least one of said “

at least one x,y position”

is a reported location of an aircraft.

4. A tangible computer-readable medium according to claim 1, wherein said “

rectangular cell location mechanism”

locates said “

encapsulating rectangular cell”

for said “

x,y position”

by;

a) determining the column in which said “

encapsulating rectangular cell”

is located by dividing the difference of “

x”

belonging to said “

x,y position” and

the westernmost extent of said “

rectangular grid”

by the width of said “

rectangular cells;

” and

b) determining the row in which said “

encapsulating rectangular cell”

is located by dividing the difference of “

y”

belonging to said “

x,y position” and

the southernmost extent of said “

rectangular grid”

by the height of said “

rectangular cells.

5. A tangible computer-readable medium according to claim 1, wherein said “

rectangular cell to hexagonal cell triplet conversion mechanism”

is applied to said “

encapsulating rectangular cell” and

identifies said “

hexagonal cell triplet”

as either an odd type hexagonal cell triplet or an even type hexagonal cell triplet.

6. A tangible computer-readable medium according to claim 5, wherein:

a) said “

odd type hexagonal cell triplet”

includes;

i) a leftmost hexagonal cell, the center of said leftmost hexagonal cell located in the middle of the west edge of said “

encapsulating rectangular cell;

”

ii) an upper right hexagonal cell, the center of said upper right hexagonal cell located in the northeast corner of said “

encapsulating rectangular cell;

” and

iii) a lower right hexagonal cell, the center of said lower right hexagonal cell located in the southeast corner of said “

encapsulating rectangular cell;

” and

b) said “

even type hexagonal cell triplet”

includes;

i) a rightmost hexagonal cell, the center of said rightmost hexagonal cell located in the middle of the east edge of said “

encapsulating rectangular cell;

”

ii) an upper left hexagonal cell, the center of said upper left hexagonal cell located in the northwest corner of said “

encapsulating rectangular cell;

” and

iii) a lower left hexagonal cell, the center of said lower left hexagonal cell located in the southwest corner of said “

encapsulating rectangular cell.”

7. A tangible computer-readable medium according to claim 6, wherein said “

hexagonal cell triplet to hexagonal cell conversion mechanism”

includes the steps of;

a) if said “

x,y position”

is determined to be within said “

odd type hexagonal cell triplet,”

then;

i) subdividing said “

encapsulating rectangular cell”

located in said “

hexagonal cell triplet”

into;

(1) a left rectangular sub-cell;

(2) a right rectangular sub-cell; and

(3) a center rectangular sub-cell;

ii) setting said “

leftmost hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be within said “

left rectangular sub-cell;

”

iii) setting said “

upper right hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within said “

right rectangular sub-cell;

” and

(2) within the upper half of said “

right rectangular sub-cell;

”

iv) setting said “

lower right hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within said “

right rectangular sub-cell;

” and

(2) within the lower half of said “

right rectangular sub-cell;

”

v) setting said “

leftmost hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within said “

center rectangular sub-cell;

”

(2) within the lower side of said “

center rectangular sub-cell;

” and

(3) within said “

leftmost hexagonal cell;

”

vi) setting said “

lower right hexagonal cell”

as the said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be within;

(1) within said “

center rectangular sub-cell;

”

(2) within the lower side of said “

center rectangular sub-cell;

” and

(3) within said “

lower right hexagonal cell;

”

vii) setting said “

leftmost hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within the upper side of said “

center rectangular sub-cell;

” and

(2) within said “

leftmost hexagonal cell”

viii) setting said “

upper right hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within the upper side of said “

center rectangular sub-cell;

” and

(2) within said “

upper right hexagonal cell,” and

b) if said “

x,y position”

is determined to be within said “

even type hexagonal cell triplet,”

then;

i) subdividing said “

corresponding rectangular cell”

located in said “

hexagonal cell triplet”

into;

(1) a left rectangular sub-cell;

(2) a right rectangular sub-cell; and

(3) a center rectangular sub-cell;

ii) setting said “

rightmost hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be within said “

right rectangular sub-cell;

”

iii) setting said “

upper left hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within said “

left rectangular sub-cell;

” and

(2) within the upper half of said “

left rectangular sub-cell;

”

iv) setting said “

lower left hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within said “

left rectangular sub-cell;

” and

(2) within the lower half of said “

left rectangular sub-cell;

”

v) setting said “

rightmost hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within said “

center rectangular sub-cell;

”

(2) within the lower side of said “

center rectangular sub-cell;

” and

(3) within said “

rightmost hexagonal cell;

”

vi) setting said “

lower left hexagonal cell”

as the said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be within;

(1) within said “

center rectangular sub-cell;

”

(2) within the lower side of said “

center rectangular sub-cell;

” and

(3) within said “

lower left hexagonal cell;

”

vii) setting said “

rightmost hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within the upper side of said “

center rectangular sub-cell;

” and

(2) within said “

rightmost hexagonal cell” and

viii) setting said “

upper left hexagonal cell”

as said “

encapsulating hexagonal cell if said “

x,y position”

is determined to be;

(1) within the upper side of said “

center rectangular sub-cell;

” and

(2) within said “

upper left hexagonal cell.”

8. A tangible computer-readable medium according to claim 1, wherein said “

rectangular grid”

is created to a determined size and grid spacing.

9. A tangible computer-readable medium according to claim 1, wherein said “

hexagonal cell triplet”

is comprised of three adjacent said “

hexagonal cells.”

2. Wherein said “

hexagonal grid”

or said “

rectangular grid”

are not regular.

10. A tangible apparatus comprising:

a) a rectangular grid creator, said “

rectangular grid creator”

configured to create a rectangular grid, said “

rectangular grid”

containing at least two rectangular cells arranged in rows and columns;

b) an encapsulating rectangular cell locator, said “

encapsulating rectangular cell locator”

configured to locate an encapsulating rectangular cell for at least one x,y position using a rectangular cell location mechanism, said “

encapsulating rectangular cell”

containing said “

x,y position;

”

c) a hexagonal grid generator, said “

hexagonal grid generator”

configured to generate a hexagonal grid from said “

rectangular grid,”

said “

hexagonal grid”

containing a multitude of hexagonal cells;

d) a hexagonal cell triplet locator, said “

hexagonal cell triplet locator”

configured to locate a hexagonal cell triplet containing said “

x,y position”

using said “

encapsulating rectangular cell” and

a rectangular cell to hexagonal cell triplet conversion mechanism; and

e) an encapsulating hexagonal cell locator, said “

encapsulating hexagonal cell locator”

configured to locate an encapsulating hexagonal cell using said “

hexagonal cell triplet” and

a hexagonal cell triplet to hexagonal cell conversion mechanism;

said “

encapsulating hexagonal cell”

containing said “

x,y position;

”

wherein said “

hexagonal grid” and

said “

rectangular grid”

cover a geographical map area and said “

hexagonal cell triplet”

consists of three adjacent hexagonal cells,.

11. A tangible apparatus according to claim 10, wherein at least one of said “

at least one x,y position”

is a reported location of an aircraft.

12. A tangible apparatus according to claim 10, wherein said “

rectangular cell location mechanism”

locates said “

encapsulating rectangular cell”

for said “

x,y position”

by;

a) determining the column in which said “

encapsulating rectangular cell”

is located by dividing the difference of “

x”

belonging to said “

x,y position” and

the westernmost extent of said “

rectangular grid”

by the width of said “

rectangular cells;

” and

b) determining the row in which said “

encapsulating rectangular cell”

is located by dividing the difference of “

y”

belonging to said “

x,y position” and

the southernmost extent of said “

rectangular grid”

by the height of said “

rectangular cells.

13. A tangible apparatus according to claim 10, wherein said “

rectangular cell to hexagonal cell triplet conversion mechanism”

is applied to said “

encapsulating rectangular cell” and

identifies said “

hexagonal cell triplet”

as either an odd type hexagonal cell triplet or an even type hexagonal cell triplet.

14. A tangible apparatus according to claim 13, wherein:

a) said “

odd type hexagonal cell triplet”

includes;

i) a leftmost hexagonal cell, the center of said leftmost hexagonal cell located in the middle of the west edge of said “

encapsulating rectangular cell;

”

ii) an upper right hexagonal cell, the center of said upper right hexagonal cell located in the northeast corner of said “

encapsulating rectangular cell;

” and

iii) a lower right hexagonal cell, the center of said lower right hexagonal cell located in the southeast corner of said “

encapsulating rectangular cell;

” and

b) said “

even type hexagonal cell triplet”

includes;

i) a rightmost hexagonal cell, the center of said rightmost hexagonal cell located in the middle of the east edge of said “

encapsulating rectangular cell;

”

ii) an upper left hexagonal cell, the center of said upper left hexagonal cell located in the northwest corner of said “

encapsulating rectangular cell;

” and

iii) a lower left hexagonal cell, the center of said lower left hexagonal cell located in the southwest corner of said “

encapsulating rectangular cell.”

15. A tangible apparatus according to claim 14, wherein said “

hexagonal cell triplet to hexagonal cell conversion mechanism”

includes the steps of;

a) if said “

x,y position”

is determined to be within said “

odd type hexagonal cell triplet,”

then;

i) subdivide said “

encapsulating rectangular cell”

located in said “

hexagonal cell triplet”

into;

(1) a left rectangular sub-cell;

(2) a right rectangular sub-cell; and

(3) a center rectangular sub-cell;

ii) if said “

x,y position”

is determined to be within said “

left rectangular sub-cell,”

then set said “

leftmost hexagonal cell”

as said “

encapsulating hexagonal cell;

”

iii) if said “

x,y position”

is determined to be within said “

right rectangular sub-cell,”

then;

(1) if said “

x,y position”

is determined to be within the upper half of said “

right rectangular sub-cell,”

then set said “

upper right hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(2) if said “

x,y position”

is determined to be within the lower half of said “

right rectangular sub-cell,”

then set said “

lower right hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

iv) if said “

x,y position”

is determined to be within said “

center rectangular sub-cell,”

then;

(1) if said “

x,y position”

is determined to be within the lower side of said “

center rectangular sub-cell,”

then;

(a) if said “

x,y position”

is determined to be within said “

leftmost hexagonal cell”

then set said “

leftmost hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(b) if said “

x,y position”

is determined to be within said “

lower right hexagonal cell”

then set said “

lower right hexagonal cell”

as the said “

encapsulating hexagonal cell;

” and

(2) if said “

x,y position”

is determined to be within the upper side of said “

center rectangular sub-cell,”

then;

(a) if said “

x,y position”

is determined to be within said “

leftmost hexagonal cell”

then set said “

leftmost hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(b) if said “

x,y position”

is determined to be within said “

upper right hexagonal cell”

then set said “

upper right hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

b) if said “

x,y position”

is determined to be within said “

even type hexagonal cell triplet,”

then;

i) subdivide said “

corresponding rectangular cell”

located in said “

hexagonal cell triplet”

into;

(1) a left rectangular sub-cell;

(2) a right rectangular sub-cell; and

(3) a center rectangular sub-cell;

ii) if said “

x,y position”

is determined to be within said “

right rectangular sub-cell,”

then set said “

rightmost hexagonal cell”

as said “

encapsulating hexagonal cell;

”

iii) if said “

x,y position”

is determined to be within said “

left rectangular sub-cell,”

then;

(1) if said “

x,y position”

is determined to be within the upper half of said “

left rectangular sub-cell,”

then set said “

upper left hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(2) if said “

x,y position”

is determined to be within the lower half of said “

left rectangular sub-cell,”

then set said “

lower left hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

iv) if said “

x,y position”

is determined to be within said “

center rectangular sub-cell,”

then;

(1) if said “

x,y position”

is determined to be within the lower side of said “

center rectangular sub-cell,”

then

(a) if said “

x,y position”

is determined to be within said “

rightmost hexagonal cell”

then set said rightmost hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(b) if said “

x,y position”

is determined to be within said “

lower left hexagonal cell”

then set said “

lower left hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(2) if said “

x,y position”

is determined to be within the upper side of said “

center rectangular sub-cell,”

then

(a) if said “

x,y position”

is determined to be within said “

rightmost hexagonal cell”

then set said “

rightmost hexagonal cell”

as said “

encapsulating hexagonal cell;

” and

(b) if said “

x,y position”

is determined to be within said “

upper left hexagonal cell”

then set said “

upper left hexagonal cell”

as said “

encapsulating hexagonal cell.”

16. A tangible apparatus according to claim 10, wherein said “

rectangular grid”

is created to a determined size and grid spacing.

17. A tangible apparatus according to claim 10, wherein said “

hexagonal cell triplet”

is comprised of three adjacent said “

hexagonal cells.”