Ch09-常用算法课程.pdf

ch09 几何扫描 • 9.1 引言 • 9.1 引言 • 9.2 几何预备知识 • 9.2 几何预备知识 • 9.3 计算线段的交点 • 9.3 计算线段的交点 • 9.4 凸包问题 • 9.4 凸包问题 • 9.5 计算点集的直径 • 9.5 计算点集的直径 • 9.6 小结与练习 • 9.6 小结与练习 9.1 引言 99..11 引引言言 • 基本概念 • 定义1 设p1=(x1, y1)和p2=(x2, y2)是平面中的两点，如果x1≤ x2并且y1≤ y2, 则称p2支配 p1 ，记为p1 p2。 • 定义2 设S是平面中的一个点集，点pS是极大点或最大 点，如果不存在点qS，使得p≠q并且p q。 算法描述（示例） • 算算法法描描述述（（示示例例）） 1. 在平面上给定一个 个点的集合 ，确定S中的极大点 11.. 在在平平面面上上给给定定一一个个n个个点点的的集集合合S，，确确定定SS中中的的极极大大点点 2. 算法 22.. 算算法法MAXIMA MMAAXXIIMMAA 输入：平面上n个点的集合S 输输入入：：平平面面上上nn个个点点的的集集合合SS 输出：S中极大点集合M 输输出出：：SS中中极极大大点点集集合合MM 设 为 中按 坐标升序排列的 for ← to x ffoorr j ttoo n 1. A S 4. 2 点的集合。如果两个点有相同 x, y ←A j 5. ( ) [ ] 的 坐标，则有较大 坐标值的 if then x y iiff y maxy tthheenn 6. 点出现在集合的前面 M← M U A j 7. { [ ]} M← A maxy←y 2. { [1]} 8. ← 的 坐标值