Before Partitioning
After Partitioning
[ 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 Spiral-Shaped 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 ... 1, 6 1, 8 11, 8 11, 6 ==== EndRectangle ==== -------------------- => (5, 6) -------------------- => (11, 6) -------------------- => (7, 5) ==== Rectangle: 2 ==== 5, 5 5, 6 11, 6 11, 5 ==== EndRectangle ==== -------------------- => (9, 5) -------------------- => (11, 5) -------------------- => (3, 4) ==== Rectangle: 3 ==== 1, 4 1, 6 3, 6 3, 4 ==== EndRectangle ==== -------------------- => (5, 4) ==== Rectangle: 4 ==== 5, 4 5, 5 7, 5 7, 4 ==== EndRectangle ==== -------------------- => (7, 3) ==== Rectangle: 5 ==== 1, 3 1, 4 7, 4 7, 3 ==== EndRectangle ==== -------------------- => (9, 3) ==== Rectangle: 6 ==== 9, 3 9, 5 11, 5 11, 3 ==== EndRectangle ==== -------------------- => (1, 1) ==== Rectangle: 7 ==== 1, 1 1, 3 11, 3 11, 1 ==== EndRectangle ==== -------------------- => (11, 1) -------------------- |
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 |
