摘要： 集成电路物理设计的测试需随机生成直角多边形以覆盖所有的情况。基于此，提出一种基于解开操作的直角多边形随机生成算法，可应用于超大规模集成电路物理设计算法的测试和分析。该算法随机生成一个点序列，逐一将每对相交的线段解开，直至找不到任何相交线段。对该算法的有穷性作出证明，并以实验证明该算法简单有效。

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

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

中图分类号: 

• TP311