Re: [Algorithms] theoretical clipping behavior

[Ron L. <ro...@do...>]

Neil Tringhan wrote

> As I recall, the general result is that for clipping a convex polygon of n
> vertices against m planes, the resulting clipped polygon can have up to
> (n+m) vertices, though I can't find my proof for this:-)

The way to prove it is to bound the number of edges.  Recall that the
intersection of two convex sets is convex, so the result of clipping a
convex polygon by a plane is convex.

Consider the result of clipping a convex polygon by a single plane.  The
edges of the clipped polygon are each either an edge of the original
polygon, a subsegment of an edge of the original polygon, or a segment
contained in the line of intersection of the plane of the polygon and the
clipping plane.  Moreover, by convexity, each original edge can contribute
at most one subsegment and the line of intersection can contribute at most
one edge.  So the result of clipping a convex polygon by a plane has at most
one more edge than the original polygon.

Also, the result of clipping a convex polygon by a plane is a convex
polygon.  So by induction,  you can increase the number of edges by at most
one for each clipping plane.  A polygon has as many vertices as edges. QED

>You can wave your
> hands about and say something along the lines of "the maximum number of
> output vertices is the number of input vertices plus the number of times
an
> input edge could have cut a plane", though.

That is indeed hand-waving, for the desired conclusion does not follow.  It
could happen that some input edges cut every clipping plane and some
clipping planes are cut by two input edges, so this assertion still allows a
greater limit on the number of vertices than you are seeking.  To cut it
down you have to invoke convexity and induction.