# Randomly distributed, randomly rotated and non-overlapping text

I am trying to generate a page with randomly distributed and randomly rotated text and the code here does the job well.

But it causes overlapping of text (I am using devanagari alphabet --- there are more than 48 of them) even when there is no scarcity of space (I can see a lot of white space).

One approach to avoid overlapping is to keep generating the page hoping that randomness will play in our favor and generate a page without an overlap.

But that is asking for too much from randomness. I tried close to a hundred times before giving up. :)

How do I get random distribution, random rotation and no overlap?

– Max
Aug 31 '18 at 6:14
– Max
Aug 31 '18 at 6:21
• This answer shows how to randomly distribute circles without overlap. You could more or less adapt it 1 to 1 and place randomly rotated texts instead where the radius of the circles is given by the maximal size of the texts.
– user121799
Aug 31 '18 at 10:11

This answer is almost entirely taken from this nice answer. It requires lualatex.

\documentclass[tikz,border=3.14mm]{standalone}
\usepackage{filecontents}
% poisson.sty and poisson.lua are from https://tex.stackexchange.com/a/185423/121799
\begin{filecontents*}{poisson.sty}
\directlua{dofile("poisson.lua")}
\newcommand{\poissonpointslist}[4]{
\directlua{poisson_points_list(#1,#2,#3,#4)}
}
\newcommand{\poissonpointslistordered}[4]{
\directlua{poisson_points_list_ordered(#1,#2,#3,#4)}
}
\end{filecontents*}
\begin{filecontents*}{poisson.lua}
-- This is a lua implementation of the algorithm described in
-- http://devmag.org.za/2009/05/03/poisson-disk-sampling/
--
-- The structure of the algorithm is exactly the same than in
-- the mentioned article. Its pseudo-code snippets were translated
-- to Lua.
--
-- One detail worths an explanation, though. The article uses a 2D matrix
-- called grid to store coordinates of points. In the article, it is
-- assumed that grid elements can be accesed via grid[point], being point
-- some structure with a pair of x and y integers, so grid[point] should
-- be equivalent to grid[x,y] or grid[x][y]. This grid is assumed to be
-- initially dimensioned and filled by nils.
--
-- In my implementation the grid is dynamic, and it is an associative array
-- indexed by string keys in the form grid["(x,y)"]. The function gridToString()
-- can be used to convert a Point to its string form, so the grid is indeed
-- accesed like this: grid[gridToString(p)] being p a Point with integer
-- coordinates (which in fact is found via imageToGrid, like in the article)

-- UTILITY FUNCTIONS (used in the article, without giving implementation)
-- =====================================================================

-- RandomQueue stores values and gives them in random order
local RandomQueue = {}
function RandomQueue.new ()
return {last=-1}
end

function RandomQueue.push(q, item)
local last = q.last + 1
q.last = last
q[last] = item
end

function RandomQueue.pop(q)
if (RandomQueue.empty(q)) then
return nil
end
local index = math.random(0,q.last)
-- A random index is generated. The last element
-- is swaped with this random item, and the new
-- last item is popped.
local last = q.last
item = q[index]
q[index] = q[last]
q[last] = nil
q.last = last -1
return item
end

function RandomQueue.empty(q)
return q.last==-1
end

function RandomQueue.print(q)
-- For debugging. Not used
local t = {}
for i=0, q.last do
table.insert(t, string.format("(%f,%f)", q[i].x, q[i].y))
end
print (string.format("RandomQueue %d elem: %s", q.last+1, table.concat(t, " ")))
end

-- Point stores a coordinate pair
local Point = {}

function Point.new(x,y)
return {x=x, y=y}
end

-- Determines if a point is inside the rendered rectangle
local function inRectangle(point, width, height)
return (point.x>0 and point.y>0 and point.x<width and point.y<height)
end

-- Converts a point to a string representation, to be used as index in the grid
local function gridToString(gridPoint)
return string.format("(%d,%d)", gridPoint.x, gridPoint.y)
end

-- Computes the distance between two points
local function distance(p1, p2)
return math.sqrt(math.pow(p2.x-p1.x,2) + math.pow(p2.y-p1.y,2))
end

-- Prints the grid. For debugging. Not used
local function printGrid(grid)
print "==========="
for k,v in pairs(grid) do
print (string.format("%s:  %f, %f", k, v.x, v.y))
end
end

-- THE FUNCTIONS GIVEN IN THE ARTICLE
local function imageToGrid(point, cellSize)
local gridX = math.floor(point.x/cellSize)
local gridY = math.floor(point.y/cellSize)
return Point.new(gridX, gridY)
end

local function generateRandomPointAround(point, mindist)
local r1 = math.random()
local r2 = math.random()
local radius  = mindist * (r1+1)
local angle   = 2 * math.pi * r2
newX = point.x + radius * math.cos(angle)
newY = point.y + radius * math.sin(angle)
return Point.new(newX, newY)
end

-- This one is not given in the article. It returns the
-- values of several cells around the give gridPoint
-- We are using string indexes for the grid, but if we
-- try to access to a key which is not stored, lua gives
-- nil instead of an exception, so it works as expected
-- because we get nils for cells which have no dot inside
local function squareAroundPoint(grid, gridPoint, n)
local extreme = math.floor(n/2)
local result = {}
for i=-extreme,extreme do
for j=-extreme,extreme do
ii = i + gridPoint.x
jj = j + gridPoint.y
data = grid[gridToString(Point.new(ii,jj))]
if data == nil then
repr = "nil"
else
repr = string.format("(%f,%f)", data.x, data.y)
end
table.insert(result, data)
end
end
return result
end

local function inNeighbourhood(grid, point, mindist, cellSize)
local gridPoint = imageToGrid(point, cellSize)
cellsAroundPoint = squareAroundPoint(grid, gridPoint, 5)
for k,cell in pairs(cellsAroundPoint) do
if not (cell==nil) then
local d = distance(cell, point)
if distance(cell, point) < mindist then
return true
end
end
end
return false
end

-- This is the lua implementation of the pseudocode in the article
function generate_poisson(width, height, min_dist, new_points_count)
local cellSize = min_dist/math.sqrt(2)
local grid = {} -- Point.new(math.ceil(width/cellSize), math.ceil(height/cellSize))}
local processList = RandomQueue.new()
local samplePoints = {};  -- Empty list

-- Generate the first point
local firstPoint = Point.new(math.random()*width, math.random()*height)
-- print (string.format("newPoint: [%f, %f]", firstPoint.x, firstPoint.y))
RandomQueue.push(processList, firstPoint)
table.insert(samplePoints, firstPoint)
grid[gridToString(imageToGrid(firstPoint, cellSize))] = firstPoint

-- Generate other points from points in queue
while (not RandomQueue.empty(processList)) do
-- RandomQueue.print(processList)
-- printGrid(grid)
local point = RandomQueue.pop(processList)
for i=0,new_points_count do
local newPoint = generateRandomPointAround(point, min_dist)
-- print (string.format("newPoint: [%f, %f]", newPoint.x, newPoint.y))
-- Check the point is in the region and not too close
-- to other points
if inRectangle(newPoint, width, height) and
not inNeighbourhood(grid, newPoint, min_dist, cellSize) then
-- In this case, the point is accepted
RandomQueue.push(processList, newPoint)
table.insert(samplePoints, newPoint)
grid[gridToString(imageToGrid(newPoint, cellSize))] = newPoint;
end
end
end
return samplePoints
end

-- Initialize random seed
math.randomseed(os.time())

-- Function to generate the list of dots in a tikz's foreach compatible syntax
local data = generate_poisson(width, height, mindist, add_points)
local str = {}
for k,v in ipairs(data) do
table.insert(str, string.format("%f/%f", v.x, v.y))
end
tex.print(table.concat(str, ", "))
end

-- Function similar to the above, but the returned list is "ordered"
-- so that the points are more or less in the left-to-right,
-- top-to-down order
local cellSize = mindist/math.sqrt(2)
local function compare_coords(a,b)
aa = imageToGrid(a, cellSize);
bb = imageToGrid(b, cellSize);
if (aa.y == bb.y) then  -- If they are around the same row
return a.x<b.x;     -- the x coord orders them
else                    -- if not
return a.y>b.y;     -- the y coord orders them
end
end

local data = generate_poisson(width, height, mindist, add_points)
table.sort(data, compare_coords);
local str = {}
for k,v in ipairs(data) do
table.insert(str, string.format("%f/%f", v.x, v.y))
end
tex.print(table.concat(str, ", "))
end
\end{filecontents*}

\usepackage{tikz}
\usetikzlibrary{backgrounds}
\usepackage{poisson}

\begin{document}
\xdef\LstTxt{"duck","koala","marmot","honey","tiger","lion","bear","pineapple",
"pizza","sun","Mercure","Venus","Earth","Mars","Jupiter","Saturn","Uranus"}
\xdef\MaxWidth{0}
\foreach \X [count=\Y] in \LstTxt
{\pgfmathsetmacro{\mywidth}{max(\MaxWidth,width(\X))}
\xdef\MaxWidth{\mywidth}
\xdef\NumEntries{\Y}}
\pgfmathsetmacro{\GraceDist}{2*\MaxWidth*1pt/1cm}
\edef\mylist{\poissonpointslist{14}{14}{\GraceDist}{\NumEntries}}
% 14 x 14 is the size of the area to fill
% \GraceDist is the minimum distance between centers
\typeout{\mylist}