Split a polygon into several mesh-based polygons (html5 canvas)

Question

I draw polygons on canvas with a basic grid

I want to split this polygon into several polygons (mesh based)

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

Is there a simple solution for this that I don't think 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 easily calculate this:
You start by taking all points from your grid (all intersections), then all you need to do is check if it is inside your polygon or not.

• If this is the angle 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 4 trivial polygons on each side of the point. Then it depends on how you want to handle the case where several multi-ton points are inside your polygon.

To see if a point is inside the polygon, there are many methods, here is just one of them from SO: Check the location of the point in a specific area on the html canvas

By the way: you do not need to consider trivial grid points outside your polygon (those with x-coordinates higher or smaller than the maximum x-coordinates of your polygon, and those with y-coordinates higher or less than max / minimum y- coordinates of your polygon).

EDIT: I made this image:

What you do is check all the grid points.
Black and blue dots are ignored because they are outside or at the borders of your grid.
Only the green point is interesting.
From there, you simply follow the grid in all directions until you click the intersection with the borders of the polygon.
This is either a border crossing point - blue, or an intersection - orange.
It is easy to find the intersection of the line and the boundaries of the polygon, so I will not go into details here. Then, what is it, you have all the points that will determine the internal polygons. Here you can also immediately detect a problem when you have many grid points (green points) inside the polygon, because you will need to choose which polygons inside the large polygon you want.
This is quite difficult to solve, and I think that goes beyond the scope of this issue.

Answer 2

To solve this problem, you can consider each grid cell as a separate polygon and intersect them with your polygon one by one, the algorithm for intersection is described here

remember that for each grid cell you can get any number of new polygons in this case: