我正在构建一个工具，该工具最终将利用Google Maps API v3在固定的“网格”系统（例如，坐标间隔开）上由固定边长（例如10米）的正方形构成的地图上建立一个区域从地球的0,0点开始每0.0001 latlong单位）。
我编写了代码，用户可以在其中单击地图上的某个区域，然后该代码绘制轮廓并填充找到的正方形。用户可以单击该正方形的其他相邻位置来构建越来越大的“块状”多边形，也可以单击单个正方形将其删除。我已经在HTML5 canvas / JavaScript和Google Maps API中对所有这些进行了测试。
现在，我想编写删除所有内部边缘/顶点的代码，以便仅绘制此多边形的最外边界，以便实际上将其绘制为一个大多边形，而不是正方形的集合。这样想：即使我们知道像澳大利亚，美国等国家一样，都由许多州组成，但是当我们划定该国的边界时，我们通常对所有州的边界都不感兴趣，可以删除那些州之间的直线，并绘制外边界。这是我要完成的同一件事，只是使用正方形网格而不是复杂的多边形。
我当前的代码在这里：
https://jsfiddle.net/wyxcvmdf/14/
HTML：
<canvas id="myCanvas" width="500" height="250" style="border:1px solid #000000;"></canvas>
<!--etc.-->
JavaScript：
// don't forget to set load type in jsfiddle to no wrap in <body>
// define the global variable and some helper variables to make the code shorter
var gv = {};
gv.o = function(id) {
return document.getElementById(id)
};
gv.i = 'innerHTML';
// etc.
关于我的代码的一些解释性注释：
•每个正方形的“原点”是该正方形左下角的顶点。没有特别的原因。
•关于HTML5画布如何绘制轮廓的“绘制方向”是从原点开始逆时针旋转的。同样，没有特别的原因。
•您还不能“单击”添加正方形，因为这只是一个概念证明，因此您可以通过在相关文本输入框中输入x和y坐标来添加正方形
我想到的证明我的代码所需的用例/测试是：
将正方形添加到具有1个重复顶点的多边形（工作）
在所有情况下，将正方形添加到具有2个和3个重复顶点的多边形上：相邻边，非相邻边，非顺序点（当前仅适用于第一种情况）
在所有情况下，将正方形添加到具有4个重复顶点的多边形中：塞孔，塞孔的一部分，连接多个多边形（当前仅在第一种情况下有效）
在上述情况下，从具有1个重复顶点的多边形中删除了正方形（尚未开发，但应有效地与附加代码“相反”）
在上述情况下，从具有2个和3个重复顶点的多边形中移除了正方形（尚未开发，但应有效地与附加代码“反向”）
在上述情况下，从具有4个重复顶点的多边形中移除了正方形（尚未开发，但应有效地与附加代码“反向”）
在具有多个内部边界（即孔）的多边形外部进行正方形添加/删除（尚未开发，可能会比较棘手）
在具有多个内部边界（即孔）的多边形内部进行正方形添加/删除（尚未开发，可能会比较棘手）
注1：我使用“正方形”，“边缘”等代替“多边形”等是为了简化说明。
注意2：我对类似问题和可能的解决方案进行了大量研究，但还没有发现任何可以满足我需要的东西。我所做的研究是：
旅行推销员问题。但是，这并不是优化路径，而是确保路径是“可绘制的”并因此朝一个方向前进。只要结果形状看起来像用户期望的那样，重叠的顶点就可以了。
凸包算法。船壳可能是凸形，凹形甚至不连续的，因此并不适用！另外，我认为通过简化为网格系统，我消除了具有许多分散顶点的问题，在这些顶点中，您需要确定顶点距中心点的距离，使用三角函数等。
凹面船体解决方案。这更接近解决我的问题的方法，但是我看到的是有许多用于商业工具（例如ArcGIS）的插件可以做到这一点，但是没有涵盖我所有用例的通用代码（与编程语言无关）。
基于图块的游戏。您可能会认为，任何需要在图块周围绘制边界的基于图块的游戏（例如，实时策略游戏中的玩家领土）都可以解决此问题，但从我的角度来看并不是这样。
最佳答案
您说的是“绘制”而不是计算外部顶点，所以...
您可以使用剪裁和合成来“挖空”一组正方形。
假设您确定这些正方形在所需边界内（部分或全部在内部）：
var aInside=[ {x:60,y:60},{x:80,y:60},{x:40,y:60},{x:60,y:40},{x:60,y:80} ];
所需边界内的正方形的图示。
然后，仅绘制一组正方形的边界，您可以：
描边（不填充）您的每个内部正方形：
context.rect
将进一步绘制限制为描边矩形：
context.clip使所有新图形删除现有像素：
context.globalCompositeOperation = 'destination-out'用纯色填充整个画布：
context.fillRect(0,0,canvas.width,canvas.height)。诀窍：绘制矩形实际上是在矩形的一半内侧和一半外侧绘制一个笔划，因此第4步将擦除矩形组的内部，但（重要！）将留下一半的外侧笔划。
因此，您最终得到以下结果：
这是示例代码和演示：
var canvas=document.getElementById("canvas");
var ctx=canvas.getContext("2d");
var aInside=[ {x:60,y:60},{x:80,y:60},{x:40,y:60},{x:60,y:40},{x:60,y:80} ];
// stroke all inside squares
ctx.save();
ctx.beginPath();
for(var i=0;i<aInside.length;i++){
var s=aInside[i];
ctx.rect(s.x,s.y,20,20);
}
ctx.stroke();
// clip to cause all new drawing to be inside the stroked squares
ctx.clip();
// set compositing to use new drawings to "erase" existing drawings
ctx.globalCompositeOperation='destination-out';
// Fill (===erase!) the entire canvas
// Clipping causes only the clipping area to be erased
// so the inside of the rects set is "hollowed out"
ctx.fillRect(0,0,canvas.width,canvas.height);
ctx.restore();body{ background-color: ivory; }
#canvas{border:1px solid red; }<canvas id="canvas" width=150 height=150></canvas>算法注释：如果要一组剩余的顶点而不是图形，则可以修改Marching Squares Algorithm以仅返回拐点。这些拐点是您外边界的顶点。
关于javascript - 以编程方式绘制一组正方形的边界的最佳方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36472902/