Clipping a line segment to a complex
polygon
Written by Paul Bourke
August 1997
The following describes a procedure for clipping a line segment to a complex polygon. Complex polygon
refers to both concave polygons and polygons with holes.
Whether the requirement is to retain that portion of the line within the polygon or remove the portion of
the polygon within the polygon the concept is the same.
Consider a parametric expression for the line segment between two points P1 and P2.
P = P1 + mu (P2 - P1) where 0 <= mu <= 1
Then all the points of intersection of this line segment with edges of the polygon can be calculated, see
here
Arrange these points of intersection by increasing values of mu along the line. These points form pairs of
edges alternatively inside and outside the polygon.
The only remaining ambiguity is whether the first point P1 of the line segment (mu = 0) is within or
outside the polygon, see here for details.
Clipping a line to a polygon
file:///F|/Geometry/Display 09 Algorithms/Clipping a line to a polygon.htm (1 of 2) [12/22/2000 03:37:32 PM]
Clipping a line to a polygon
file:///F|/Geometry/Display 09 Algorithms/Clipping a line to a polygon.htm (2 of 2) [12/22/2000 03:37:32 PM]