基于解开操作的直角多边形随机生成算法

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

Random Generation Algorithm of Rectilinear Polygon Based on Untangling

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.