Method and system for determining shortest oceanic routes

A computer system for providing a shortest route from an initial location point X on a sphere to a destination location point Y on the sphere comprising:

• a first memory storing an oceanic database, where the oceanic database comprises a plurality of vertex points on the sphere, where each vertex point in the plurality of vertex points defines a point on a border of a single spherical polygon in a plurality of spherical polygons, where each border of the single spherical polygon in the plurality of spherical polygons surrounds an interior region associated with one obstacle in a plurality of obstacles on the sphere, where the interior region is an area of the sphere, such that a plurality of interior regions are present where each interior region in the plurality is associated with a single obstacle;
• a second memory storing a database of predetermined data, where the predetermined data comprises a matrix of inter-vertex distances, where the matrix of inter-vertex distances comprises a shortest route D(i,j) on the sphere from a given vertex i to a given vertex j and a sequence of vertexes associated with the shortest route D(i,j), where the given vertex i and the given vertex j are vertex points in the plurality of vertex points, and where the sequence of vertexes comprises one or more vertexes in the plurality of vertexes;
• a display device;
• an input device;
• and
• a processor in data communication with the first memory, the second memory, the display device, and the input device, and the processor configured to perform steps comprising:
• receiving the initial location point X and the destination location point Y from the input device, where the initial location X and the destination location Y are locations on the sphere;
• accessing the first memory and the oceanic database stored in the first memory and retrieving the plurality of vertex points and the plurality of interior regions;
• determining a visibility set Sx using the plurality of vertex points, where the visibility set Sx is a first set of vertex points in the plurality of vertex points, and where for each vertex point i in the first set of vertex points, an arc segment Xi on the sphere connects the initial location X and the each vertex point i, where the arc segment Xi is a segment of a first great circle of the sphere, and where the arc segment Xi does not intersect one or more interior regions in the plurality of interior regions, and where all vertex points in the plurality of vertex points having the arc segment Xi are included in the visibility set Sx;
• determining a plurality of chains, where each chain in the plurality of chains comprises a group of vertexes, where the group of vertexes comprises the border of one spherical polygon in the plurality of spherical polygons, and where the each vertex in the group of vertexes is one of the first set of vertex points in the visibility set Sx;
• determining if the destination location point Y is visible from the initial location point X by defining an arc segment XY on the sphere, where the arc segment XY is the shortest path on the sphere from the initial location point X to the destination location point Y such that the arc segment XY is a segment of a second great circle of the sphere, where the second great circle may be a great circle identical to the first great circle, and determining if the arc segment XY intersects one or more chains in the plurality of chains, and if the arc segment XY does not intersect one or more chains in the plurality of chains, determining that the destination location point Y is visible from the initial location point X, and if the arc segment XY does intersect one or more chains in the plurality of chains, determining that the destination location point Y is not visible from the initial location point X;
• defining, if the destination location point Y is visible from the initial location point X, the arc segment XY as the shortest route from the initial location point X to the destination location point Y, thereby determining the shortest route from the initial location point X on the sphere to the destination location point Y on the sphere;
• and
• calculating, if the destination point Y is not visible from the initial location point X, the shortest route from the initial location point X on the sphere to the destination location point Yon the sphere by performing steps comprising:
• determining a visibility set Sy using the plurality of vertex points, where the visibility set Sy is a second set of vertex points in the plurality of vertex points, and where for each vertex point j in the second set of vertex points, an arc segment Yj on the sphere connects the initial location Y and the each vertex point j, where the arc segment Yj is a segment of a third great circle of the sphere, where the third great circle may be a great circle identical to the second great circle or the first great circle, and where the arc segment Yj does not intersect one or more interior regions in the plurality of interior regions, and where all vertex points in the plurality of vertex points having the arc segment Yj are included in the visibility set Sy;
• selecting an initial vertex point in the visibility set Sx;
• choosing an initial vertex point in the visibility set Sy;
• establishing a distance d(X,i) from the initial location point X to the initial vertex point in the visibility set Sx, where the distance d(X,i) is a length of the arc segment Xi from the initial location point X to the initial vertex point in the visibility set Sx;
• designating a distance d(j,Y) from the destination location point Y to the initial vertex point in the visibility set Sy, where the distance d(j,Y) is a length of the arc segment Xj from the initial location point Y to the initial vertex point in the visibility set Sy;
• accessing the second memory and the database of predetermined data stored in the second memory, and retrieving the shortest distance D(i,j) from the initial vertex point in the visibility set Sy, to the initial vertex point in the visibility set Sy and retrieving the sequence of vertexes associated with the shortest distance D(i,j) from the initial vertex point in the visibility set Sx to the initial vertex point in the visibility set Sy;
• quantifying a D(X,Y) where the D(X,Y) is equal to the distance d(X,i) added to the shortest distance D(i,j) added to the distance d(j,Y), and associating the D(X,Y) with the initial vertex point in the visibility set Sx and the initial vertex point in the visibility set Sy;
• picking a subsequent vertex point in the visibility set Sx and a subsequent vertex point in the visibility set Sy and repeating the selecting, the choosing, the establishing, the designating, the accessing, and the quantifying steps using the subsequent vertex point in the visibility set Sx as the initial vertex point in the visibility set Sx and using the subsequent vertex point in the visibility set Sy as the initial vertex point in the visibility set Sy until every vertex point in the visibility set Sx has been utilized as the initial vertex point in the visibility set Sx and every vertex point in the visibility set Sy has been utilized as the initial vertex point in the visibility set Sy, thereby generating one or more D(X,Y);
• and
• determining a minimum D(X,Y) from the one or more D(X,Y) and designating the initial location X, the sequence of vertexes associated with the shortest distance D(i,j) comprising the minimum D(X,Y), and the destination location point Y as the shortest oceanic route from the initial location point X to the destination location point Y, thereby determining the shortest route from the initial location point X on the sphere to the destination location point Y on the sphere;
• communicating with the display device to display the shortest oceanic route from the initial location point X on the sphere to the destination location point Y on the sphere, thereby providing the shortest oceanic route from the initial location point X on the sphere to the destination location point Y on the sphere.

A non-transitory computer readable medium having stored therein instructions executable by a processor to cause the processor to perform functions of:

• receiving an initial location point X and a destination location point Y from an input device, where the initial location X and the destination location Y are locations on a sphere;
• accessing a first memory in data communication with the processor where the first memory stores an oceanic database, where the oceanic database comprises a plurality of vertex points on the sphere, where each vertex point in the plurality of vertex points defines a point on a border of a single spherical polygon in a plurality of spherical polygons, where each border of the single spherical polygon in the plurality of spherical polygons surrounds an interior region associated with one obstacle in a plurality of obstacles on the sphere, where the interior region is an area of the sphere, such that a plurality of interior regions are present where each interior region in the plurality is associated with a single obstacle;
• retrieving the plurality of vertex points and the plurality of interior regions;
• determining a visibility set Sx using the plurality of vertex points, where the visibility set Sx is a first set of vertex points in the plurality of vertex points, and where for each vertex point i in the first set of vertex points, an arc segment Xi on the sphere connects the initial location X and the each vertex point i, and the arc segment Xi does not intersect one or more interior regions in the plurality of interior regions, and where all vertex points in the plurality of vertex points having the arc segment Xi are included in the visibility set Sx;
• determining a plurality of chains, where each chain in the plurality of chains comprises a group of vertexes, where the group of vertexes comprises the border of one spherical polygon in the plurality of spherical polygons, and where the each vertex is one of the first set of vertex points in the visibility set Sx;
• determining if the destination location point Y is visible from the initial location point X by defining an arc segment XY on the sphere, where the arc segment XY is the shortest path on the sphere from the initial location point X to the destination location point Y, and determining if the arc segment XY intersects one or more chains in the plurality of chains, and if the arc segment XY does not intersect one or more chains in the plurality of chains, determining that the destination location point Y is visible from the initial location point X, and if the arc segment XY does intersect one or more chains in the plurality of chains, determining that the destination location point Y is not visible from the initial location point X;
• defining, if the destination location point Y is visible from the initial location point X, the arc segment XY as the shortest route from the initial location point X to the destination location point Y, thereby determining the shortest route from the initial location point X on the sphere to the destination location point Y on the sphere;
• and
• calculating, if the destination point Y is not visible from the initial location point X, the shortest route by performing steps comprising:
• determining a visibility set Sy using the plurality of vertex points, where the visibility set Sy is a second set of vertex points in the plurality of vertex points, and where for each vertex point j in the second set of vertex points, an arc segment Yj on the sphere connects the initial location Y and the each vertex point j, and the arc segment Yj does not intersect one or more interior regions in the plurality of interior regions, and where all vertex points in the plurality of vertex points having the arc segment Yj are included in the visibility set Sy;
• selecting an initial vertex point in the visibility set Sx;
• choosing an initial vertex point in the visibility set Sy;
• establishing a distance d(X,i) from the initial location point X to the initial vertex point in the visibility set Sx, where the distance d(X,i) is a length of the arc segment Xi from the initial location point X to the initial vertex point in the visibility set Sx;
• designating a distance d(j,Y) from the destination location point Y to the initial vertex point in the visibility set Sy, where the distance d(j,Y) is a length of the arc segment Yj from the initial location point Y to the initial vertex point in the visibility set Sy;
• accessing a second memory in data communication with the processor, where the second memory stores a database of predetermined data, where the predetermined data comprises a matrix of inter-vertex distances, where the matrix of inter-vertex distances comprises a shortest route D(i,j) on the sphere from a given vertex i to a given vertex j and a sequence of vertexes associated with the shortest route D(i,j), where the given vertex i and the given vertex j are vertex points in the plurality of vertex points, and where the sequence of vertexes comprises one or more vertexes in the plurality of vertexes, and retrieving the shortest route D(i,j) from the initial vertex point in the visibility set Sx to the initial vertex point in the visibility set Sy and retrieving the sequence of vertexes associated with the shortest route D(i,j) from the initial vertex point in the visibility set Sx to the initial vertex point in the visibility set Sy;
• quantifying a D(X,Y) where the D(X,Y) is equal to the distance d(X,i) added to the shortest route D(i,j) added to the distance d(j,Y), and associating the D(X,Y) with the initial vertex point in the visibility set Sx and the initial vertex point in the visibility set Sy;
• picking a subsequent vertex point in the visibility set Sx and a subsequent vertex point in the visibility set Sy and repeating the selecting, the choosing, the establishing, the designating, the accessing, and the quantifying steps using the subsequent vertex point in the visibility set Sx as the initial vertex point in the visibility set Sx and using the subsequent vertex point in the visibility set Sy as the initial vertex point in the visibility set Sy until every vertex point in the visibility set Sx has been utilized as the initial vertex point in the visibility set Sx and every vertex point in the visibility set Sy has been utilized as the initial vertex point in the visibility set Sy, thereby generating one or more D(X,Y);
• and
• determining a minimum D(X,Y) from the one or more D(X,Y) and designating the initial location X, the sequence of vertexes associated with the shortest distance D(i,j) comprising the minimum D(X,Y), and the destination location point Y as the shortest oceanic route from the initial location point X to the destination location point Y, thereby determining the shortest route from the initial location point X on the sphere to the destination location point Y on the sphere;
• communicating with a display device to display the shortest route from the initial location point X on the sphere to the destination location point Y on the sphere, thereby providing the shortest route from the initial location point X on the sphere to the destination location point Y on the sphere.