矩形多边形连接算法与超媒体建模技术解析

### 矩形多边形连接算法与超媒体建模技术解析 #### 矩形多边形连接算法 在处理矩形多边形连接算法时，一个关键步骤是计算矩形多边形与当前扫描线的交集。设 \(t\) 为当前考虑的矩形多边形，\(I^*\) 为对应 IB + -树中为 \(t\) 标记的区间集合。我们仅有的信息是 \(I^*\) 和位于当前扫描线上的边界点。 这里有几个重要的观察： - 交集的 \(x\) 投影可能与 \(I^*\) 中的区间重叠。 - 在与当前扫描线重叠的 \(t\) 的边界中，从下方界定 \(t\) 的边界是新交集的一部分，而从上方界定 \(t\) 的边界则不是。 基于这些观察，我们可以按以下步骤计算交集的 \(x\) 投影： 1. 提取由与 \(t\) 关联的列表中的边界点形成的水平边界的 \(x\) 投影。 2. 将从下方和上方界定 \(t\) 的边界的投影分别存储在两个集合 \(I_{below}\) 和 \(I_{above}\) 中。 3. 使用 \(I_{below}\)、\(I_{above}\) 和 \(I^*\) 计算当前交集的 \(x\) 投影。 提取 \(I^*\) 可以通过对 IB + -树的结构进行轻微修改来实现，使得树中当前为 \(t\) 标记的区间与 \(t\) 的 ID 一起存储，时间复杂度为 \(O(\log_b \frac{N}{b})\)。新交集的 \(x\) 投影的计算在内存中进行。对于 \(t\) 的每条水平边界线，在 IB + -树上仅执行一次标记、取消标记和报告操作。 从上述讨论可知，集合 \(r\) 和 \(s\) 的连接可以直接在 \(O(bN \log_b \frac{N}{b} + \ell^2k)\) 次 I/O 操作内计算得出。当所有输入的矩形多边形都是 \(y\) -单调时，集合 \(r\) 和 \(s\) 的连接可以直接在 \(O(bN \log_b \frac{N}{b} + \ell k)\) 次 I/O 操作内计算，其中 \(k\) 是相交的矩形多边形对的数量。 下面用一个表格总结矩形多边形连接算法的关键信息： | 操作 | 具体内容 | 时间复杂度 | | ---- | ---- | ---- | | 提取 \(I^*\) | 修改 IB + -树结构，使标记区间与 \(t\) 的 ID 一起存储 | \(O(\log_b \frac{N}{b})\) | | 计算交集 \(x\) 投影 | 利用 \(I_{below}\)、\(I_{above}\) 和 \(I^*\) 在内存中计算 | - | | 集合 \(r\) 和 \(s\) 连接（一般情况） | - | \(O(bN \log_b \frac{N}{b} + \ell^2k)\) | | 集合 \(r\) 和 \(s\) 连接（\(y\) -单调情况） | - | \(O(bN \log_b \frac{N}{b} + \ell k)\) | #### 超媒体建模技术（HMT） 随着软硬件技术的进步，超媒体应用的可用性和接受度显著提高，对超媒体模型、方法和 CASE 工具的需求也相应增加。目前提出的一些超媒体设计方法，如 HDM、OOHDM、RMM 等，主要侧重于信息呈现问题。然而，下一代方法应解决更多方面的问题： - 时间是超媒体应用的重要方面，目前大多数方法尚未支持元素的初始化和同步功能。 - 需要更强大的链接概念，涵盖如 Dexter 超文本参考模型和阿姆斯特丹超媒体模型中描述的高级功能。 - 应提供高级设计原语，用于建模查询接口和对底层数据源的操作组件。 - 需要坚实的授权概念来处理数据操作的访问限制。 基于关系管理方法（RMM），我们开发了超媒体建模技术（HMT）。HMT 扩展了 RMM 的功能，提供了用于查询和操作底层数据源、指定不同级别的访问限制、定义具有扩展功能的超链接以及指定时间依赖关系的新设计原语。同时，部分修改了原设计原语的语法和图形表示，以提供更合适、直观和易用的接口。 HMT 设计过程包含以下 6 个步骤： 1. **需求分析**：定义应用领域，识别目标用户，指定系统功能和使用方式。 2. **E/R 设计**：根据需求分析构建 E/R 模型，反映现