Efficient convex hull computation for planar freeform curves
We present an efficient real-time algorithm for computing the precise convex hulls of planar freeform curves. For this purpose, the planar curves are initially approximated with G1-biarcs within a given error bound ? ? in a preprocessing step. The algorithm is based on an efficient construction of approximate convex hulls using circular arcs. The majority of redundant curve segments can be eliminated using simple geometric tests on circular arcs. In several experimental results, we demonstrate the effectiveness of the proposed approach, which shows the performance improvement in the range of 200300 times speed up compared with the previous results (Elber et al., 2001) [8].
convex hull planar freeform curves biarcs efficient algorithm culling upper envelope