AutoMovie API
    Preparing search index...

    Function solveAutoMovieHalfPlaneProgram

    • The point of a disc nearest a preferred point that satisfies a set of half-planes in the plane, or, when no point satisfies them all, the point of the disc that violates the worst of them least: the two- and three-dimensional linear programs of optimal reciprocal collision avoidance (van den Berg, Guy, Lin and Manocha 2011, Reciprocal n-body collision avoidance, Robotics Research, Springer Tracts in Advanced Robotics 70, sections 5.2 and 5.3).

      A half-plane is a directed line, a point and a unit direction; a point v lies inside it when det(direction, point - v) <= 0, on the direction's left. The program is solved incrementally, the half-planes added in their given order (Seidel's randomised incremental algorithm in its deterministic order, which keeps the result reproducible): while the current optimum satisfies the next half-plane it stays; otherwise the new optimum lies on that half-plane's line and is found by a one-dimensional program along it against the earlier half-planes and the disc. When that fails, the three-dimensional program takes the point of the disc whose greatest signed distance into the violated half-planes is least, by the same incremental method on the projected half-planes of the planes that bound it.

      The first hard half-planes stay hard in that fallback: the paper's obstacle half-planes, which the projected programs carry unchanged while only the later ones are relaxed. When the hard half-planes leave no point of the disc between them, every half-plane is relaxed alike.

      Parameters

      Returns IAutoMovieSolveHalfPlaneProgram.IResult

      The point found, and whether every half-plane holds at it.

      When the radius is not positive and finite, hard is not a whole count within the half-planes, a direction is not a unit vector, or a value is not finite: a caller's defect.