我正在构建一个工具,该工具最终将利用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以仅返回拐点。这些拐点是您外边界的顶点。