算法： 计算凸包并绘制 HTML5 Canvas（ 第 2 部分， 共 N 部分）
添加更多方法（选择点、绘制三角形等），以便我们可以在 HTML5 Canvas 上进行一些特殊的绘制，从而研究凸包计算算法。
引言
本文继续详细介绍凸包算法的计算以及我正在创建的用于研究该算法的 HTML5 Canvas 工作，该工作始于第一篇文章。
算法：计算凸包和绘制 HTML Canvas（第 1 部分，共 2 部分）[^]
您可以在我的网站上看到最新的工作版本： http://raddev.us/TrapPoints[^]
背景
为了能够继续将本系列文章写成一个循序渐进的教程，我决定这次我们将添加一些附加功能，以便我们可以更仔细地研究该算法。 在本文中，我将添加两个额外的代码下载（TrapPoints_v005.zip 和 TrapPoints_v006.zip）。
TrapPoints_v005.zip 将添加:
DrawTriangle() 方法的第一个版本，该版本尝试遍历 allPoints[] 数组并为每三个点绘制一个三角形。
TrapPoints_v006.zip 将添加:
- 能够选择任意三个点并从这些点绘制一个三角形（用户需要按住 Shift 键来选择点）
- 能够仅清除屏幕上绘制的线条 - 不删除用户添加的点集（allPoints[]）。
- 附加按钮，允许用户运行新功能。
为什么选择这些功能？
算法研究
所有添加的功能都是为了提供一种分析计算凸包所需工作的方法。 有了这些功能，用户将能够通过绘制画布上的点周围的三角形来检查如何尝试找到所有凸包上的点。
HTML5 Canvas / JavaScript 研究
这项工作还使我们能够了解我们可以编写哪些 JavaScript 来操作 HTML5 Canvas。 将这两项结合起来是为了使这两个主题都更有趣，并帮助读者巩固对两者的知识。
第 5 步（TrapPoints_v005）开始
此版本的代码仅添加了一个新函数，如下所示。
function drawTriangle(){
if (allPoints.length < 3){
console.log("not enough points to draw a triangle");
return;
}
var triIndex = $("#triangleNumber").val();
if (triIndex < 1){
return;
}
console.log(triIndex);
var offset = (triIndex - 1);
maxIdx = allPoints.length;
var firstPoint = null;
for (var count = 0; count < 2; count++)
{
var idxPoint1 = (offset +count) % maxIdx;
console.log("(offset +count) % maxIdx : " +(offset +count) % maxIdx);
var idxPoint2 = (offset + count + 1) % maxIdx;
drawLine(allPoints[idxPoint1], allPoints[idxPoint2]);
if (count == 0)
{
firstPoint = allPoints[idxPoint1];
}
else if (count > 0){
drawLine(allPoints[idxPoint2], firstPoint);
}
}
}
三角形：至少需要三个点
在方法中，我们首先确保用户已经在屏幕上绘制了至少三个点。 如果没有添加至少三个点，我们会在控制台写入消息并退出方法。 注意：这是一个手动工具，所以我没有弹出对话框或其他任何东西。 您可以根据需要添加该功能。
jQuery：从输入控件获取值
接下来，我们使用 jQuery 来获取新添加的输入控件的值。 以下代码选择输入控件：$("#triangleNumber")
我们对该 jQuery 对象调用名为 val() 的 jQuery 方法，它返回控件当前设置的值。
我们将该值存储在一个名为 triIndex（三角形索引）的变量中，它表示我们要绘制的三角形的索引。 这将是 allPoint[] 数组中点的索引值。 但是，我想确保用户确实想绘制一个三角形，所以如果值为 0 或未定义（未设置），我将再次从方法返回。
我希望用户说：“我想绘制第 X 个三角形”，这意味着第 1 个三角形从 allPoints[] 数组的第 0 个点开始。 第 0 个三角形可以表示为不想绘制三角形。 我这样做是因为我希望稍后使用此功能，这样如果用户不想按索引绘制特定三角形，程序将根据选定的点绘制一个三角形。
一旦用户将值设置为 1 或更大，我将使用以下代码计算偏移值：var offset = (triIndex - 1);
不允许用户超出索引值
我还想知道 allPoints[] 数组中点可能具有的最大索引值（即长度 - 1），这样我就可以在 allPoints 中计算点，而不会使索引溢出。 这样，即使用户在输入框中输入了一个很大的值，我也永远不会超出索引值。 是的，即使数组中只有 3 个点，用户在输入框中输入 3489，drawTrianlge() 方法也将使用偏移点索引绘制适当的三角形。 这是该确切情况的快照。
模运算完美地适用于此
要完成这项工作，请想想我们知道什么。
- 一个三角形总是三个点
- allPoints[] 数组中的最大点数。
- 我们希望从原始点数组 allPoints[] 中的某个特定点开始绘制我们的三角形，这是一个偏移量（用于开始的位置）。
- 第一个点也将始终是最后一个点，因为我们要闭合三角形
有了这些信息，我们就可以使用模运算轻松地遍历点集。
三角形始终有三个点
首先，我们知道的最简单的事情是三角形总是由三个点组成。 这为我们的 for 循环设定了界限。 但是，您可能已经注意到 for 循环只迭代了两次。 那是因为我们在同一个循环中绘制最后两条线，因为那时我们拥有所需的所有信息。 这是因为最后一条线从第三个点回到第一个点以闭合三角形。
获取三角形中每条线的每个点
一旦进入循环，我们要做的第一件事就是计算三角形中每条线所需的两个点。 我们将这些索引值存储在两个变量（idxPoint1 和 idxPoint2）中。 计算第一个点是基于用户选择的 offset 以及我们所在的循环（count）的迭代。 但是，由于我们要确保永不超出 allPoints 数组的最大索引，我们进行模运算以确保返回到 idxPoint1 的值永远不会超出该最大值。
var idxPoint1 = (offset +count) % maxIdx;
计算第二个点的唯一区别是我们在索引上加一（下面的 + 1），但我们仍然进行模运算以防止超出边界。
var idxPoint2 = (offset + count + 1) % maxIdx;
模运算示例值
- 1 % 5 = 1
- 2 % 5 = 2
- 3 % 5 = 3
- 4 % 5 = 4
- 5 % 5 = 0
- 6 % 5 = 1
- 7 % 5 = 2
DrawLine
最后，我们只需调用我们在 TrapPoints 的先前版本中创建的 drawLine() 方法，它就会在它接收到的两个点之间绘制线条。 这很简单。
第一个点是最后一个点
因为最后一条绘制的线总是从最后一个点到第一个点，所以我们将第一个点存储在一个变量中，以便我们可以轻松地绘制回第一个点的线。
最后一次循环
在最后一次（第二次）循环时，您可以看到我们调用了两次 drawLine()。 第一次在 for 循环的常规主体中，第二次在 else if () 部分中。
第 5 步结论
就是这样，现在您可以在网格上绘制点，并选择一个起点（通过在输入框中选择一个索引值），然后单击“绘制三角形”按钮，您将看到一个在点之间绘制的三角形。
当然，这个代码有一些限制，我们将在第 6 步中解决这些限制。
第 6 步（TrapPoints_v006.zip）开始
附加功能
我添加了很多功能，以帮助用户操作点和线，并在他们想要的地方绘制三角形，以便他们可以研究如何创建凸包算法。
清除线条
首先，我希望您能够清除绘制的线条而不清除点，因此我添加了一个“清除线条”按钮，该按钮将允许您在背景上重新绘制点，而不会绘制任何三角形或连接线。
由于我清理代码的方式，clearLines() 方法非常简单。
function clearLines(){
draw();
}
显然，这只是调用 draw() 方法，所以我们需要看一下修改后的方法。
主 draw() 方法
主 draw() 方法很容易检查，因为它由其他功能组成。 自第一篇文章以来，它变化不大。
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 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);
}
if (allPoints.length > 0){
drawPoints();
}
drawHighlightPoints();
}
自从上一个版本以来，我只是添加了最后一个 if 语句和对新的 drawHighlightPoints() 方法的调用。
if 语句只是检查 allPoints 数组是否包含任何值（代表用户添加的点）。 如果包含，则 draw() 方法现在将重新绘制它们。
选择点以创建三角形
现在，让我们看看 drawHighlightPoints() 方法，我们将研究允许用户选择三个点来绘制自己的三角形的功能。
drawHightlightPoints() 是一个简单的方法，它实现了一个 for 循环，并迭代一些点，同时调用 highlightPoint()，所以我们现在将同时查看这两个方法。
function drawHighlightPoints(){
for (var x = 0; x < selectedTriangle.length;x++){
highlightPoint(selectedTriangle[x]);
}
}
function highlightPoint(point){
ctx.strokeStyle = "red";
ctx.lineWidth = 2;
drawPoint(point);
// set style back to original
ctx.strokeStyle = "black";
ctx.lineWidth = 1;
}
用户可以选择点来突出显示它们
您可以看到 drawHighlightPoints() 在一个名为 selectedTriangle[] 的新数组上工作。 这是用户已突出显示的（最多三个）点的集合。 用户可以通过按住 Shift 键同时单击屏幕上已有的点来选择一个点来突出显示它。
在 MouseDownHandler 中选择高亮点
要了解允许用户突出显示点的代码，我们需要查看我添加的 mouseDownHandler 函数的新部分。
这是 mouseDownHandler() 的当前外观。 重要的部分是我确定在用户单击鼠标时是否按下了 Shift 键。
function mouseDownHandler(event){
if (event.button == 0){
var currentPoint = getMousePos(event);
if ((currentPoint.x > 650) || (currentPoint.y > 650))
{
return;
}
if (event.shiftKey){
console.log(event.shiftKey);
var p = hitTest(currentPoint);
if (p !== undefined)
{
selectedTriangle.push(p);
if (selectedTriangle.length > 3){
selectedTriangle.shift();
}
draw();
}
}
else{
allPoints.push(currentPoint);
drawPoint(currentPoint);
console.log(currentPoint);
}
}
}
event 对象包含一个布尔值，告知您是否按下了 Shift 键，所以这足够简单了。
点的命中测试
接下来，您可以看到我调用了一个名为 hitTest() 的方法来确定用户单击的位置是否具有先前绘制的点（来自 allPoints[]）。如果 hitTest 成功，它将返回一个我们可以使用的点对象。 否则，它将返回 undefined（无点）。
hitTest() 代码很有趣而且很简单。
function hitTest(p){
// iterate through all points
for (var x = 0;x<allPoints.length;x++){
if ((Math.abs(p.x - allPoints[x].x) <= RADIUS) && Math.abs(p.y - allPoints[x].y) <=RADIUS){
console.log("It's a hit..." + allPoints[x]);
return allPoints[x];
}
}
}
hitTest() 采用一个点，代表鼠标的当前位置（当用户在按住 Shift 键时单击）。
然后我们只需遍历 allPoints[] 数组中的所有点。 allPoints[] 数组中每个点的点值是中心点，屏幕上绘制的点实际上是 RADIUS * 2 的大小。 这意味着我们需要检查我们的新点是否与 allPoints[] 中每个点的距离 +/- RADIUS。
我们使用简单的减法语句和 JavaScript Math.abs()（绝对值）函数来实现这一点。
如果我们命中，我们将返回 allPoints[] 数组中的特定点。 非常简单，我认为非常优雅。
回到 OnMouseDownHandler
如果返回了一个有效点，我们就运行以下代码。
selectedTriangle.push(p);
if (selectedTriangle.length > 3){
selectedTriangle.shift();
}
draw();
我们将该点推入 selectedTriangle[] 数组，该数组用于跟踪将被用于绘制用户选择的三角形的点。 然后您会看到我们检查数组是否包含超过 3 个点。 如果包含，我们调用 JavaScript shift() 方法（一个数组方法），该方法将第一个元素从数组中弹出，并将所有项目向下移动索引。 这会确保数组中只包含最后三个点。
不能突出显示超过 3 个点
这样，用户一次最多只能选择三个点。
最后，我们调用 draw() 方法，因为它会依次调用 drawHighlightPoints() 方法，然后所有正确的点将以红色绘制。 看起来是这样的。
DrawTriangle：已修改以处理用户选择的点
我们需要查看的最后一件事是 drawTriangle() 方法，我已经修改了它以同时处理索引三角形和用户选择的三角形。 如果输入框中的索引值小于或等于 0 并且存在选定的三角形（用户已选择三个点），则它将使用红色高亮显示的点绘制一个三角形。
function drawTriangle(){
var tempAllPoints = null;
if (allPoints.length < 3){
console.log("not enough points to draw a triangle");
return;
}
var triIndex = $("#triangleNumber").val();
if (triIndex < 1){
if (selectedTriangle.length == 3){
tempAllPoints = allPoints;
allPoints = selectedTriangle;
}
}
console.log(triIndex);
var offset = (triIndex - 1);
offset = offset > 0 ? offset :0;
maxIdx = allPoints.length;
var firstPoint = null;
for (var count = 0; count < 2; count++)
{
var idxPoint1 = (offset +count) % maxIdx;
console.log("(offset +count) % maxIdx : " +(offset +count) % maxIdx);
var idxPoint2 = (offset + count + 1) % maxIdx;
drawLine(allPoints[idxPoint1], allPoints[idxPoint2]);
if (count == 0)
{
firstPoint = allPoints[idxPoint1];
}
else if (count > 0){
drawLine(allPoints[idxPoint2], firstPoint);
}
}
if (tempAllPoints !== null){
allPoints = tempAllPoints;
}
}
基本功能（检查上面的粗体代码）
第一行粗体代码只是一个临时对象变量，我们将用它来保存原始 allPoints[] 数组，以便在绘制用户选择的三角形后可以恢复它。
在此之后，我只是检查 selectedTriangle 数组是否有效（包含 3 个点）。 如果是，我将交换数组与 allPoints 数组，因为使用相同的数组来执行原始的 drawTriangle() 工作很容易。
最后，如果 tempAllPoints 不为 null，则它包含原始 allPoints 数组的副本，我们将其恢复。
当您突出显示三个点并单击 **[绘制三角形]** 按钮时，它看起来会像这样。
我希望您在这里学到了很多，并会尝试一下。
下一篇文章
我计划
- 添加一个按钮来创建随机生成的点
- 使其能够移动点 - 似乎是一个有趣的挑战
- 开始实现第一个尝试算法的凸包生成。
- 随着我的想法出现其他事情。
历史
本文的第一个版本，附带两个代码版本；2016 年 4 月 26 日