关键词: 直角多边形, 随机生成, 解开操作, 电子设计自动化

Abstract: The test of integrated circuit physical design needs random generating rectilinear polygon to cover all the cases. A novel algorithm that generates a random simple rectilinear polygon is presented. This polygon can be used for testing and analyzing algorithms in VLSI physical design. The algorithm generates an ordered sequence of points, and then untangles each pair of intersecting line segments until no more can be found. The finiteness of the algorithm is proved. Experimental results show that this algorithm is simple and efficient.

Key words: rectilinear polygon, random generation, untangling, electronic design automation