🚀 go-pugleaf

Here's a sketch of a proof that the upper bound is 2N+4:

A concave polygon P has Nx convex vertices and Nv concave vertices,
where Nx >= (N+1)/2 and Nv<Nx.  (For N even, Nv <= Nx-2.)

A concave vertex flanked by two convex vertices can contribute 4
vertices to the clipped polygon when all three vertices lie outside
the clipping region.

6 more vertices can be introduced by clipping the convex hull of the
polygon against the clipping region.

For even N, the maximum number of concave vertices is N/2 - 1, so the
number of clipped vertices from concave vertices is 
	4*(N/2 - 1) = 2N - 2.
Adding the 6 from the convex hull yields 2N + 4.

For odd N, the largest number of concave vertices that can be flanked
by convex vertices on both sides is (N-1)/2 - 1, so the total becomes
	4*((N-1)/2 - 1) + 6 (+ 1) = 2N-3 + 6 (+ 1) = 2N + 3 (+ 1)
The (+ 1) in parentheses is potentially contributed by the "extra"
convex vertex, if it is inside the clipping region, again yielding a
maximum of 2N+4.

A more careful analysis would count the contribution by edges
according to classification of their endpoints, but I am convinced
that the result would be the same.

Of course, I'm equally happy to be proved wrong.

--
=Spencer W. Thomas 		|  Info Tech and Networking, B1911 CFOB, 0704
   "Genome Informatician"	|  Univ of Michigan, Ann Arbor, MI 48109
Spencer.W.Thomas@med.umich.edu	|  313-747-2778, FAX 313-764-4133

--
Moderated by SCRI Vis <>           Submissions to: graphics@scri1.scri.fsu.edu
Guy, John R. Murray   <> Administrivia to: graphics-request@scri1.scri.fsu.edu