算法： 计算凸包并绘制 HTML5 Canvas（ 第 1 部分， 共 2 部分）
逐步讲解，并提供不同版本的代码下载，带您从 HTML5 Canvas 绘制基础知识入手，同时学习一个有趣的连接点算法。
- 下载 TrapPoints_v004.zip - 2 KB
- 下载 TrapPoints_v003.zip - 1.8 KB
- 下载 TrapPoints_v002.zip - 1.5 KB
- 下载 TrapPoints_v001.zip - 1.3 KB
引言
在阅读新发布的书籍《Algorithms In A Nutshell 2nd ed. (亚马逊链接在新窗口/标签页中打开)》时，我被书中讨论如何计算任意点集凸包的第一个算法示例所吸引。凸包是包围网格上所有其他点的点的集合。
书中示例图片
背景
然而，为了学习如何做到这一点，我需要测试数据。仅仅填充一个数组并进行计算而没有任何输出似乎有些枯燥，所以我决定绘制这些点并显示它们。
图形库的部署挑战
但是，绘制和显示点必然会依赖于某个图形库，而这个库可能对许多用户来说不可用，除非强迫他们安装某个组件或库。这时，HTML5 Canvas 就派上用场了……
HTML5 Canvas：无需部署
如果您正在 CodeProject 阅读本文，那么您已经拥有了运行代码所需的一切（一个网络浏览器）。是的，您的浏览器确实需要支持 HTML5 并启用 JavaScript，但如今这已是一个相当小的要求。
查看正在运行的项目（目前的版本）
它还使得查看正在运行的项目变得极其容易，用户无需下载任何东西，只需将他们引导至一个 URL。您可以在我的网站上看到（最终）项目：
http://raddev.us/TrapPoints （在新窗口/标签页中打开）
在撰写本文时，它看起来像
截至目前的可用功能
- 绘制一个浅绿色的背景网格，只是为用户提供一个添加点的空间
- 用户只需点击网格中的任意位置即可添加点
- 点击“[连接点]”按钮会在每个点与下一点之间绘制一条线，并通过连接最后添加的点与第一个点来闭合路径。
- 此时，点击“[计算凸包]”按钮会在点数组中的每三个点之间绘制三角形。（这是通往最终算法的中间步骤）
本文将如何进行
即使应用程序的版本可能已经更新（取决于我在这项目上投入了多少时间和是否完成了算法），我将从最基础的代码开始，并将不同版本的代码作为单独的下载提供。
这将使您能够分块学习代码。例如：
第 1 步：设置 HTML、JavaScript 和要加载的库（jQuery、Bootstrap 和主要的 JS 文件）。
第 2 步：编写设置 Canvas 并绘制背景的代码。
第 3 步：编写允许用户添加点并在网格上绘制它们的代码。我们还将添加允许您清除点的代码。
第 4 步：编写连接点的代码。
这对于本文来说应该足够了，然后我们将在第 2 部分完成实际的算法。
在本文的第二部分，我们将继续我们上次中断的地方，并完成以下项目。
第 5 步：讨论我第一次尝试实现凸包算法，通过绘制整个点集中的每三个点的三角形。
第 6 步：实现计算凸包的有效解决方案。
让我们开始创建项目框架所需的基本文件。
关于代码下载
您可以看到有 4 个代码版本附加在此文章中。这样您就可以下载每个版本并逐步阅读文章。
第 1 步开始
创建 HTML 项目框架
我们首先需要创建项目的文件集。我喜欢为我的简单 HTML5 项目创建如下所示的文件夹结构。
您可以看到，我有一个主文件夹（TrapPoints），然后我创建了一个文件夹来存放 JavaScript（js），以及一个文件夹来存放 CSS（层叠样式表）（css）。我还将项目的 HTML 主文件名命名为 index.htm，这样当您将浏览器指向 URL 时，它通常会默认加载。
您还可以看到项目中有 .git 文件夹，因为我正在使用 Git VCS。
命名项目文件
我简单地将 JavaScript 文件命名为与项目相同，所以这里是 TrapPoints.js。
我的 CSS 文件是 main.css。
HTML 项目文件
index.htm 文件仅包含对我们的 JavaScript 和 CSS 文件的所有引用，它还包含我对一些我正在使用的库的引用。
Bootstrap 和 jQuery
我使用 Bootstrap 是因为它是一个易于获取样式精美的控件（按钮等）的库。我使用 jQuery 是因为 Bootstrap 无论如何都需要它，并且它提供了一个不错的 API 来选择 HTML 元素等。
立即下载基础项目代码文件
如果您想跟随代码更改，现在可以下载 TrapPoints_v001.zip 来获取此项目的基础代码。
起始代码示例
如果您下载了第一个版本，您会发现基础的 htm 文件确实包含了入门和加载所有库所需的所有引用。
我不会在这里显示整个 HTML 文件，因为它实际上只是提供了一种加载所有其他内容的方式，我将让您自行查看。但我将向您展示一行 HTML，它显示一个按钮并使用 Bootstrap 样式，以表明使用起来有多么容易。
<button onclick="connectPoints();" class="btn btn-primary">Connect Points</button>
添加 HTML 类，添加 Bootstrap 样式
请注意该行中的 class="btn btn-primary"。这会为按钮设置样式，使其成为蓝色，并带有漂亮的圆角。Bootstrap 让这变得如此简单。
如果您下载了起始代码并加载它，您会发现还没有网格，但按钮已通过 Bootstrap 设置了样式。它看起来如下：
我没有截取大快照，因为它们都只是一个空白的白色背景。
JavaScript 基础代码
该项目还包含一些非常基础的 JavaScript 代码，位于 TrapPoints.js 中。让我们看一下那段代码。
// trappoints.js
var ctx = null;
var theCanvas = null;
window.addEventListener("load", initApp);
function initApp()
{
theCanvas = document.getElementById("gamescreen");
ctx = theCanvas.getContext("2d");
ctx.canvas.height = 650;
ctx.canvas.width = ctx.canvas.height;
window.addEventListener("mousedown", mouseDownHandler);
}
function mouseDownHandler(){
}
初始化全局变量
您可以看到我初始化了一些我确定稍后会用到的全局变量。
Canvas 上下文
前两行将用于跟踪我们将用于绘图的 HTML5 Canvas 元素。
第三行代码引用了浏览器的主要窗口对象，以便我们可以添加事件监听器。
我们希望知道整个 HTML 及其所有组件（库）何时加载完成，以便我们可以进行我们的工作。我们通过调用 addEventListener 方法来告诉浏览器在页面加载完成后通知我们。
启动应用程序
我们提供一个参数（第二个参数），即当浏览器完成加载时我们希望运行的函数的名称。这就是启动我们的应用程序。在 OnLoad 事件中启动我们的应用程序确保了我们所有的库都已完全加载，因此当我们去使用它们时，它们就已经准备就绪。
我们的 initApp 方法
一旦页面和所有资源都加载完成，我们的 initApp() 方法就会触发，在该方法内部，我们进行一些初始化。
获取 Canvas 元素的引用
我们做的第一件事就是获取代表 Canvas 的 HTML 元素的引用。<canvas> 标签是 HTML5 规范中新增的一个元素，专门用于在 HTML 中进行绘图。
如果您查看 HTML，您会看到该元素看起来如下，我们添加了 id 属性，以便在代码中标识它。
<canvas id="gamescreen">You're browser does not support HTML5.</canvas>
该值 (gamescreen) 与我们在 JavaScript 调用中用来获取元素引用的值相同。
theCanvas = document.getElementById("gamescreen");
由于 jQuery 可用，我们也可以这样做：
theCanvas = $("#gamescreen").get(0);
一旦您获取了 <canvas> 元素的引用，您就可以在其上调用 HTML5 特定的函数。
您必须调用的第一个函数是 getContext("2d")；
该方法检索我们将在整个应用程序中使用的上下文，因为它暴露了 2D 上下文对象，允许我们调用 HTML5 API，从而允许我们在屏幕上进行绘图。
设置 Canvas 区域的高度和宽度
接下来，我们在 Context 对象上设置两个属性（height 和 width），它们允许我们设置将显示在屏幕上的 HTML5 Canvas 的有效区域。
ctx.canvas.height = 650;
ctx.canvas.width = ctx.canvas.height;
当然，您还看不到那个区域，因为它和 HTML 窗口的其他区域一样是白色的。
最后，我们添加另一个事件监听器，以便在用户单击鼠标按钮时执行一些工作。目前，这将响应任何一个按钮的单击，但稍后我们将对其进行修改，使其仅在单击左按钮时调用。
第一个步骤就是这些。此时，您已经有了一个准备好使用 HTML5 canvas 进行工作的框架。
第 2 步开始
现在我们将进行绘制背景的工作。
您可以通过下载本文顶部的 TrapPoints_v002.zip 来获取此步骤的完整代码。
绘制背景网格
当应用程序首次加载时，我们希望绘制背景网格，以便用户知道他们可以添加点的限制。
首先，我想初始化一些我们将用于网格的值。由于我希望看到 20 条水平和垂直线，我将简单地将宽度（与高度相同）除以 20 来计算 lineInterval 值，以便我可以在画布上绘制水平和垂直线。
我还添加了 gridColor 变量，它使用预定义的 HTML 值作为网格线的颜色。
我将这三个变量作为全局变量添加到我们的 trappoints.js 的顶部。
var LINES = 20;
var lineInterval = 0;
var gridColor = "lightgreen";
初始化网格
接下来，我想添加一个新方法来设置和使用这些值。
function initBoard(){
lineInterval = Math.floor(ctx.canvas.width / LINES);
console.log(lineInterval);
draw();
}
我称之为 initBoard()，因为这只需要运行一次。我将向我们的 initApp() 方法添加一个对此方法的调用，以便应用程序将
- 加载所有关联文件
initApp()将设置 2d 上下文和其他内容initApp()将调用 initBoard() 并绘制初始网格。
在 initBoard 中，我们执行简单的计算来确定网格线，并将值保存在我们的全局变量中。
然后，我们调用一个新方法来执行实际的绘制，这个方法被恰当地命名为 draw()；
使用 2D 上下文绘制网格
绘制网格非常简单，因为我们可以使用简单的数学和一个 for 循环来遍历画布区域的高度和宽度，并以间隔绘制我们的线条。代码如下：
function draw() {
ctx.globalAlpha = 1;
// fill the canvas background with white
ctx.fillStyle="white";
ctx.fillRect(0,0,ctx.canvas.height,ctx.canvas.width);
// draw the blue grid background
for (var lineCount=0;lineCount<LINES;lineCount++)
{
ctx.fillStyle=gridColor;
ctx.fillRect(0,lineInterval*(lineCount+1),ctx.canvas.width,2);
ctx.fillRect(lineInterval*(lineCount+1),0,2,ctx.canvas.width);
}
}
globalAlpha
设置 globalAlpha 值的首行设置了我们要绘制的项目的不透明度，使其完全不透明。值为 1 是最大值，小数表示半透明度，值越接近零，半透明度越高。
fillRect 填充 Canvas
接下来，我们将 fillStyle 设置为另一个预定义的 HTML 颜色（白色），以便我们可以将整个画布区域渲染为白色。
要用白色填充整个画布，我们调用 fillRect 方法，从左上角 (0,0) 开始，一直填充到点 x = 650, y = 650，这样整个画布矩形就被填充了。
绘制网格线
最后，我们绘制所有的网格线，只需遍历画布，每次绘制线之前稍微移动我们开始画线的位置。
请注意，对于我绘制的每条网格线，我实际上都调用 fillRect() 来完成工作。虽然我也可以调用 lineTo() 方法，这是绘制线的另一种方式。我使用 fillRect 是因为这些线稍微粗一些，我需要调用 lineTo() 多次才能完成这项工作。这样做更简单。
此时，您已经有了网格，并且应用程序现在看起来如下：
第 3 步开始
现在代码变得更有趣了，因为我们将会在用户单击鼠标左键时绘制一些点。
下载完成的代码
通过下载本文顶部的 TrapPoints_003.zip 来下载此步骤的完整代码。
获取鼠标位置
我们要做的第一件事是在鼠标单击时捕获鼠标位置。
为此，我们需要一些基本的 JavaScript 来完成这项工作。我将其封装在一个名为 getMousPos() 的函数中。
function getMousePos(evt) {
var rect = theCanvas.getBoundingClientRect();
var currentPoint = {}; // initialize an object in js
currentPoint.x = evt.clientX - rect.left;
currentPoint.y = evt.clientY - rect.top;
return currentPoint;
}
在这种情况下，我使用了 theCanvas 元素来获取边界矩形，以便获取画布相对于 HTML canvas 元素绘制的位置偏移。然而，在这个程序中这并不重要，因为我们知道 canvas 占据了页面上的前 650 x 650 像素。
接下来，我们只需获取 X 和 Y 值，并将它们存储在一个点对象中，我们稍后可以在画布上绘制该点时使用。
我们每次用户单击鼠标按钮时都会运行 getMousePos() 方法。
mouseDownHandler() 方法在用户每次单击鼠标按钮时触发。我们的方法的第一版如下：
function mouseDownHandler(event){
if (event.button == 0){
var currentPoint = getMousePos(event);
if ((currentPoint.x > 650) || (currentPoint.y > 650))
{
return;
}
console.log(currentPoint);
}
}
首先要注意的是，mouseDownEvenHandler() 方法实际上接受一个我们命名为 event 的参数。该参数由触发的原始浏览器事件（mousedown）传递给我们的方法。
该参数携带了额外的信息，提供了有关哪个按钮被单击以及指针位置的坐标值。您可以在 Mozilla 的优秀参考文档（https://mdn.org.cn/en-US/docs/Web/Events/mousedown^）中找到所有详细信息。
确定是否单击了左按钮
我们做的第一件事是确保我们只响应单击了左按钮的情况。如果 event.button 的值为零，则表示单击了左按钮。
确定坐标是否在 Canvas 内
接下来，我们确定按钮单击的坐标是否在 Canvas 区域内（x < 650 且 y < 650）。
在第一个修订版中，我只是将坐标值输出到控制台。现在我们来修改它来完成我们的工作。
保存并绘制每个点
我将添加一个名为 drawPoint() 的新方法，并允许它在每次添加新点时绘制它。
我还将添加一个新数组（allPoints）来存储绘制在 Canvas 上的所有点。
var allPoints = [];
var DIAMETER = 10;
function drawPoint(currentPoint){
ctx.beginPath();
ctx.arc(currentPoint.x, currentPoint.y,RADIUS,0,2*Math.PI);
allPoints.push(currentPoint);
ctx.stroke();
}
allPoints 数组是一个全局变量，因为我们将需要从其他方法访问它。
在 drawPoints() 方法中，我们调用了几个 HTML5 Canvas 绘图方法。首先，我们使用 beginPath() 设置绘图上下文。接下来，我们使用 arc() 方法绘制实际的点（这是一个圆的轮廓）。
Context Arc 方法
arc() 方法的前两个参数是您正在绘制的圆的中心的 x、y 位置。第三个参数是圆的半径（从圆心到边缘的距离）。我们已将其预设为一个名为 RADIUS 的全局常量，并将其设置为 10（像素）。
arc() 方法的第 4 和第 5 个参数表示圆周围的角度的弧度。在我们的例子中，我们从零（圆的 3 点钟位置）开始，并围绕圆逆时针移动 2*Math.PI 弧度，这会绘制一个完整的圆。
要绘制实际的点，我们调用上下文的 stroke() 方法，点就会出现。由于我们要存储每个点供以后使用，我们只需通过调用 allPoints.push() 将其推入 allPoints 数组。
圆的绘制就完成了，每次用户单击 Canvas 时，点都会渲染出来。
这是我在 Canvas 上单击几个位置后的样子：
清除所有点
此时，我还要添加“清除”功能，因为它很简单，并且允许您通过单击“[清除]”按钮来绘制新的点集。
function clearPoints(){
// clear all the points from the array
allPoints = [];
// redraw the background grid (erasing the points);
draw();
}
第 4 步开始
下载
您可以下载 TrapPoints_v004.zip 来获取此步骤的最终版本。
现在，我们只需要添加一个函数来绘制 allPoints 数组中每个点之间的线。
基本上，由于我们有数组中的所有点，我们只需使用 HTML5 Canvas 上下文提供的 moveTo() 和 lineTo() 方法。我将工作分解为两个单独的函数。第一个名为 connectPoints()，它调用 drawLine() 功能来执行实际的绘制工作。
function connectPoints(){
console.log("connecting points...");
if (allPoints === null || allPoints.length < 3){
console.log("there are not enough points to do calculation.");
return;
}
for (var x = 0;x < allPoints.length-1;x++){
drawLine(allPoints[x],allPoints[x+1]);
console.log("x+1 : " + x+1);
}
// draws back to the first point.
drawLine(allPoints[allPoints.length-1], allPoints[0]);
}
当用户单击“[连接点]”按钮时，会调用 connectPoints() 方法。如果数组中没有至少 3 个点，该方法会在控制台输出一条消息并返回。
当数组中至少有三个点时，它会遍历数组中的点并将它们发送到 drawLine() 方法。我们向 drawLine() 发送两个点（起始点和结束点）。
绘制每条连接线
function drawLine(p, p2){
ctx.beginPath();
ctx.moveTo(p.x,p.y);
ctx.lineTo(p2.x, p2.y);
console.log ("p.x : " + p.x + " p.y : " + p.y + " p2.x : " + p2.x + " p2.y : " + p2.y);
ctx.stroke();
}
同样，我们使用 beginPath 方法来设置我们的绘图上下文。接下来，我们使用 moveTo() 方法移动到第一个点。然后，我们只需调用 lineTo() 和 stroke() 来绘制线。
我们还将与点相关的信息输出到控制台进行简单调试。
将点围成一个形状
最后，请注意，在 connectPoints() 方法中，我们使用最后一个点绘制回第一个点，以创建一个完整的封闭形状。
版本 4：完整功能
就是这样。这完成了我们所有的工作，现在有了版本 4，您可以：
- 添加点
- 连接点
- 清除点并添加更多点
其他用途
现在您已经具备了这些基本功能，您可以将其用于您可能想要进行的与绘制点集相关的其他工作，并自行进行实验。
下一篇文章
下次我们将更详细地讨论实际的凸包创建算法，并完成我们的工作，以便能够让用户输入所有点并自动计算凸包。
历史
本文的第一个修订版，包含应用程序的前 4 个版本: 04-24-2016