Research On 2D Curve Intersection And Its Related Algorithm

Finding intersections among 2D curves is a basic problem in CAD/CG, and widely used in the fields of intelligent information systems, such as GIS, image process, etc. It's difficult to find curve intersection directly. In general, curves are split into polygonal chains consisting of line-segments, and curves intersections can be found from the intersections of polygonal chains. However, the efficiency of the general method isn't high for there are a great many of line-segments. It is important to improve efficiency of curve intesection algorithm. In addition, a lot of curves are composed of arcs and line segments in engineering, such as the contour lines in machining fields. It is useful to find intersections for such curves using the special properties of line-arc curves.By using monotony and convexity-concavity of polygonal chain as well as box technique, an improved algorithm for polygonal chains intersection is proposed based on the sweep line algorithm. The proposed algorithm is best suited for finding intersections among polygonal chains consisting of densely spaced vertices. For the closed-curves consist of arcs and line segments, we present a fast approach to find intersections of closed-curve by extending Park's polygonal chains intersection algorithm. In the algorithm, the convexity-concavity of vertexes and arcs must be identified, and a fast approach for identifying the convexity-concavity of line-arc closed curve is proposed. Firstly, the orientation of a closed-curve is determined by constructing a new convex polygon. Secondly, by using the orientation of the closed curve the convexity-concavity of vertices and arcs are identified. Finally, the convexity-concavity of the closed curve is detected. In the end, Choi's pair-wise offset of polygon algorithm is improved based on the proposed curve intersection algorithm.