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.
The point found, and whether every half-plane holds at it.
Throws
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.
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
vlies inside it whendet(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
hardhalf-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.