Robust Free Space Computation for Curved Planar Bodies
Victor Milenkovic, Elisha P. Sacks, Steven Trac · IEEE Transactions on Automation Science and Engineering · 2013
We present a free space computation algorithm for two planar bodies bounded by line segments and circular arcs. The computational complexity is O(((mn)2+k)log(mn)) with m and n the number of boundary curves of the two bodies, and with k the number of configurations with three pairs of curves in contact. Although k is in O((mn)3), mild input restrictions reduce it to O(mn). We develop a robust implementation that is accurate, is fast, and handles degenerate input.