How do I clip a line against a strictly regulated polygon

Question

I need to clip a line against a very regulated polygon. The polygon will always be a rectangle, orientated along the euclidian axis, and MAY have corners "cut off". Look at this picture to see what I mean.

The corners may be cut so that a point forms at one of the edges, but never more. In some cases (most, actually) no corners will be cut, and I have implemented the Cohen-Sutherland algorithm to deal with these cases, but I'm at a loss as to how to do it when corners are cut. I suppose there are general algorithms for clipping a line against a polygon, but I don't know much about this. Also, this will probably be overkill for my situation. The polygons I'm dealing with will always be simple, concave and monotone. Are there any good (prefferably simple) algorithms for this?

Answer 1

Here's one way to do it:

For each side of a convex polygon
  p = the intersection point between line and the polygon side
  if p lies between the endpoints of the polygon side, save point p
  if there are two saved points then exit the loop
next

Draw a line between the two points for the answer. Take care if the line passes through a polygon vertex -- roundoff errors may cause problems.