丹娜·h·巴拉德著
ACM通信，1981年5月，第24卷第5期，310-321页
10.1145/358645.358661
评论
用曲线表示二维结构是许多科学研究的重要组成部分。例如，地理学家广泛使用曲线来表示等高线、道路和河流等地图特征。电路布局设计者使用曲线来指定电路之间的布线。由于涉及的数据量非常大，而且需要对这些数据有效地执行操作，因此这种曲线的表示是一个关键问题。描述了一种由二叉树组成的层次表示，在每个节点上都有一个特殊的基准。这种数据称为条带，包含这种数据的树称为条带树。树中的较低级别对应于曲线的较细分辨率表示。条形树结构是使用一种特殊的方法将线数字化并保留所有中间步骤的直接结果。这就提供了几个理想的属性。对于性能良好的曲线，相交和点隶属度(对于闭合曲线)的计算可以在0(log)内求解
n),
n是描述曲线的点数。曲线可以有效地编码和显示在各种分辨率。表示在交集和并集下是封闭的，这些操作可以在不同的分辨率下进行。所有这些属性都依赖于分层树结构，它允许基本操作以尽可能低的分辨率执行，并节省大量计算时间。
条形树是一种线性插值方案，它不显式表示所有的点，实现了重要的空间节省。这意味着即使添加了树索引的开销，存储需求也与显式表示大多数点的栅格表示相当。
本文的全文是优质内容
没有发现记录
登录阅读全文
需要访问吗?
请选择下面的一个选项以访问高级内容和功能。
创建一个网上帐户
如果你已经是ACM会员，通信订阅者或数码图书馆订阅者，请设置网页帐户，以浏览本网站的优质内容。
参加ACM
成为ACM的会员，可以充分利用ACM卓越的计算信息资源、网络机会等优势。
订阅ACM杂志通讯
获得50多年的中华中医药学会内容的完整访问权限，并每月获得杂志印刷版。
购买这篇文章
非会员可以购买这篇文章或刊登这篇文章的杂志。
