path: root/circrect.tex

\documentclass[dutch, a4paper, twocolumn]{article}

\usepackage{babel}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{csquotes}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{listings}
\usepackage[noabbrev]{cleveref}
\usepackage[
	backend=biber,
	bibencoding=utf8,
]{biblatex}
\usepackage{tikz}
\usepackage{needspace}

\usetikzlibrary{patterns}
\lstset{
	numbers=left,
	numberstyle=\tiny,
	numbersep=10pt,
	basicstyle=\ttfamily,
}
\addbibresource{refs.bib}
\setdescription{
	labelwidth=3ex
}
\DeclareMathOperator{\clamp}{clamp}

\title{Exacte berekening van het gedeelde oppervlak van een cirkel en een rechthoek}
\author{Loek Le Blansch}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
Dit document beschrijft een functie waarmee het gedeelde oppervlak van een
willekeurige cirkel met een willekeurige rechthoek exact berekend kan worden. Een
interactief voorbeeld is beschikbaar op Desmos \autocite{circrect2}, en een
voorbeeldimplementatie van de complete formule in de programmeertaal Python is
beschikbaar in de bijlage van dit document (bijlage \ref{attach:python-impl}).
\end{abstract}

\section{Definities}
De volgende variabelen (met uitzondering van functieparameters) worden gebruikt in de
berekeningen. Deze variabelen zijn weergegeven in een diagram in \cref{fig:context}.

\begin{description}
	\item[$ab$] (de rechthoek)
	\item[$a$] (\'e\'en hoekpunt van de rechthoek $ab$)
		\begin{description}
			\item[$a_x, a_y$] (de co\"ordinaten van punt $a$)
		\end{description}
	\item[$b$] (tegenovergestelde hoekpunt van $a$ in rechthoek $ab$)
		\begin{description}
			\item[$b_x, b_y$] (de co\"ordinaten van punt $b$)
		\end{description}
	\item[$o$] (het gedeelde oppervlak van $ab$ en $c$)
\end{description}

\begin{figure}
	\centering
	\begin{tikzpicture}[scale=2.5]
		% draw area
		\clip(-1.25,-0.25) rectangle (1.75,1.75);

		% axes
		\draw[->] (-1.5,0) -- (1.5,0) node[right]{$x$};
		\draw[->] (0,-1.5) -- (0,1.5) node[above]{$y$};

		% labeled points
		\coordinate [label=225:$a$] (a) at (0.5,0.5);
		\coordinate [label=45:$b$] (b) at (1.0,1.0);

		% draw rectangle, circle and line
		\draw[thick] (a) rectangle (b);
		\draw[thick] (0,0) circle (1);
		% label a, a and b
		\path[thick,<->] (0,0) edge node[below left] {1} (-0.707,0.707);
		\node[fill,circle,inner sep=1.5pt] at (a) {};
		\node[fill,circle,inner sep=1.5pt] at (b) {};

		% hatch overlapping area
		\begin{scope}
			\clip (0,0) circle (1);
			\fill[pattern=north east lines] (a) rectangle (b);
		\end{scope}
	\end{tikzpicture}
	\caption{Voorbeeldvisualisatie toepassing}
	\label{fig:context}
\end{figure}

Omdat elke transformatie bestaand uit een willekeurige schaling en/of translatie van
cirkel $c$ uit te drukken is door de bijbehorende inverse transformatie toe te passen
op rechthoek $ab$, is cirkel $c$ een eenheidscirkel.

Om de formules verder te vereenvoudigen worden de volgende eisen aan de
invoerwaarden gesteld:
\begin{equation}\label{eq:constrain:x}
-1 \leq a_x \leq b_x \leq 1
\end{equation}
\begin{equation}\label{eq:constrain:y}
-1 \leq a_y \leq b_y \leq 1
\end{equation}

\section{Aanpak}

Mijn initi\"ele aanpak voor dit probleem was de integraal berekenen op het interval
$[a_x, b_x]$ van een kromme die een halfrond begrensde tussen $[a_y,b_y]$. Deze
aanpak werkte in de Desmos grafische rekenmachine \autocite{circrect1}, maar was niet
implementeerbaar in Python.

Omdat de berekening van $o$ toegepast wordt in de context van een computerprogramma,
is het van belang dat de formule die deze waarde berekent constant is. Dit betekent
dat de (halfrond) functie die geprimitiveerd wordt niet de min, max of abs functies
kan gebruiken.

\begin{figure}
	\centering
	\begin{tikzpicture}[scale=2.5]
		% draw area
		\clip(-0.1,-0.25) rectangle (1.5,1.25);

		% axes
		\draw[->] (-1,0) -- (1.25,0) node[right]{$x$};

		% labeled points
		\coordinate (a) at (0.25,0.25);
		\coordinate (b) at (1.00,0.75);

		% draw rectangle, circle and line
		\draw[thick] (a) rectangle (b);
		\begin{scope}
			\clip (-2,0) rectangle (2,2);
			\draw[thick] (0,0) circle (1);
		\end{scope}

		% hatch overlapping area
		\begin{scope}
			\clip (0,0) circle (1);
			\fill[pattern=north east lines] (0.25,5) rectangle (b);
			\fill (a) rectangle (b);
			\fill[pattern=crosshatch dots] (a) rectangle (5,0);
		\end{scope}

		% labels
		\node[anchor=east] at (0.25,0.875) {1};
		\node[anchor=east] at (0.25,0.500) {2};
		\node[anchor=east] at (0.25,0.125) {3};
	\end{tikzpicture}
	\caption{Markering ongewenste gebieden}
	(alleen het oppervlak van gebied 2 is gewenst)
	\label{fig:unwanted-area}
\end{figure}

De aanpak is als volgt:
\begin{enumerate}
	\item\label{step:semicircfn} Defini\"eer de functie $f$ als alleen het bovenste
		halfrond van cirkel $a$.
	\item Beschouw alleen het domein $[a_x, b_x]$. Als de integraal van $f$ genomen zou
		worden op dit interval, zou de uitkomst niet alleen het oppervlak van de overlap
		met rechthoek $bc$ zijn, maar het oppervlak van de bovenste rand van de cirkel
		tot de $x$-aslijn. Dit is ongewenst.
	\item\label{step:regdelbelow} De regio tussen $[0, a_y]$ (regio 3 in
		\cref{fig:unwanted-area}) kan worden verwijderd door een verticale translatie van
		$-a_y$ toe te passen op $f$ v\'o\'or de integraal wordt berekend. Dit zorgt voor
		problemen zodra punt $(a_x,a_y)$ of $(b_x,a_y)$ buiten cirkel $a$ valt.
	\item\label{step:regdelabove} De regio tussen $[b_y, 1]$ (regio 1 in
		\cref{fig:unwanted-area}) kan worden verwijderd door deze te berekenen en af te
		trekken van de resulterende regio uit stap \ref{step:regdelbelow}. Deze regio kan
		worden berekend door een tweede integraal te berekenen, maar op $f$ met een
		translatie van $-b_y$. Dit zorgt weer voor problemen, maar bij de punten
		$(a_x,b_y)$ en $(b_x,b_y)$.
	\item\label{step:limitintdomain} De tot nu toe genoemde problemen kunnen worden
		opgelosd door de intervallen van de integralen te begrenzen tot het punt waar de
		getransleerde functies de $x$-as snijden.
\end{enumerate}

Deze stappen worden in detail beschreven in \cref{sec:calculation}.

\section{Berekening}
\label{sec:calculation}

Stap \ref{step:semicircfn} is beschreven in \cref{eq:fn:f}. Om later voor stap
\ref{step:limitintdomain} het domein van de integraal te begrenzen is ook de inverse
van functie $f$ nodig. Omdat de functie $f$ een cirkel beschrijft, is de inverse
functie gelijk aan functie $f$.
\begin{equation}\label{eq:fn:f}
f\left(x\right) = \sqrt{1-x^2}
\end{equation}

Stappen \ref{step:regdelbelow} en \ref{step:regdelabove} zijn beschreven in
\cref{eq:fn:fa,eq:fn:fb}.
\begin{align}
\label{eq:fn:fa} f_a\left(x\right) &= f\left(x\right)-a_y\\
\label{eq:fn:fb} f_b\left(x\right) &= f\left(x\right)-b_y
\end{align}

Stap \ref{step:limitintdomain} is beschreven in
\cref{eq:var:xb1,eq:var:xb2,eq:var:xc1,eq:var:xc2}.
\begin{align}
\label{eq:fn:clamp} \clamp\left(a,b,x\right) &=
	\max\left(a, \min\left(b, x\right)\right)\\
\label{eq:var:xb1} x_{a_1} &=
	\clamp\left(a_x,b_x,-f\left(a_y\right)\right)\\
\label{eq:var:xb2} x_{a_2} &=
	\clamp\left(a_x,b_x, f\left(a_y\right)\right)\\
\label{eq:var:xc1} x_{b_1} &=
	\clamp\left(a_x,b_x,-f\left(b_y\right)\right)\\
\label{eq:var:xc2} x_{b_2} &=
	\clamp\left(a_x,b_x, f\left(b_y\right)\right)
\end{align}

Nu kan de oppervlakte $o$ berekend worden door de integralen uit te rekenen volgens
\cref{eq:var:oa,eq:var:ob,eq:var:o}.
\begin{align}
\label{eq:var:oa} o_a &= \int_{x_{a_1}}^{x_{a_2}}f_a\left(x\right)dx\\
\label{eq:var:ob} o_b &= \int_{x_{b_1}}^{x_{b_2}}f_b\left(x\right)dx\\
\label{eq:var:o} o &= o_a - o_b
\end{align}

\section{Uitbereiding}

Om \cref{eq:var:o} als een constante formule te defini\"eren moet functie $f$
geprimitiveerd worden. De primitieve van functie $f$ is gedefini\"eerd in
\cref{eq:fn:F} als de nieuwe functie $F$ met een extra argument $n$ voor een
verticale verschuiving van $f$.
\begin{equation}\label{eq:fn:F}
	\begin{aligned}[c]
F\left(x,n\right)&=\int\left(f\left(x\right) + n\right) dx\\
								 &=\frac{1}{2}\left(2nx+\sqrt{1-x^2}x+\sin^{-1}\left(x\right)\right)
	\end{aligned}
\end{equation}

\needspace{3cm}
Nu kan een nieuwe functie $g$ beschreven worden die alleen afhankelijk is van
ingevoerde variabelen:
\begin{align}
\begin{split}
o ={}& o_a - o_b
\end{split}\\
\begin{split}
={} &\int_{x_{a_1}}^{x_{a_2}}f_a\left(x\right)dx\\
  - &\int_{x_{b_1}}^{x_{b_2}}f_b\left(x\right)dx
\end{split}\\
\begin{split}
={} &\int_{x_{a_1}}^{x_{a_2}}\left(f\left(x\right)-a_y\right)dx\\
  - &\int_{x_{b_1}}^{x_{b_2}}\left(f\left(x\right)-b_y\right)dx
\end{split}\\
\begin{split}
={} &\left(F\left(x_{a_2}, -a_y\right) - F\left(x_{a_1}, -a_y\right)\right)\\
  - &\left(F\left(x_{b_2}, -b_y\right) - F\left(x_{b_1}, -b_y\right)\right)
\end{split}\\
\begin{split}
={} &F\left(x_{a_2}, -a_y\right) - F\left(x_{a_1}, -a_y\right)\\
  - &F\left(x_{b_2}, -b_y\right) + F\left(x_{b_1}, -b_y\right)
\end{split}\\
\begin{split}\label{eq:fn:g}
g\left(a,b\right)
={} &F\left(\clamp\left(a_x,b_x, f\left(a_y\right)\right), -a_y\right)\\
  - &F\left(\clamp\left(a_x,b_x,-f\left(a_y\right)\right), -a_y\right)\\
  - &F\left(\clamp\left(a_x,b_x, f\left(b_y\right)\right), -b_y\right)\\
  + &F\left(\clamp\left(a_x,b_x,-f\left(b_y\right)\right), -b_y\right)
\end{split}
\end{align}

De complete oplossing bestaat uit de functie $g$ \'e\'en keer normaal berekenen, en
nog een keer met de rechthoek $ab$ gespiegeld om de $x$-as (vermenigvuldig $a_y$ en
$b_y$ met $-1$). De som van deze twee waarden vormt oppervlak $o$.

Let op dat bij de gespiegelde aanroep van functie $g$, de $y$-co\"ordinaten van de
punten $a$ en $b$ omgedraaid zijn, om de eisen uit
\cref{eq:constrain:x,eq:constrain:y} te waarborgen.
\begin{equation}\label{eq:fn:h}
	\begin{aligned}[c]
		h\left(a,b\right)
		= g\,(&\left(a_x, \max\left(0, a_y\right)\right),\\
			    &\left(b_x, \max\left(0, b_y\right)\right))\\
		+ g\,(&\left(a_x, \max\left(0,-b_y\right)\right),\\
			    &\left(b_x, \max\left(0,-a_y\right)\right)
		)
	\end{aligned}
\end{equation}

De Python implementatie in bijlage \ref{attach:python-impl} heeft enkele handige
toevoegingen:
\begin{itemize}
	\item Invoergetallen worden automatisch genormaliseerd
	\item De formule schaalt het oppervlak $o$ automatisch voor elke willekeurige
		straal van cirkel $c$
\end{itemize}

\section*{Colofon}

Ik heb geen wiskunde gestudeerd, en kan geen bewijs geven dat de methode die
beschreven is in dit document foutloos is.

\printbibliography

\clearpage\pagestyle{empty}
\onecolumn\appendix
\section{Python implementatie}
\label{attach:python-impl}
\fontsize{8.5}{12}\selectfont
\lstinputlisting{circrect.py}

Dit document \autocite{self}, en de bovenstaande broncode \autocite{selfsrc} zijn ook
online beschikbaar.

\end{document}