4
$\begingroup$

I'm trying to figure this out for my Computer Graphics course, but I find it very hard to understand.

I believe the minimum number of angles obtained from clipping a convex polygon with n angles is 0, for example if the polygon is outside of the clipping rectangle, but I'm not sure if this makes sense.

As for the maximum number of angles, I believe it is 2n, as in if every angle tip gets outside of the rectangle. However, I'm not sure about this either.

$\endgroup$
  • $\begingroup$ Related (though not a duplicate) $\endgroup$ – trichoplax Jun 26 '16 at 11:17
  • $\begingroup$ Does "clipping" in this context mean "clipping against a rectangle"? $\endgroup$ – trichoplax Jun 26 '16 at 11:18
  • $\begingroup$ Yes, that is exactly what I mean :) $\endgroup$ – douaberigoale Jun 26 '16 at 11:57
  • $\begingroup$ Sorry - I just realised you did mention a rectangle in your question... $\endgroup$ – trichoplax Jun 26 '16 at 12:02
3
$\begingroup$

Since this is a homework question, I'll give hints rather than a numerical answer.


Clipping a convex polygon

Think about how many times the polygon can cross each edge of the rectangle. In general, a polygon can cross one of the edges of the rectangle an arbitrarily large number of times. How is this number reduced if the polygon is convex?

This will give you the maximal number of new angles that can be added per rectangle edge, which should lead you to the answer.

Clipping a non-convex polygon

As for your guess of 2n, even for a non-convex polygon it may not be able to reach this high. If one vertex is outside the rectangle, then in order to create 2 new vertices both of its neighbouring vertices must be inside the rectangle. This means you cannot create 2n new vertices this way.

The exception is when an edge of the polygon crosses 2 edges of the rectangle, for example at a corner of the rectangle. This allows creating two new vertices from a single edge. So for small enough n, it is possible to clip to a polygon with 2n vertices, but for larger n this is not possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.