Hi, everyone! I have a question about generating random meshgrid.

Firstly, I created a [x,y] meshgrid and plot it, then I added random amounts to the vertices of the mesh so that the shape of the mesh became random. Then I wanted to constrain the area of each small grid to be equal, but found that there were too many variables and too few constraints, making it difficult to proceed. Any better way to get what I want? Thank you guys!

Answer 1

[David Goodmanson]

Hello yc,

If you are willing to make an approximation to the area of each grid quadrilateral then I think there is a reasonably viable solution. Consider a square with corner points

a b
c d

and small x and y displacements ax, ay of the top left corner, similarly for b,c,d. The area of the resulting quadrilateral is a complicated function of the 8 deflections but if you are willing to go with the area to lowest order in the deflections and drop higher order terms such as ax*by and so forth, which is reasonable if the deflections are on the order of .1, then the change in area is simply (1/2)* [(bx-ax) + (dx-cx) + (ay -cy) + (by-dy)] and for each quadrilateral to not change in area from its original value, then the sum of all those terms is 0. If you have n small squares per side, then there are (n+1)^2 points, 2*(n+1)^2 deflections and n^2 constraints on the quadrilateral areas. That leaves 2*(n+1)^2 - n^2 random degrees of freedom. I think the following code gets it done. I have not tried to optimise it for speed.

% mesh (n+1)x(n+1) of n squares per side                                                          c d.
% 1,1 index is in upper left corner, row index is y, column index is x.
% After constraints are taken into account, the x and y displacements
% of the corners of the squares are derived from uniform random variables
% with -g < x,y < g.

n = 10;
g = .2;
m = zeros(n^2,2*(n+1)^2);  % constraint matrix, operates on a column vector of x deflections
                           % concatenated with a column vector of y deflections 
for j = 1:n
  for k = 1:n     
    mx = zeros(n+1,n+1);
    mx(j:j+1,k:k+1) = [-1 1;-1 1];
    my = zeros(n+1,n+1);
    my(j:j+1,k:k+1) = [1 1; -1 -1];
    m(j+(k-1)*n,1:(n+1)^2) = mx(:)';
    m(j+(k-1)*n,(n+1)^2+1:2*(n+1)^2) = my(:)';
  end
end
nullm = null(m);     
df = 2*(n+1)^2-n^2;       % number of degrees of freedom
r = g*(2*rand(df,1)-1);   % random numbers about 0
delxy = nullm*r;
delx = delxy(1:(n+1)^2);
dely = delxy((n+1)^2+1:2*(n+1)^2);
delx = reshape(delx,n+1,n+1);
dely = reshape(dely,n+1,n+1);

% <new calculation>
% check that Alin (the linear approx to A) = 1 for all quadrilaterals.
% find the fractional difference of Alin compared to the true area, A
% D = (Alin-A)/A

% for this calc go to complex variables. visually, +1 is to the right, +i is down
u = delx-i*dely;
da = u(2:end,2:end)-u(1:end-1,1:end-1);
bc = u(1:end-1,2:end)-u(2:end,1:end-1);
A = (1/2)*imag((da+1+i).*conj(bc+1-i));
% multiply this out, discard quadratic terms
Alin = 1 + (1/2)*imag((da+conj(bc))*(1+i));
D = Alin./A -1;
max(D,[],'all')
min(D,[],'all')

[chen yuqin]

Hello DG! Thanks for your reply! This really helped me a lot! Now all I need to do is generate the mesh. I think it is a good idea to abandon high-order quantities, because the area of each grid unit must be constrained to be equal, so the four grid points of the grid can only move within a small range, which will definitely lead to very small high-order quantities that can be ignored.

[David Goodmanson]

Hello yc,

I understand your point, although i would state the situation a bit differently. If you denote the linear approximation to the area by Alin, then the code makes all of the Alins = 1 even if the displacements are fairly large. So the real quesion is for the n^2 quadrilaterals, how closely Alin is to the true area A in each of those cases. I added some code to calculate the n^2 differences between Alin and A.

The original code draws from a uniform distribution on [-g, g] to create the displacements and although the draws do not quite give the displacements directly (because of the constraints), still g can get fairly large, up to around .3 and the fractional difference between Alin and A is no worse than 12 percent or so.

Answer 2

[John D'Errico]

Any better way? Sorry, but no. You want to generate a "randomly" perturbed mesh, but one where each cell has exactly equal area? UGH. As problems go, this one will be nasty in triplicate.

No easy solution. Not even a remotely viable solution.

[chen yuqin]

Hi, John! Thanks for your reply. I also realize the complexity of the problem. I can think of using optimization and iteration ideas, but once the number of grids increases, it will increase exponentially, and it will be difficult to start from the beginning.

[John D'Errico]

You might decide to randomly perturb the mesh, then TRY to use iterative methods to further perturb the mesh. But don't be surprised if the solution found is one where the grid moves to one that us effectively the same one you started with, before perturbation. Or you might get out some other regular grid as a result, since that is also a trivial solution.

[Image Analyst]

Why do they need to be equal areas? What is your next step, assuming you were able to achieve that? I'd like to determine if it's really necessary or not. Maybe having approximately the same area is good enough for what you want to do.

[chen yuqin]

Thanks for your answer! We intend to generate a random set of microlens arrays that the energy passing through each microlens unit is the same. I think the approximate equal area is a good idea. Maybe the result after optimization and iteration is approximately equal.