random polygons inside a semi-circle

how to generate 2D random convex polygons inside a semi-circle 150mm diameter.the size of polygons should have a limit . maximum length of side of polygons is between 5 to 10 mm not smaller nor larger

[Bruno Luong]

"2D random polygons using convex hull"

Do you mean the polygons are required to be convex?

"fixed size distribution"

I don't understand what that means.

"generate and place method or any other"

This sentence is not grammatically correct in english. Or is it even a sentence?

[jahanzaib ahmad]

FIXED SIZE MEANS THAT THEY SHPOULD HAVE A FIXED SIZE NOT LIKE SMALLER POLYGON AND THEN SMALLER IN ORDER TO FILL THE WHOLE SHAPE . AND YES CONVEX POLYGONS . WHAT I HAVE READ IS MOST PEOLPE GENERATE A POLYGON AND THEN PLACE IT INSIDE THE OTHER SHAPE THIS HAS BEEN CALLED TO BE GENERATE AND PLACE METHOD IF U HAVE ANY OTHER WAY TO GENERATE SUCH POLYGONS IN SEMI-CIRCLE THAT OK . POLYGONS SHOULD NOT OVERLAP

[Guillaume]

Please, don't write in all caps. It's very difficult to read.

[jahanzaib ahmad]

i have used this code to generate polygons now i want to place them randomly in semi circles and want to fix there size as well

x1 = rand(1,10); y1 = rand(1,10);

vi = convhull(x1,y1); polyarea(x1(vi),y1(vi))

plot(x1,y1,'.') axis equal hold on fill ( x1(vi), y1(vi), 'r','facealpha', 0.5 ); hold off

Answer 1

[Bruno Luong]

Edit code:

1. make polygon more uniform in size at the trade off of randomness remove artifact of the border.
2. adjust repulsion parameters.
3. improve sticky-border artifact due to denser points

N = 100; % aproximative number of polygonals to be generated
n = 64; % control size and number of vertexes of polygonal
nrepulsion = 8; % control the size of the polygonal and the randomness of the position

X = randn(N,2);
R = sqrt(rand(N,1));
X = R .* X ./ sqrt(sum(X.^2,2));
X(:,2) = abs(X(:,2));

nb = 100;
theta = linspace(0,pi,nb)';
XC = [cos(theta), sin(theta)];
nb = ceil(nb*2/pi);
XY0 = linspace(-1,1,nb)' .* [1 0];
XY0([1 end],:) = [];

n1 = size(X,1);
n2 = size(XC,1);
n3 = size(XY0,1);
CC = n1+(1:n2-1)' + [0 1];
C0 = (n1+n2)+(1:n3-1)' + [0 1];
C = [CC; C0];
XB = [XC; XY0];

% Repulsion of seeds to avoid them to be too close to each other
for k = 1:nrepulsion-1
    XALL = [X; XB];
    DT = delaunayTriangulation(XALL);
    T = DT.ConnectivityList;
    containX = ismember(T,1:n1);
    b = any(containX,2);
    TX = T(b,:);
    [r,i0] = find(containX(b,:));
    i = mod(i0+(-1:1),3)+1;
    i = TX(r + (i-1)*size(TX,1));
    T = accumarray([i(:,1);i(:,1)],[i(:,2);i(:,3)],[n1 1],@(x) {x}); 
    maxd2 = 0;
    R = zeros(n1,2);
    for i=1:n1
        Ti = T{i};
        P = X(i,:) - XALL(Ti,:);
        nP2 = sum(P.^2,2);
        maxd2 = maxd2 + mean(nP2);
        b = Ti > n1;
        nP2(b) = nP2(b)*3; % reduce repulsion from each point of the border
        R(i,:) = sum(P./nP2,1);
    end
    if k==1
        v0 = 0.005/sqrt(maxd2/n1);
    end
    v = v0/sqrt(max(sum(R.^2,2)));
    X = X + v*R;
    % Project back if points falling outside the half-circle
    X(:,2) = max(X(:,2),0.01);
    r2 = sum(X.^2,2);
    out = r2>1;
    X(out,:) = X(out,:) .* (0.99 ./ sqrt(r2(out)));
end

DT = delaunayTriangulation(X);
[V,P] = voronoiDiagram(DT);

KX = convexHull(DT);
[ib,ik] = ismember(1:N,KX);
r = 2;
r2 = r^2;
warning('off','MATLAB:polyshape:boundary3Points');
warning('off','MATLAB:polyshape:repairedBySimplify');
PXB = polyshape(XC);
for k=1:N
    Pk = V(P{k},:);
    if ib(k) % infinity
        ik0 = ik(k);

          if ik0 == length(KX)
              kp = KX(1);
          else
              kp = KX(ik0+1);
          end
          km = k;
          Pv = Pk(2,:);
          if Pv*Pv' < r2
              t = X(km,:)-X(kp,:);
              nt2 = t*t';
              P0 = t*((Pv*t')/nt2);
              cs2 = P0*P0';
              if cs2 <= r2
                  d = [-t(2),t(1)] / sqrt(nt2);
                  sn = sqrt(r2-cs2);
                  if sn > (Pv-P0)*d'
                      Pk(1,:) = P0 + sn*d;
                  else
                      Pk(1,:) = [];
                  end
              else
                  Pk(1,:) = [];
              end
          else
              Pk(1,:) = [];
          end       

          if ik0 == 1
              km = KX(end);
          else
              km = KX(ik0-1);
          end
          kp = k;
          Pv = Pk(end,:);
          if Pv*Pv' < r2
              t = X(km,:)-X(kp,:);
              nt2 = t*t';
              P0 = t*((Pv*t')/nt2);
              cs2 = P0*P0';
              if cs2 <= r2
                  d = [-t(2),t(1)] / sqrt(nt2);
                  sn = sqrt(r2-cs2);
                  if sn > (Pv-P0)*d'
                      Pk(end+1,:) = P0 + sn*d;
                  end
              end
          end  
      end
      [Pk,sid] = intersect(PXB, polyshape(Pk));
      Pk = Pk.Vertices;
      m = length(Pk);
      if m >= 3
          nb1 = sum(sid == 1);
          m = m - nb1;
          W = rand(n,m-1) .^ (1./(m-1:-1:1));
          W = cumprod([ones(n,1),W],2) .* (1-[W, zeros(n,1)]);
          if nb1>0
              % Consider weight of the borders as weight for two points
              Pk = circshift(Pk,-find(sid==0, 1, 'first'),1);
              nb1 = nb1+2;
              w = linspace(0,2/nb1,nb1);
              Pk = [Pk(1:m-2,:); [w; fliplr(w)]*Pk(m-1:end,:)];
          end
          Pk = W*Pk;
          K = convhull(Pk);
          P{k} = Pk(K,:);
      else
          P{k} = [];
      end
  end
  P(cellfun('isempty',P)) = [];

% Check
fig = figure(1);
clf(fig);
ax = axes('Parent',fig);
hold(ax,'on');
plot(ax, XB([1:end 1],1),XB([1:end 1],2),'k');
for k=1:length(P)
    Pk = P{k};
    fill(ax,Pk(:,1),Pk(:,2),k);
end
axis(ax,'equal');
axis(ax,[-1.1 1.1 -0.1 1.1]);

[jahanzaib ahmad]

thanks you

[jahanzaib ahmad]

few polygons are very small .I have restriction of using 5mm to 10mm(average longest length ) how to check that ?

[jahanzaib ahmad]

if I change n to bigger value still I get few very small polygons . I want to impose size restriction

[jahanzaib ahmad]

can u please write the description in each step ? please

[jahanzaib ahmad]

@bruno u r expert . please I want to know that how to keep the distance between to polygons to 0.25mm . ?and can u add circles of 3mm to 6mm in the free area ? from last 10 days I m trying to understand this code .

[Bruno Luong]

If you want to increase the spacing between random polygonal you might shrink Pk (after shift the origin to the seed X(k,:)

Pk = X(k,:) + 0.5*(Pk - X(k,:)); % 0.5 is adjustable constant in (0,1)

right before the statement

Pk = W*Pk;

Not sure to understand your question about circle but I think you might open a new question with better description. It looks like an unrelated problem after formulation.

[jahanzaib ahmad]

@bruno

i want to two different size only like 10 mm and 5 mm and not more then that and not less then that .or two fixed area ± 20 percent and skip the other sizes/areas in between ,

i have tried to do this generating random numbers twice .this is ur first code u uploaded ..(my exact problem is that 30 percent area of semi circle should be covered with same 5 mm±2mm polygons and 40 percent should be covered with 10mm ±2mm)

N = 10; % aaproximative Number of polygonals

n = 200; % control size and number of vertexes of polygonal

X = randn(N,2);

R = sqrt(rand(N,1));

X = R .* X ./ sqrt(sum(X.^2,2));

X(:,2) = abs(X(:,2));

nb = max(N,100);

theta = linspace(0,pi,nb)';

XC = [cos(theta), sin(theta)];

%XY0 = linspace(-1,1,nb)' .* [1 0];

%XY0([1 end],:) = [];

XALL = [X; XC];

n1 = size(X,1);

n2 = size(XC,1);

%n3 = size(XY0,1);

CC = n1+(1:n2-1)' + [0 1];

%C0 = (n1+n2)+(1:n3-1)' + [0 1];

C = [CC];

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

N1 = 10; % aaproximative Number of polygonals

n11 = 50; % control size and number of vertexes of polygonal

X1 = randn(N1,2);

R1 = sqrt(rand(N1,1));

X1 = R1 .* X1 ./ sqrt(sum(X1.^2,2));

X1(:,2) = abs(X1(:,2));

nb1 = max(N1,100);

theta1 = linspace(0,pi,nb1)';

XC1 = [cos(theta1), sin(theta1)];

XY01 = linspace(-1,1,nb1)' .* [1 0];

XY01([1 end],:) = [];

X1ALL = [X1; XC1; XY01];

n111 = size(X1,1);

n21 = size(XC1,1);

n31 = size(XY01,1);

CC1 = n111+(1:n21-1)' + [0 1];

C01 = (n111+n21)+(1:n31-1)' + [0 1];

C1 = [CC1; C01];

C3 = [C;C1];

X3 = [X1ALL;XALL] ;

DT = delaunayTriangulation(X3, C3);

[V,r] = voronoiDiagram(DT);

yV1 = V(:,2);

xV1 = V(:,1);

inside1 = (yV1 > 0) & (xV1.^2+yV1.^2) < 1;

inside1 = cellfun(@(ab) all(inside1(ab)), r);

r = r(inside1);

for k=1:length(r)

rk = r{k};

m1 = length(rk);

W1 = rand(m1-1,n) .^ (1./(m1-1:-1:1)');

W1 = cumprod([ones(1,n);W1]) .* (1-[W1; zeros(1,n)]);

W2 = rand(m1-1,n11) .^ (1./(m1-1:-1:1)');

W2 = cumprod([ones(1,n11);W2]) .* (1-[W2; zeros(1,n11)]);

%rk = X(k,:) + 0.9*(rk - X(k,:)); this line is not working with this

%code

W=[W1 W2];

P = W'*V(rk,:);

K1 = convhull(P);

r{k} = P(K1,:);

end

% Check

close all

hold on

XB1 = [XC1; XY01];

plot(XB1([1:end 1],1),XB1([1:end 1],2),'b');

for k=1:length(r)

rk = r{k};

plot(rk([1:end 1],1),rk([1:end 1],2),'g');

end

axis equal;

axis([-1.1 1.1 -0.1 1.1]);

%%%%%%%%%%%%%%%%%%%%%%

if value of n11 > n and N>N1 OVERLAPPING also happens .PLEASE

Answer 2

[jahanzaib ahmad]

@bruno luong

https://www.mathworks.com/matlabcentral/answers/437754-polyshapes-formed-by-intersection-of-polygons-polyshapes .only u can help .

[jahanzaib ahmad]

how change the semi-circle to square ? please

[jahanzaib ahmad]

[jahanzaib ahmad]

convex polygons sizes measured (the max distance between vertices of polygons )

[jahanzaib ahmad]

is this possible to get constant size polygons ? or to minimize the variation in size ?

[jahanzaib ahmad]

@Bruno

Edit code:

1. make polygon more uniform in size at the trade off of randomness remove artifact of the border.
2. adjust repulsion parameters.
3. improve sticky-border artifact due to denser points

i tried to make a 3D buts it do not have the above mentioned qualities .i want to make the tetrahedron big enough that do not intersect but i want to control the number of vertices (maximum should be 15 ). plus uniform distribution inside cube .

N=250;

X=rand(N,3);

n=80;

my_vertices = [0 0 0; 0 1 0; 1 1 0; 1 0 0; 0 0 1; 0 1 1; 1 1 1; 1 0 1];

XALL=[X;my_vertices];

n1 = size(X,1);

DT = delaunayTriangulation(XALL(:,1),XALL(:,2),XALL(:,3));

%triplot(DT)

[V,r] = voronoiDiagram(DT);

yV = V(:,2);

xV = V(:,1);

zV=V(:,3);

%plot(xV,yV,'b-');

inside = (yV>0)&(yV<1)& (xV<1)& (xV > 0) &(zV<1)& (zV > 0) ;

inside = cellfun(@(id) all(inside(id)), r);

r = r(inside);

for k=1:length(r)

rk = r{k};

m = length(rk);

W = rand(m-1,n) .^ (1./(m-1:-1:1)');

W = cumprod([ones(1,n);W]) .* (1-[W; zeros(1,n)]);

%P = W'*V(rk,:);

% P = V(rk,:)- .0000001.*V(rk,:);

P =W'* (V(rk,:));

%P = W'*P;

K = convhull(P);

r{k} = P(K,:);

% plot(P(:,1),P(:,2),'.');

%hold on

end

figure(1)

for k=1:length(r)

rk = r{k};

DT3 = delaunayTriangulation(rk);

[C3,v3]= convexHull(DT3);

trisurf(C3,DT3.Points(:,1),DT3.Points(:,2),DT3.Points(:,3),'FaceColor','w');

hold on

end