算法(4th ed)(81):基础——数据抽象 4.2.1

阅读数:11 2019 年 11 月 2 日 12:08

算法(4th ed)(81):基础——数据抽象 4.2.1

(抽象数据类型举例:几何对象)

面向对象编程的一个典型例子是为几何对象设计数据类型。例如,表 1.2.3 至表 1.2.5 中的 API 为三种常见的几何对象定义了相应的抽象数据类型:Point2D(平面上的点)、Interval1D(直线上的间隔)、Interval2D(平面上的二维间隔,即和数轴对齐的长方形)。和以前一样,这些 API 都是自文档化的,它们的用例十分容易理解,列在了表 1.2.5 的后面。这段代码从命令行读取一个 Interval2D 的边界和一个整数 T,在单位正方形内随机生成 T 个点并统计落在间隔之内的点数(用来估计该长方形的面积)。为了表现效果,用例还画出了间隔和落在间隔之外的所有点。这种计算方法是一个模型,它将计算几何图形的面积和体积的问题转化为了判定一个点是否落在该图形中(稍稍简单,但仍然不那么容易)。我们当然也能为其他几何对象定义 API,比如线段、三角形、多边形、圆等,不过实现它们的相关操作可能十分有挑战性。本节末尾的练习会考察其中几个例子。

算法(4th ed)(81):基础——数据抽象 4.2.1

本书中使用的部分抽象数据类型

表 1.2.3 平面上的点的 API

public class Point2D
              Point2D(double x, double y)创建一个点
     double   x()x 坐标
     double   y()y 坐标
     double   r()极径(极坐标)
     double   theta()极角(极坐标)
     double   distTo(Point2D that)从该点到 that 的欧几里得距离
       void   draw()StdDraw 绘出该点

表 1.2.4 直线上间隔的 API

public class Interval1D
              Interval1D(double lo, double hi)创建一个间隔
      double  length()间隔长度
     boolean  contains(double x)x 是否在间隔中
     boolean  intersect(Interval1D that)该间隔是否和间隔 that 相交
        void  draw()StdDraw 绘出该间隔

表 1.2.5 平面上的二维间隔的 API

public class Interval2D
          Interval2D(Interval1D x, Interval1D y)创建一个二维间隔
  double  area()二维间隔的面积
 boolean  contains(Point2D p)p 是否在二维间隔中
 boolean  intersect(Interval2D that)该间隔是否和二维间隔 that 相交
    void  draw()StdDraw 绘出该二维间隔
复制代码
public static void main(String[] args)
{
double xlo = Double.parseDouble(args[0]);
double xhi = Double.parseDouble(args[1]);
double ylo = Double.parseDouble(args[2]);
double yhi = Double.parseDouble(args[3]);
int T = Integer.parseInt(args[4]);
Interval1D xinterval = new Interval1D(xlo, xhi);
Interval1D yinterval = new Interval1D(ylo, yhi);
Interval2D box = new Interval2D(xinterval, yinterval);
box.draw();
Counter c = new Counter("hits");
for (int t = 0; t < T; t++)
{
double x = Math.random();
double y = Math.random();
Point2D p = new Point2D(x, y);
if (box.contains(p)) c.increment();
else p.draw();
}
StdOut.println(c);
StdOut.println(box.area());
}
`Interval2D` 的测试用例

算法(4th ed)(81):基础——数据抽象 4.2.1

处理几何对象的程序在自然世界模型、科学计算、电子游戏、电影等许多应用的计算中有着广泛的应用。此类程序的研发已经发展成了计算几何学的这门影响深远的研究学科。在贯穿全书的众多例子中你会看到,我们在本书中学习的许多算法在这个领域都有应用。在这里我们要说明的是直接表示几何对象的抽象数据类型的定义并不困难且在用例中的应用也十分简洁。本书网站和本节末尾的若干练习都证明了这一点。

评论

发布