[ Introduction ]
This program, which was implemented by Java, can partition an orthogonal polygon into rectangular strips. It is a necessary step for constructing the Corner Stitching data structure from VLSI physical layouts. The orthogonal polygon to be partitioned can also contain holes. To deal with a polygon with holes, we must first represent it as one polygon contour. Examples of polygons and their corresponding contours are shown below.
The program uses plane sweep techniques. It means that an imaginary horizontal line scans the polygon vertices from the top to the bottom, or scans the vertices from the one with the largest Y coordinate to the one with the smallest Y coordinate. For the case that vertices which have the same Y coordinate, they are processed from the left to the right.
[ Example: A SpiralShaped Orthogonal Polygon ] download the contour
Before Partitioning 
After Partitioning 


[ Example: An Orthogonal Polygon with Holes ] download the contour
Before Partitioning 
After Partitioning 


[ Example: A Complex Orthogonal Polygon ] download the contour
Before Partitioning 
After Partitioning 


[ Program Download ]
Click here to download.
[ Program Usage ]
$ java jar polygon2strips.jar <the polygon contour file>
For example, to partition the orthogonal polygon with holes as shown in one of the above example:
$ java jar polygon2strips.jar holes.txt
The output will be:
Going Through eventQ ... 
The 7 rectangular strips are highlighted in red.
[ History ]
Date 
Events 
Jun 19, 2005  First working version was implemented. 
Jun 20, 2005  built this web page 
Jun 23, 2005  added Program Download and Program Usage on the page 