Hi,

currently am working on the grid generator. Lets say I have a shape like that

I need to fill the whole shape with grids that have defined size, now the problem appears when there are rotated walls. I gotta find those non-grid shapes(blue colour) and create meshes representing them. All i got is the corner points of that strange shape because it is also a mesh. If there is any algorithm or your own brilliant idea how to find those points, share it here. Appreciate that!

The winding number algorithm is a comprehensive way to find out which corners of your rectangles are inside and which outside of the polygon.

After that the challenging part is slicing the rectangles that have part of their corners inside and part outside. You just have to compare each of these edge rectangles against the surrounding polygon: you can find the intersections of a rectangle’s side and the surrounding polygon with line segment intersection algorithms and go from there.

EDIT:I wrote that thinking that you are placing a polygon on top of a grid and need to get the underlying rectangles to fit in it… But if you just need to rectangulate an existing polygon, it would be easier to just slice the polygon e.g. starting from it’s leftmost node and finding the linesegment intersection points between the polygon and vertical lines that are placed at regular intervals. This way you’ll get tall polygons that you can then slice horizontally in the same manner.