基于网格(html5画布)将多边形拆分为多个多边形

Question

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

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

因此,我得到4个多边形的坐标,而不是1个多边形.

有没有一个简单的解决方案,我没有想到？

这是我的测试画布(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

您可以很容易地计算出来：
您首先从网格中获取所有点（所有交叉点），然后您所要做的就是对每个点检查它是否在多边形内部。

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

要查看一个点是否在多边形内部，有很多方法，这里只是其中之一：检查 html 画布上特定区域中的点位置

顺便说一句：您不需要考虑外部的琐碎网格点多边形的 x 坐标（x 坐标高于或小于多边形的最大/最小 x 坐标，y 坐标高于或小于多边形的最大/最小 y 坐标）。

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

你要做的就是检查网格上的所有点。
黑色和蓝色点将被忽略，因为它们位于网格的外部或边界上。
只有绿点是有趣的。
从那里，您只需沿着网格向各个方向移动，直到与多边形边界相交。
这要么是边界点（蓝色），要么是交叉点（橙色）。
找到直线与多边形边界的交点很容易，这里不再赘述。
就是这样，您拥有了定义内部多边形的所有点。

在这里，当多边形内有多个网格点（绿色点）时，您还可以立即发现问题，因为您必须选择所需的大多边形内的哪些多边形。
解决这个问题非常复杂，我认为这超出了这个问题的范围。