Patent ID: 9541401
Date: 2017-01-10
CPC Classifications: G01C

Claim:
1. A computer system for determining 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 retrieve the plurality of vertex points and the plurality of interior regions; determining a set of one or more vertexes i visible from the initial location point X, where for each vertex point i in the set of one or more vertexes i, an arc segment Xi on the sphere connects the initial location X and the each vertex point i, 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 set of one or more vertexes i; 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 every vertex comprising the group of vertexes is one of the one or more vertexes i visible from the initial location point X; 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; calculating, if the destination point Y is not visible from the initial location point X, the shortest route by: determining a set of one or more vertexes j visible from the destination location point Y, where for each vertex point j in the set of one or more vertexes j, an arc segment Yj on the sphere connects the initial location Y and the each vertex point j, 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 set of one or more vertexes j; determining the shortest route associated with the minimal distance from the initial location point X to the final location point Y by calculating distances from the initial location point X to every vertex point i in the set of one or more vertexes i, calculating distances from every vertex point j in the set of one or more vertexes j to the destination location point Y, and accessing the second memory and the database of predetermined data stored in the second memory to determine the shortest route D(i,j) from the every vertex point i in set of one or more vertexes i to the every vertex point j in set of one or more vertexes j and to determine the associated sequence of vertexes associated with the shortest route D(i,j); and communicating with the display device to display the shortest route on the display device.