Envolvent approximation using accurate slope information

Abstract

A trajectory and a footprint of a hypothetical pen are each divided into sequences of segments, each segment having a slope associated therewith. The segments of the footprint form a closed sequence and those of the trajectory form a sequence with a beginning and an end. Each of the two approximate envolvents of the thick line are calculated in the same way, from the trajectory segments and the footprint segments. An envolvent is initialized to include the first segment of the trajectory starting at an appropriate offset from the trajectory start point, followed by zero or more footprint segments and then followed by the next trajectory segment until each of the trajectory segments are concatenated. In determining how many footprint segments to concatenate before concatenating the next trajectory segment, the slopes of the last concatenated trajectory segment and the next trajectory segment are compared to the slopes of the footprint segments. If any footprint segments have slopes between the slopes of the last and next trajectory segments, those footprint segments are concatenated before the next trajectory segment is concatenated. The selection of one of the two sets of footprint slope vectors, either the clockwise set or the counterclockwise set, determines which envolvent of the two envolvents are generated.