Method for Labeling Segments of Paths as Interior or Exterior

摘要

A method for labeling a segment of a two-dimensional input path defined according to a nonzero winding rule as either interior or exterior is described. A winding number is initialized. A scan line that intersects the segment is identified. For each contour of the input path, winding values are accumulated into the winding number for any segments of the contour that cross the identified scan line, where the accumulation for coincident segments that cross the identified scan line at a same location as the segment is postponed. These coincident segments are marked and saved in a list. The labeling of the segment as either interior or exterior is determined from the list and the winding number.

主权项

1. A method for labeling a segment of an input path as either interior or exterior, wherein the input path is defined according to a nonzero winding rule in a two-dimensional (2D) coordinate system, the input path includes a set of contours, and wherein each contour includes a sequence of segments, comprising the steps of:
initializing a winding number to zero; identifying a scan line that intersects the segment; accumulating, for each contour, winding values into the winding number for any segments of the contour that cross the scan line, wherein the accumulation for coincident segments of the contour that cross the scan line at a same location as the segment is postponed until after all the contours have been processed, and wherein the coincident segments are marked, and wherein the marked coincident segments are saved in a list; labeling the segment as interior if the list is empty and the winding number is not zero and the winding number when updated to account for the segment is not zero; labeling the segment as exterior if the list is empty and either the winding number is zero or the winding number when updated to account for the segment is zero; labeling the segment as interior if the list is not empty and, after canceling out pairs of segments of the list that have opposite directions, the list is augmented to contain the segment, and accumulating the winding values into the winding number for any remaining non-cancelled segments in the list excluding the segment, the winding number is not zero and the winding number when updated to account for the segment is not zero; and labeling the segment as exterior if the list is not empty and, after canceling out pairs of segments of the list that have opposite directions, the list is augmented to contain the segment, and accumulating the winding values into the winding number for the remaining non-cancelled segments in the list excluding the segment, either the winding number is zero or the winding number when updated to account for the segment is zero, wherein the steps are performed in a processor.