A pair-wise offset algorithm for 2D point-sequence curve

Abstract

Presented in the paper is an efficient pair-wise offset algorithm for closed 2D point-sequence curves (PS-curve). A key feature of the proposed algorithm is that all local invalid loops are removed from the input PS-curve before constructing a raw offset-curve, by invoking a pair-wise interference-detection (PWID) test. In the PWID test, each pair of elementary offset segments is tested for interference and then interfering segments are successively removed. The proposed, algorithm has been implemented and tested with various PS-curves. Empirical tests show that the proposed PS-curve offsetting method is vary fast and robust with a near O(n) time-complexity, where n is the number of points in a PS-curve. (C) 1999 Elsevier Science Ltd. All rights reserved.