Systems and methods for four-dimensional routing around concave polygon avoidances

A navigation route generator, comprising:

• one or more processors;
• and
• a non-transient computer-readable medium storing processor- executable instructions which, when executed by the one or more processors, cause the one or more processors to:
• maintain, in a navigation database, four-dimensional data corresponding to a plurality of cells into which the four-dimensional data is divided, each cell representing a three-dimensional space from a start time to an end time;
• receive an avoidance corresponding to four-dimensional data;
• generate a concave polygon representing the avoidance at the start time, the concave polygon including a plurality of edges, by assigning a vector to each edge from a first vertex of the edge to a second vertex of the edge;
• identify a displacement vector corresponding to movement of the avoidance;
• identify, based on the displacement vector, at least one leading edge and at least one trailing edge of the concave polygon at the start time;
• shift each leading edge from the start time to the end time using the displacement vector;
• identify each gap between vertices of the plurality of edges of the at least one trailing edge and the shifted at least one leading edge;
• add an added edge to the plurality of edges of the concave polygon to connect vertices across each identified gap;
• determine, for each edge of the plurality of edges of the concave polygon, if the edge includes an internal edge;
• remove each internal edge from the concave polygon;
• compare the concave polygon to the plurality of cells;
• identify one or more cells in which the concave polygon is located;
• and output a navigation alert based on the identified one or more cells.

A method, comprising:

• maintaining, by a navigation database, four-dimensional data corresponding to a plurality of cells into which the four-dimensional data is divided, each cell representing a three-dimensional space from a start time to an end time;
• receiving, by a route generator, an avoidance corresponding to the four-dimensional data;
• generating, by the route generator, a concave polygon representing the avoidance at the start time, the concave polygon including a plurality of edges;
• identifying, by the route generator, a displacement vector corresponding to movement of the avoidance;
• identifying, by the route generator based on the displacement vector, at least one leading edge at the start time, the at least one leading edge having a first edge direction that crosses a direction of the displacement vector in a first direction across the displacement vector, the at least one trailing edge having a second edge direction that crosses the direction of the displacement vector in a second direction opposite the first direction;
• shifting, by the route generator, each leading edge from the start time to the end time using the displacement vector;
• identifying, by the route generator, each gap between vertices of the plurality of edges of the at least one trailing edge and the shifted at least one leading edge;
• adding, by the route generator, an added edge to the plurality of edges of the concave polygon to connect vertices across each identified gap;
• determining, by the route generator, for each edge of the plurality of edges of the concave polygon, if the edge includes an internal edge;
• removing, by the route generator, each internal edge from the concave polygon;
• comparing, by the route generator, the concave polygon to the plurality of cells;
• identifying, by the route generator, one or more cells in which the concave polygon is located;
• and
• outputting, by the route generator, a navigation alert based on the identified one or more cells.