CODEWITHSUNDEEP
random
Ricardo Sanchez
Ricardo Sanchez

Reputation: 5167

How to randomly fill a space in one dimension?

I would like to know how can I randomly fill a space with a set number of items and a target size, for example given the number of columns = 15 and a target size width = 320, how can I randomly distribute the columns width to fill the space? like shown in the image below if possible any sort of pseudo-code or algorithm will do

enter image description here

Upvotes: 1

Views: 161

Answers (2)

FelixCQ
FelixCQ

Reputation: 2028

One way to partition your 320 pixels in 15 random "columns" is to do it uniformly, i.e., every column width follows the same distribution.

For this, your actually need a uniform distribution on the simplex. The first way to achieve is the one described by yi_H, and is probably the way to go:

  • Generate 14 uniform integers between 0 and 320.
  • Keep regenerating any number that has already been chosen, so that you end up with 14 distinct numbers
  • Sort them
  • Your columns bounds are given by two consecutive random numbers.

If you have a minimum width requirement (e.g., 1 for non-empty columns), remove it 15 times from your 320 pixels, generate the numbers in the new range and make the necessary adjustments.

The second way to achieve a uniform point on a simplex is a bit more involved, and not very well suited with discrete settings such as pixels, but here it is in brief anyway:

  • Generate 15 exponential random variables with same shape parameter (e.g. 1)
  • Divide each number by the total, so that each is in [0,1]
  • Rescale those number by multiplying them by 320, and round them. These are your column widths

This is not as nice as the first way, since with the rounding you may end with a total bigger or smaller than 320, and you may have columns with 0 width... The only advantage is that you don't need to perform any sort (but you have to compute logarithms... so all in all, the first way is the way to go).

I should add that if you do not necessarily want uniform random filling, then you have a lot more algorithms at your disposal.

Edit: Here is a quick implementation of the first algorithm in Mathematica. Note that in order to avoid generating points until they are all different, you can just consider that an empty column has a width of 1, and then a minimum width of 2 will give you columns with non-empty interior:

min = 2;
total = 320;
height = 50;
n = 15;
x = Sort[RandomInteger[total - n*min - 1, n - 1]] + Range[n - 1]*min
Graphics[{Rectangle[{-2, 0}, {0, height}], (*left margin*)
  Rectangle[{#, 0}, {# + 1, height}] & /@ x, (*columns borders*)
  Rectangle[{total, 0}, {total + 2, height}]}, (*right margin*)
 PlotRange -> {{-2, total + 2}, {0, height}}, 
 ImageSize -> {total + 4, height}]

with gives the following example output:

output with 15 columns, minimum width 2

Edit: Here is the modified javascript algorithm (beware, I have never written Javascript before, so there might be some errors\poor style):

function sortNumber(a,b)
{
   return a - b;
}

function draw() {
   var canvas = document.getElementById( "myCanvas" );

   var numberOfStrips = 15;
   var initPosX = 10;
   var initPosY = 10;
   var width = 320;
   var height = 240;
   var minColWidth = 2;
   var reducedWidth = width - numberOfStrips * minColWidth;
   var separators = new Array();

   for ( var n = 0; n < numberOfStrips - 1; n++ ) {
      separators[n] = Math.floor(Math.random() * reducedWidth);
   }
   separators.sort(sortNumber);
   for ( var n = 0; n < numberOfStrips - 1; n++ ) {
      separators[n] += (n+1) * minColWidth;
   }
   if ( canvas.getContext ) {
      var ctx = canvas.getContext( "2d" );

      // Draw lines
      ctx.lineWidth = 1;
      ctx.strokeStyle = "rgb( 120, 120, 120 )";
      for ( var n = 0; n < numberOfStrips - 1; n++ ) {
         var newPosX = separators[n];
         ctx.moveTo( initPosX + newPosX, initPosY );
         ctx.lineTo( initPosX + newPosX, initPosY + height );
      }
      ctx.stroke();

      // Draw enclosing rectangle
      ctx.lineWidth = 4;
      ctx.strokeStyle = "rgb( 0, 0, 0 )";
      ctx.strokeRect( initPosX, initPosY, width, height );
   }
}

Additionally, note that minColWidth should not be bigger than a certain value (reducedWidth should not be negative...), but it is not tested in the algorithm. As stated before, us a value of 0 if you don't mind two lines on one another, a value of 1 if you don't mind two lines next to each other, and a value of 2 or more if you want non-empty columns only.

Upvotes: 2

Karoly Horvath
Karoly Horvath

Reputation: 96266

Create 14 unique numbers in the range (0,320). Those will be the x position of the bars.

Create random number, compare with previous ones, store it.

If consecutive lines aren't allowed, also check that it doesn't equal with any previous+-1.

Upvotes: 1

Related Questions