论文部分内容阅读
以IC布图应用为背景,本文提出一个表示平面正交矩形划分的称为“壁勾链”的数据结构。它通过定义一组区域邻接指针,把矩形划分上的所有区域勾链起来。基于壁勾链数据结构,平面矩形划分上的点定位、邻域查找、路径搜索等操作可以迅速而有效地完成。壁勾链数据结构可以完整描述矩形划分的几何信息和拓扑信息,适应IC布图系统各个过程对布图表示的要求,可以作为一个集成布图系统中统一的布图表示数据结构。