Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!ogicse!ucsd!nosc!halibut.nosc.mil!dwu
From: dwu@halibut.nosc.mil (Daniel Wu)
Newsgroups: comp.windows.x
Subject: How to clip Regions in X11R4?
Message-ID: <3725@nosc.NOSC.MIL>
Date: 20 Mar 91 08:40:24 GMT
Sender: news@nosc.NOSC.MIL
Organization: Naval Ocean Systems Center, San Diego
Lines: 35
Originator: dwu@halibut.nosc.mil


I have been trying to implement some polygon clipping routines.  Someone
mentioned to me that since X-windows X11R4 has a concept of a Region
which is a a general polygon, I should check the X11 sources to see
how the Region clipping routines are implemented.  I did and I found the file
XRegion.c in the mit/lib/X directory of the mit distribution tape.

I've looked over the code briefly.  It mentions a method called 
Y-X banding, that it employs to perform the polygon clip.  What is
Y-X banding?  Can someone point me to a source or a reference?  Looking
over the code, I gather that a region is basically an array of rectangles.
Is this right?

But how can this be?  A region is supposed to be a general polygon, specified
with (x,y) vertices.  How does it get converted into a bunch of rectangles?
More importantly, how does one recover the original list of vertices of the
polygon from the array of rectangles?

Can someone please point me in the right direction?  I would very much like
to adopt these clipping routines.  They are very nice.  The routines are
based on set operations so that one can UNION, INTERSECT, AND, OR,
take the symmetric DIFFERENCE of 2 polygons.  That's exactly what I need.  
(Actually I need one other requirement that may or may not be satisfied by 
Xregion.c: the polygons should be general polygons---convex or concave---and 
perhaps have holes).

Looking through Foley & Van Dam, I've considered the other possiblities:
Sutherland-Hodgeson (nice and simple but 1 polygon has to be convex), and
Weiler (too complex, I'm very short on time).  Are there any other
possiblities?

Daniel
dwu@halibut.nosc.mil

PS. Please reply via e-mail.  I don't read this newsgroup too often.