Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!ginosko!uunet!cbmvax!mitchell
From: mitchell@cbmvax.UUCP (Fred Mitchell - QA)
Newsgroups: comp.graphics
Subject: Re: clipping polygons to a viewport
Keywords: polygons,clipping
Message-ID: <8072@cbmvax.UUCP>
Date: 3 Oct 89 23:43:37 GMT
References: <120@csinc.UUCP>
Reply-To: mitchell@cbmvax.UUCP (Fred Mitchell - QA)
Organization: Commodore Technology, West Chester, PA
Lines: 132

In article <120@csinc.UUCP> shal@csinc.UUCP (Shal Jain x848) writes:
>Am looking for a very robust algorithm/code for clipping polygons to a 
>rectangular viewport. The polygons can be concave,convex or bow-tied.

I have developed a method of doing this which is (kinda) simple.
First, let's look at your figure:

>           ------------------
>           +                +
>           +            ****@*****
>           +             *  +    *
>           +              * +    *
>           +               *+    *
>           +                @    *
>           +                +*   *
>           +                + *  *
>           +                +*   *
>           +                @    *
>           +               *+    *
>           +              * +    *
>           --------------@---    *
>                        *        *
>                       ***********

Treat the horizontal bounds:

>           ----------------------------
>                            
>                        **********
>                         *       *
>                          *      *
>                           *     *
>                            *    *
>                             *   *
>                              *  *
>                             *   *
>                            *    *
>                           *     *
>                          *      *
>           --------------@-------@-----
>                        *        *
>                       ***********

And now check each line IN SEQUENCE, starting from any arbitrary beginning:

from first line to last:
	a) A line segment that is COMPLETELY between
		leave alone

	b) A line segment that is COMPLETELY outside
		delete it

	c) A line segment that is BISECTED by a horizontal line
		determine point of intersection (@)
		truncate line at (@), and replace the 
			old line with the part of the new line satifies (b).
		check truncation queue
		if (empty)
			place this point (@) in queue
		else
			pull out last (@) from queue
			create a new line ((@)-(@))

Now we should have:

>           ----------------------------
>                            
>                        **********
>                         *       *
>                          *      *
>                           *     *
>                            *    *
>                             *   *
>                              *  *
>                             *   *
>                            *    *
>                           *     *
>                          *      *
>           --------------@*******@-----

So for the vertical case:

>           +                +
>           +                +
>           +            ****@*****
>           +             *  +    *
>           +              * +    *
>           +               *+    *
>           +                @    *
>           +                +*   *
>           +                + *  *
>           +                +*   *
>           +                @    *
>           +               *+    *
>           +              * +    *
>           +             @**@****@
>           +                +
>           +                +

Apply the above algorithm, except for the vertical bounds.
Then you will have:

>           +                +
>           +                +
>           +            ****@
>           +             *  *
>           +              * *
>           +               **
>           +                @
>           +                *
>           +                * <--- artifact
>           +                *
>           +                @
>           +               **
>           +              * *
>           +             @**@
>           +                +
>           +                +

Note that two of the lines overlap, the 'clip' lines. You may want to further
processing to eliminate the 'artifact' area if that will interfere with
your application. The artifact area will always be characterized by
'even' overlapped segments of the line (and, of course, coinciding with
the boundary). 

Also, note that a line is counted as 'within bounds' if it coincides
with the boundary lines.

If you need any more help, E-Mail me!
Address is: mitchell@cbmvax.UUCP 

	-Mitchell