PolyCARP: Algorithms and Software for Computations with Polygons(LAR-18798-1)

PolyCARP is a package of algorithms, including both their formal models and software implementations, for computing containment, collision, resolution, and recovery information for polygons. The intended applications of PolyCARP are related, but not limited, to safety critical systems in air traffic management. One application is weather avoidance. A weather cell can be approximated by a polygon, and PolyCARP provides algorithms to detect whether a trajectory will intersect such a polygon in the near future and will provide maneuver guidance to avoid the polygon. If the trajectory is inside the polygon at the current time, PolyCARP provides algorithms for maneuver guidance to exit the polygon. Another application is ensuring that an aircraft stays inside a predetermined safety region, also known as assured containment, and PolyCARP provides algorithms that ensure that a point is inside or outside a particular polygonal region. Another application is obstacle avoidance by an aircraft. There are several functionalities provided by PolyCARP. There are algorithms to insure that a point is contained in or excluded from a polygon. There are also collision detection algorithms that determine if a moving point intersects a polygon, including the case where the polygon is moving or even warping over time, as well as where the polygon and the point are following piecewise linear trajectories. There are algorithms that resolve potential collisions between and point and a polygon by providing collision-free trajectories, and there are algorithms that compute new trajectories to regain separation from a polygon.