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 200–300 times speed up compared with the previous results (Elber et al., 2001) [8].

Figure optionsDownload high-quality image (88 K)Download as PowerPoint slideHighlights
► We present an efficient real-time algorithm for computing the precise convex hulls for planar freeform curves with G1-biarc approximation.
► 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.