How to draw random polygons but with the same perimeter?

I want to draw some random closed polygons but am having some trouble. Each smooth curve must have the same perimeter but a different area. Something like the following figure, where the complexity can be adjusted. Is this possible?

(Also sorry I posted a similar question a few minutes ago with wrong wording, I since deleted it.)

Answer 1

[John D'Errico]

Since I'm the one who pointed out that the last question was not correct...

This is trivial, in a sense.

1. Start with points around a circle, stored in polar coordinates form.

2. Then apply proportional random noise to the radii. This ensures the polygon will always be non-overlapping, as long as the noise is always positive.

3. To ensure the perimeter stays constant, compute the perimeter, then apply a final scaling to the radii.

If your goal is to ensure the area is a GIVEN value, chosen from some distribution, while the perimeter stays fixed, that too should be doable, but perhaps more complex.

[Image Analyst]

Clever algorithm. Paul, how are you going to specify the shapes? Are you going to have a matrix (digital image), or an equation (like splines) between the discrete and separate vertices?

[John D'Errico]

Splines are an option. My arclength tool (on the FEX) can compute the arclength of a closed curve, using a spline interpolate. However, polygonal arclength is easier to compute though (a one-liner), and a polygon allows you to compute the area using polyarea.

If you want to generate smoother curves, then I suppose you could use random noise with a correlation, so successive points will be related to each other. That will yield curves that will be more smooth.

[Paul Scotti]

Thanks for the help! Here is some (very) rough code, which seems to be making some progress. It makes use of polygeom.m to compute perimeter.

Basically following John D'Errico's instructions, constructed a polygon and used proportional random noise to vary the radii. I couldn't figure out how to compute the perimeter in polar coordinates so I just converted to cartesian, used the polygeom file, and adjusted the polar coordinates using that to figure out the proportion needed to apply to the radii to keep a constant perimeter. Then to smooth the polygon I used splines. So far this is what I have, will hopefully tweak better later.

Lowering the proportion to something like 0.2 reduces the complexity to more of a blob (radii are less free to vary).

sides=20;

theta=0:2*pi/(sides):2*pi-(pi/(sides));

radius=ones(1,numel(theta)); %Every point 1 radii away

proportion = 0.8;

for i = 1:length(radius)
    radius(i) = radius(i) - rand()*proportion;
end

figure(1)
polar(theta,radius);

[x,y] = pol2cart(theta,radius);
polyperim = polygeom(x,y); %last number is perimeter

ratio = 6.2574/polyperim(end); %6.2574 is the perimeter of the polygon with 20 sides if all radii were maximum of 1

radius = radius * ratio;

[x,y] = pol2cart(theta,radius);
figure(2);
fill(x,y,'w');
xlim([-2 2]); ylim([-2 2]);

n = length(x);
t = 1:n;
tfine = 1:0.01:n;
xfine = spline(t, x, tfine);
yfine = spline(t, y, tfine);

figure(3);
fill(xfine,yfine,'w');
xlim([-2 2]); ylim([-2 2]);

Essentially looks like this so far :

Again, I'm not the best coder so it's programmed pretty inefficiently. Would appreciate any further directions, will look into the arclength tool.

[John D'Errico]

Not terrible code either. It is moderately vectorized, and where not, loops are not the end of the world. You could have modified the radius in one line, instead of a loop, for example. Maybe this:

radius = radius.*(1+(rand(size(radius))*2 - 1)*proportion);

Given that may be more difficult to read than a simple loop, who really cares if there is a loop in there?

You might have chosen to use a different distribution for the radii. Lognormal proportional noise comes to mind as one simple alternative.

Constructs like this, using the colon operator are somewhat dangerous.

theta=0:2*pi/(sides):2*pi-(pi/(sides));

More robust is to use linspace where you can, so like this:

theta = linspace(0,2*pi-(pi/(sides),sides);

The danger with the colon operator is it MIGHT be at risk of rounding problems with a non-integer stride. LINSPACE completely avoids that. (For some reason, I think they might have a trap in the colon operator to catch exactly such a problem. I would have done so, were I writing the colon code.)

Other points might be to compute the perimeter using the interpolated points. That will be more accurate than using it on the original set, then interpolating using a spline.

Oh, for the spline interpolant, do NOT use spline. Use pchip. The problem with spline is it can show large over and undershoot behavior on noisy data. That could end up creating a curve that intersects with itself, by overshooting below zero! Pchip has the property that it cannot exhibit overshoot or undershoot. A pchip interpolant has the property that it will never introduce extrema into the curve that were not in the data.

I was picky in the above comments though. As I said, not too bad code.

[Image Analyst]

For what it's worth, I attach my demo where an image is binarized and the boundaries/outlines are found. Then I smooth the boundaries with pchip. (Requires Image Processing Toolbox.)