How to fill out a procedurally generated mesh with quads of varying sizes?

Hello, I'm generating meshes based of color coded areas on an image.

In the following picture, the semi-transparent image is a representation of what a color coded section might look like, with the black dots being natural 2d vertex positions.

The way I currently create a mesh is by iterating through a nested x,y for loop and making a 1x1 quad.

However, I would like to generate the meshes in a way in which I could specify the desired quad size, perhaps something like the following image(desired quad size 3x3)

The generation doesn't have to follow this schema exactly, or even be consisted of quads. The only important thing is that I'm able to specify the desired size of the generated triangles, in order to make meshes of varying detail to use in a LOD system.

Would you happen to know what kind of mathematical area I should look into in order to figure out how to write this logic, or better yet, of an algorithm or a library that can do the aforementioned?

I, of course, plan to texture the generated mesh, so I wanted to additionally ask if the UVs are going to be messed up with this kind of generation, and if fixing those UVs at runtime is going to be problematic and cpu intensive.