Split polygon into multiple polygons based on grid (html5 canvas)

Question

I'm drawing polygons on a canvas with an underlying grid

I want to split this polygon into multiple polygons now (based on the grid)

So instead of 1 polygon, I get the coordinates for 4 polygons.

Is there an easy solution for this I'm not thinking about?

This is the code for my test 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

You can quite easily calculate this:
You start by taking all points from your grid (all intersections), then all you have to do is for each point to check whether it is inside your polygon or not.

• If it is a corner of your polygon, you can ignore it.
• If it is outside your polygon, you can ignore it.
• If it is inside your polygon, you have trivial 4 polygons to each side of the point. It then depends how you want to handle the case where multiple grid-points are inside your polygon.

To see whether a point is inside a polygon, there are plenty of methods, here is just one of them from SO: Check a point location in a particular area on html canvas

By the way: you don't need to consider trivial gridpoints outside of your polygon (those with x-coordinates higher or smaller than the max/min x-coordinates of your polygon and those with y-coordinates higher or smaller than the max/min y-coordiantes of your polygon).

EDIT: I made this image:

What you do is you check all points on the grid.
The black and blue points are ignored because they are outside or on the borders of your grid.
Only the green point is interesting.
From there, you simply follow the grid in all directions until you hit an intersection with the polygon borders.
This is either a border point - blue - or an intersection - orange.
It's easy to find the intersection of a line and borders of a polygon, so I won't go into the detail here.
Then that's it, you have all the points which will define the inner polygons.

Here, you can also immediately spot the problem when you have multiple grid points (green points) inside the polygon because you'll have to choose which polygons inside the big polygon you want.
That's quite complicated to solve and I think it's out of scope for this question.