# Tightly covering a shape with grid (rasterization)

I am trying to re-create the images below.

I found them here: http://www.math.cornell.edu/~erin/docs/dimension.pdf which is a document written by Erin Pearse. It follows a lot of Falconer's Fractal Geometry book (which is what I am reading).

Would someone be able to help my automatically place the grids over the set please?

The shape I am using is produced by:

\documentclass[tikz,border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{hobby}
\begin{document}
\begin{tikzpicture}[use Hobby shortcut,closed=true,scale=0.3]
\draw [fill=blue!20, name path global=F,rotate=30]
(-3.5, 0.5) .. (-3.0, 2.5) .. (-1.0, 3.5) .. (1.5, 3.0) ..
( 4.0, 3.5) .. ( 5.0, 2.5) .. ( 5.0, 0.5) .. (2.5,-1.0) ..
( 0.0,-1.2).. (-3.0,-2.0) .. (-3.5, 0.5);
\node at (-2,1) {$F$};
\end{tikzpicture}
\end{document}


• While you wait for an answer to this question, can you go back to your previous ones and look if the answers solve your problems and accept them, if they do? – user36296 Jul 26 '17 at 21:13
• It would be useful if you showed us how you draw the F domain in the first place. You also state you want help covering automatically. Maybe you can show us how you'd do this manually ? – marsupilam Jul 26 '17 at 21:14
• @percusse And to add to the challenge, these 7 pictures show various covering methods, with at least 5 different algorithm ! – marsupilam Jul 26 '17 at 21:17
• Sure thing, but you may have noticed that the do-everything-for-me is not the most popular type of (tikz) questions, around here ?! – marsupilam Jul 26 '17 at 21:21
• @JSharpee I think this could be a very good question, with almost assured very skilled answer, if you provided the tikz drawing of the filled shape, and stated explicitely you would be content with the grid covering, with an appropriate illustration (just the 3 relevant pics). And I am less confident than you in the possibility for the other covering methods – marsupilam Jul 26 '17 at 21:29

It's a bit of a fiddle, and it takes ages, but...

\documentclass[varwidth,border=5]{standalone}
\usepackage{tikz}
\usetikzlibrary{intersections,hobby}
\begin{document}
\foreach \d [count=\i] in {1cm, 0.5cm, 0.25cm,0.125cm}{
\begin{tikzpicture}
\begin{scope}[use Hobby shortcut, closed=true, scale=0.3, local bounding box=F]
\draw [fill=gray, name path global=F]
(-3.5, 0.5) .. (-3.0, 2.5) .. (-1.0, 3.5) .. (1.5, 3.0) ..
( 4.0, 3.5) .. ( 5.0, 2.5) .. ( 5.0, 0.5) .. (2.5,-1.0) ..
( 0.0,-1.2).. (-3.0,-2.0) .. (-3.5, 0.5);
\node at (-2,2) {$F$};
\end{scope}
\pgfpointdiff{\pgfpointanchor{F}{south west}}{\pgfpointanchor{F}{north east}}
\pgfgetlastxy\w\h
\pgfmathsetmacro\W{int(ceil(\w/\d))}
\pgfmathsetmacro\H{int(ceil(\h/\d))}
\begin{scope}[shift=(F.south west)]
\begin{scope}
\clip \pgfextra{\expandafter\pgfsetpath\csname tikz@intersect@path@name@F\endcsname};
\foreach \x in {0,...,\W}
\foreach \y in {0,...,\H}
\draw (\x*\d-\d/2,\y*\d-\d/2) rectangle ++(\d,\d);
\end{scope}
\foreach \x in {0,...,\W}{
\foreach \y in {0,...,\H}{
\path [name path global=S] (\x*\d-\d/2,\y*\d-\d/2) rectangle ++(\d,\d);
\draw [name intersections={of=F and S, total=\T}]
\ifnum\T>0 (\x*\d-\d/2,\y*\d-\d/2) rectangle ++(\d,\d)\fi;
}
}
\end{scope}
\end{tikzpicture}
\\}
\end{document}


Although it might not be expected to work with holes, by adding (1,0.75) circle [radius=1.5] at the end of the "hobby" path, the 0.125cm iteration looks like this:

• Congratulations. This method works even if F contains holes! – Paul Gaborit Jul 27 '17 at 13:55

Obviously heavily inspired by Mark Wibrow's answer.

The algorithm is saner, though, since it scales linearly, instead of quadratically.

Now with holes, like the cool kids ;) (thanks to Paul Gaborit for the remark !)

## The code

\documentclass[varwidth,border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{intersections,hobby}
\begin{document}
\foreach \d [count=\i] in {1cm, 0.5cm, 0.25cm, 0.125cm}
{
\begin{tikzpicture}
\begin{scope}[use Hobby shortcut, closed=true, scale=0.3, local bounding box=F]
\draw [fill=blue!20, name path global=F,rotate=30]
(-3.5, 0.5) .. (-3.0, 2.5) .. (-1.0, 3.5) .. (1.5, 3.0) ..
( 4.0, 3.5) .. ( 5.0, 2.5) .. ( 5.0, 0.5) .. (2.5,-1.0) ..
( 0.0,-1.2).. (-3.0,-2.0) .. (-3.5, 0.5)
(-1,1) circle (1.7cm)
{
[rounded corners=1mm,rotate=50]
(-3.1,1.9) rectangle (-.2,.6)
};
\end{scope}
\path(F.south west);
\pgfgetlastxy\w\h
\pgfmathsetmacro\Wmin{int(floor(\w/\d))}
\pgfmathsetmacro\Hmin{int(floor(\h/\d))}
\path(F.north east);
\pgfgetlastxy\w\h
\pgfmathsetmacro\Wmax{int(ceil(\w/\d))}
\pgfmathsetmacro\Hmax{int(ceil(\h/\d))}

\pgfmathsetmacro{\opa}{min(100,300*\d/1cm)}
\tikzset{myGrid/.style={red!\opa}}
\begin{scope} % inner tiling
\clip \pgfextra{\expandafter\pgfsetpath\csname tikz@intersect@path@name@F\endcsname};
\draw[myGrid] (\Wmin*\d, \Hmin*\d) grid[step=\d] (\Wmax*\d, \Hmax*\d);
\end{scope}

\foreach \x in {\Wmin,...,\Wmax} % first pass, with vertical lines
{
\path [name path global=S] (\x*\d,\Hmin*\d) -- (\x*\d,\Hmax*\d);
\path [name intersections={of=F and S, name=i, total=\T}] node {\xdef\CC{\T}};
\ifnum\CC>0 \foreach \s in {1,...,\CC}
{
\path (i-\s); \pgfgetlastxy\w\h
\pgfmathsetmacro\hh{int(floor(\h/\d))}
\draw[myGrid] (\w-\d,\hh*\d) grid[step=\d] (\w+\d,\hh*\d+\d);
}
\fi;
}
\foreach \y in {\Hmin,...,\Hmax} % second pass, with horizontal lines
{
\path [name path global=S] (\Wmin*\d,\y*\d) -- (\Wmax*\d,\y*\d);
\path [name intersections={of=F and S, name=i, total=\T}] node {\xdef\CC{\T}};
\ifnum\CC>0 \foreach \s in {1,...,\CC}
{
\path (i-\s); \pgfgetlastxy\w\h
\pgfmathsetmacro\ww{int(floor(\w/\d))}
\draw[myGrid] (\ww*\d,\h-\d) grid[step=\d] (\ww*\d+\d,\h+\d);
}
\fi;
}
\end{tikzpicture}
\\}
\end{document}

• Congratulations. This method works even if F contains holes! – Paul Gaborit Jul 27 '17 at 11:32
• @PaulGaborit Merci ! Don't Mark Wibrow's method and this one work under exactly the same conditions, though ? – marsupilam Jul 27 '17 at 11:38
• You are right... but linear time with holes is better than quadratic time with holes! ;-) – Paul Gaborit Jul 27 '17 at 13:56

Mandatory Asymptote MWE:

% boxcount.tex :
%
\documentclass[10pt,a4paper]{article}
\usepackage{lmodern}
\usepackage{subcaption}
\usepackage[inline]{asymptote}
\begin{asydef}
size(5cm);
guide[] g;
g.push((-3.5,0.5)..(-3,2.5)..(-1,3.5)..(1.5,3)..(4,3.5)..(5,2.5)
..(5,0.5)..(2.5,-1)..(0,-1.25)..(-3,-2)..cycle);
pair gmin=min(g[0]), gmax=max(g[0]);
g.push(shift(2.5,1.2)*rotate(18)*scale(0.4)*shift(-(gmin+gmax)/2)*reverse(g[0]));
g.push(shift(-1,0)*rotate(-30)*scale(0.3)*shift(-(gmin+gmax)/2)*reverse(g[0]));
for(int i=0;i<g.length;++i) g[i]=shift(-gmin)*g[i];

void boxcount(guide[] g, int step){
pair gmin=min(g[0]), gmax=max(g[0]);
real gw=gmax.x-gmin.x;
real gh=gmax.y-gmin.y;
real u=min(gw,gh);
int n,nx,ny;
n=2^step;
nx=ceil(gw*n/(u));
ny=ceil(gh*n/(u));
guide gb=box(-(u/n,u/n)/2,(u/n,u/n)/2);

int[] count=array((nx+1)*(ny+1),0);
pair v;

filldraw(g,gray(0.8),black+0.4bp);

for(int i=0;i<=ny;++i){
for(int j=0;j<=nx;++j){
v=(u*j/n, u*i/n);
if( inside(g[0],v)){
count[i*(nx+1)+j      ]=1;
count[i*(nx+1)+j-1    ]=1;
count[(i-1)*(nx+1)+j-1]=1;
count[(i-1)*(nx+1)+j  ]=1;
}
}
}

for(int k=1;k<g.length;++k){
for(int m=0;m<count.length;++m){
if(count[m]>0){
int i,j;
i=m#(nx+1);
j=m-i*(nx+1);
v=(u*(j+1/2)/n, u*(i+1/2)/n);
if(inside(g[k], shift(v)*gb)==1){
count[i*(nx+1)+j]=0;
}
}
}
}

int N=0;

for(int m=0;m<count.length;++m){
if(count[m]>0){
int i,j;
i=m#(nx+1);
j=m-i*(nx+1);
v=(u*j/n, u*i/n);
draw(box(v,v+(u/n, u/n)),gray(0.3)+0.3bp);
++N;
}
}
label("$F$", (2,4));
label("$N="+string(N)+"$",(gw,0),plain.NW);
}

\end{asydef}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm]{geometry}
%
\begin{document}
%
\begin{figure}
\captionsetup[subfigure]{justification=centering}
\centering
\begin{subfigure}{0.3\textwidth}
\centering
\begin{asy}
boxcount(g,3);
\end{asy}
%
\caption{Step=3}
\label{fig:1a}
\end{subfigure}
%
\begin{subfigure}{0.3\textwidth}
\centering
\begin{asy}
boxcount(g,4);
\end{asy}
%
\caption{Step=4}
\label{fig:1b}
\end{subfigure}
%
\begin{subfigure}{0.3\textwidth}
\centering
\begin{asy}
boxcount(g,5);
\end{asy}
%
\caption{Step=5}
\label{fig:1c}
\end{subfigure}
%
\caption{Box-Counting}
\label{fig:1}
\end{figure}
%
\begin{figure}
\centering
\begin{asy}
size(8cm);
boxcount(g,6);
\end{asy}
\caption{Step=6}
\label{fig:2}
\end{figure}

\end{document}
%
% Process:
%
% pdflatex boxcount.tex
% asy boxcount-*.asy
% pdflatex boxcount.tex

• Asymptote has a boolean inside(curve,point) function, and arrays ?! That's cheating ! ;) Good work, thanks for the nice example ! – marsupilam Jul 27 '17 at 20:00
• @marsupilam: Even better! It has int inside(curve,curve) as you can see in the code above. – g.kov Jul 27 '17 at 20:10
• While it's nice to count boxes, I guess OP would be glad if you could actually compute upper bounds for the box dimension of the domain : dim(F) = - log(N_boxes)/log(box_side), as explained in the PDF lectures above. – marsupilam Jul 27 '17 at 20:50
• @marsupilam: And the answer is 2. (Or should I say 42?). – g.kov Jul 27 '17 at 21:17
• Yeah it should be close to 2... The more boxes, the closer ! – marsupilam Jul 27 '17 at 21:49