Graphics Gems III (IBM Version)

IV.6

FASTER LINE SEGMENT INTERSECTION

Franklin Antonio,     QUALCOMM, Incorporated, Del Mar, California

Publisher Summary

This chapter presents an algorithm to determine whether two line segments in 2-D space intersect or not and to determine the point of intersection. Rapid calculation of line segment intersections is important because this function is often called a primitive many number of times in the inner loops of other algorithms. To develop the algorithm, it is convenient to use vector representation. The chapter describes C implementation as one that involves calculation of the intersection point coordinates where the segments are found to intersect. The C implementation uses integer arithmetic. Calculation of the intersection point ...