Tightly covering a shape with grid (rasterization)
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:
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 output
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}
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