javascript - 基于网格将多边形拆分为多个多边形(html5 canvas)

Question

我在带有底层网格的 Canvas 上绘制多边形

我现在想把这个多边形分割成多个多边形(基于网格)

所以我得到的不是 1 个多边形，而是 4 个多边形的坐标。

有没有我没有考虑过的简单解决方案？

这是我的测试 Canvas 的代码 ( codepen )

<script>
var bw = 200;
var bh = 200;
var p = 0;
var cw = bw + (p*2) + 1;
var ch = bh + (p*2) + 1;

var grid = 50;

var canvas = document.getElementById("canvas");
var context = canvas.getContext("2d");

function drawBoard(){

 context.beginPath();
 for (var x = 0; x <= bw; x += grid){
    context.moveTo(0.5 + x + p, p);
    context.lineTo(0.5 + x + p, bh + p);
 }
 for (var x = 0; x <= bh; x += grid) {
    context.moveTo(p, 0.5 + x + p);
    context.lineTo(bw + p, 0.5 + x + p);
 }
 context.lineWidth = 1;
 context.strokeStyle = "black";
 context.stroke();

}
drawBoard();

// Polygon
context.fillStyle = '#f00';
context.beginPath();
context.moveTo(0, 0);
context.lineTo(100,50);
context.lineTo(50, 100);
context.lineTo(0, 90);
context.closePath();
context.fill();
</script>

Answer 1

你可以很容易地计算出这个:
您首先从网格中获取所有点(所有交叉点)，然后您所要做的就是检查每个点是否在多边形内。

• 如果它是多边形的一个 Angular ，您可以忽略它。
• 如果它在你的多边形之外，你可以忽略它。
• 如果它在您的多边形内部，则该点的每一侧都有 4 个微不足道的多边形。然后，这取决于您要如何处理多边形内有多个网格点的情况。

要查看一个点是否在多边形内，有很多方法，这里只是其中一种来自 SO:Check a point location in a particular area on html canvas

顺便说一下:您不需要考虑多边形之外的琐碎网格点(那些 x 坐标高于或小于多边形的最大/最小 x 坐标，以及那些 y 坐标高于或小于最大/最小值的网格点)多边形的最小 y 坐标)。

编辑:我制作了这张图片:

你要做的是检查网格上的所有点。
黑色和蓝色点将被忽略，因为它们位于网格的外部或边界上。
只有绿点有意思。
从那里开始，您只需沿各个方向跟随网格，直到遇到与多边形边界的交点。
这要么是一个边界点——蓝色——要么是一个交点——橙色。
线和多边形边界的交点很容易找到，这里不再赘述。
就是这样，您拥有将定义内部多边形的所有点。

在这里，当多边形内有多个网格点(绿点)时，您也可以立即发现问题，因为您必须选择大多边形内的哪些多边形。
这很难解决，我认为这超出了这个问题的范围。