环绕一组点的边界
在这个实验练习中，我们将实现一个算法，它可以取x，y平面上的一组点，并构建一个围绕这些点的边界。
你的程序将从名为“points.txt”的文本文件中读取点列表的坐标，并运行一个算法来计算一组点，这些点需要构建一个边界多边形，该多边形只是围绕着平面上的点。你的程序会将边界点的坐标保存到第二个名为boundary.txt的文件中。
为了帮助您判断结果是否正确，我还将提供一个Java程序，该程序允许您查看原始点集和您构建的边界。上面的图片显示了我们正在寻找的结果。
算法的构建块
与计算机科学中的许多算法一样，我们将在本实验练习中实现的算法依赖于一组子问题的解。本节的实验材料将描述其中的几个子问题以及如何解决它们。
实验室要用到的第一个概念是两点之间的极夹角。下面的图片说明了这个概念。
图中是一对点p和q，两点的x坐标之差为Δx，两点的y坐标之差为Δy。点q相对于参考点p的弧度极角θ由公式给出
θ = atan2（Δy，Δx）
atan2（y,x）函数在Java中作为Math.atan2（y,x）方法可用。
我们的解需要用到的第二个子问题是平面上的三个点的集合是向左转弯还是向右转弯。
这是一个由三点p， q和r组成的左转弯的图。
这是一个由三个点p， q和r组成的右转弯的图。
下面是一个Java方法的代码，该方法可以确定这三个点是否形成一个右转。
public static boolean右转（点p，点q，点r） {double v1x = q.x - p.x；双v1y = q.y - p.y；Double v2x = rx - q.x；双v2y = r.y - q.y；返回v1x*v2y-v2x*v1y < 0；｝
构造边界的算法
这里是算法的轮廓，我们将使用它来为平面上的点集合构造一组边界点。
- 将赢博体育的点放在一个列表中，并创建第二个空列表来保存边界点。
- 搜索点列表以找到y坐标最低的点。这个点将成为算法的参考点。从原来的点列表中删除这个点。
- 接下来，计算每个剩余点相对于该参考点的极坐标角度。将点列表按极角增加的顺序排序。
- 把参考点放在边界表上。将第一个点放置在边界列表中排序好的点列表中。
- 对于列表中第一个点之后的每一个点，这样做：
- 当边界列表中的最后两个点与该点形成右转时，删除并丢弃边界列表中的最后一个点。
- 将该点添加到边界列表中。
一旦这个算法完成，我们就有了我们需要的边界点列表。
检查你的工作
在这些说明的顶部，你会发现一个链接到NetBeans项目的按钮，你将在这个实验练习中使用它。NetBeans项目包括一个文本文件points.txt，您将使用该文件为程序提供一组要使用的点。该项目还包括一个可视化程序，将允许您可视化您的结果。运行该项目将启动可视化程序。
由于可视化程序期望从名为boundary.txt的文件中读取边界点列表，因此在编写了计算边界点并将其保存到boundary.txt的程序之前，您将无法运行可视化程序。
为您的程序向项目添加一个新类。这个新类的主要方法将实现我在上面概述的算法。运行此程序应计算并将边界点列表保存到boundary.txt文件中。在这一点上，您将能够运行可视化程序，以确认您的边界是正确的。